ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73673
Темы:    [ Сочетания и размещения ]
[ Индукция (прочее) ]
[ Треугольник Паскаля и бином Ньютона ]
[ Формула включения-исключения ]
[ Производная и кратные корни ]
[ Подсчет двумя способами ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

m и n – натуральные числа,  m < n.  Докажите, что  


Решение 1

  Рассмотрим алфавит из n букв  {a1, a1, ..., an}.  Подсчитаем двумя способами количество слов длины m. С одной стороны, оно равно nm. С другой стороны, такие слова не могут содержать все буквы алфавита (так как  m < n),  поэтому все такие слова принадлежат объединению
A1 ∪ ... ∪ An ,   где Ai  – множество всех слов длины m, не содержащих букву ai. Заметим, что пересечение k множеств типа Ai  – это множество слов, записанных в алфавите из  nk  букв, поэтому оно состоит из  (nk)m  слов. Теперь по формуле включения-исключения получаем
    Это эквивалентно доказываемому равенству.


Решение 2

  Рассмотрим многочлены   
  Заметим, что   P1(x) = ((1 + x)n)′,   Pm+1(x) = (xPm(x))′.   Поскольку число  –1  является корнем многочлена  (1 + x)n  кратности n, то оно будет корнем многочлена P1(x) кратности  n – 1,  корнем P2(x) кратности  n – 2,  ..., корнем Pm(x) кратности  nm.  А интересующая нас сумма равна  Pm(–1).

Замечания

Другие решения и обсуждение задачи см. в решениях Задачника "Кванта", а также в статье
  В. Вагутен. "Биномиальные коэффициенты, многочлены, последовательности" или
  Н. Васильев, В. Гутенмахер. "Числа Cnk, многочлены, последовательности" (сб. "Задачник "Кванта". Математика, ч. 3", 1997).

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 4
Задача
Номер М138

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .