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

Проект МЦНМО
при участии
школы 57
Задача 61525
Темы:    [ Раскладки и разбиения ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Обозначим через Pk,l(n) количество разбиений числа n на не более чем k слагаемых, каждое из которых не превосходит l.
Докажите равенства:
  а)  Pk,l(n) – Pk,l–1(n) = Pk–1,l(n – l);
  б)  Pk,l(n) – Pk–1,l(n) = Pk,l–1(nk);
  в)  Pk,l(n) = Pl,k(n);
  г)  Pk,l(n) = Pk,l(kl – n).


Подсказка

в) Рассмотрите симметричную диаграмму Юнга.


Решение

 а) Из каждого разбиения  n – l = a1 + a2 + ... + am  числа  nl  на слагаемые, не превосходящие l, можно получить разбиение  n = a1 + a2 + ... + am + 1  числа n. Но так получаются не все интересующие нас разбиения (которых Pk,l(n)), а только те, которые содержат слагаемое, равное l. Количество разбиений, не содержащих таких слагаемых, равно Pk,l–1(n).

  б) Можно доказать это аналогично а), но проще заметить, что б) сразу следует из а) и в).

  в) По разбиению, обладающему указанными свойствами, можно построить соответствующую диаграмму Юнга. Симметричная диаграмма Юнга соответствует как раз разбиению числа n на не более чем l слагаемых, каждое из которых не превосходит k.

  г) Разбиению   n = a1 + a2 + ... + am  (mkail)   числа n сопоставим разбиение   kl – n = (l – a1) + (l – a2) + ... + (l – am) + l + ... + l   числа  kl – n,  где слагаемое  l – ai  отбрасывается, если оно равно нулю, а число слагаемых l равно  k – m.

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

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 11
Название Последовательности и ряды
Тема Последовательности
параграф
Номер 4
Название Многочлены Гаусса
Тема Последовательности
задача
Номер 11.098

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

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