К содержанию
Quantoros

Без дифференцирования многочленов объясните Σk=0..n C(n,k)2^k=3^n.

Quant ResearchУровень: ПрактикаCounting by a distinguished symbol

Без дифференцирования многочленов объясните Σk=0..n C(n,k)2^k=3^n.

Подсказки
  • Разбейте троичные строки по ненулевым позициям.
  • У выбранной позиции два значения.

Ответ

Считайте строки длины n из {0,1,2}. Выберите k ненулевых позиций и заполните их 1 или 2: C(n,k)2^k. Сумма учитывает каждую из 3^n строк ровно раз.

Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы