Без дифференцирования многочленов объясните Σ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