Таблицы Брадиса

Г'г + 11 = Г'О + Г ,г 1 = п! +

Г'г + 11 = Г'О + Г ,г 1 = п! +

Элементы математики в задачах - Г. А. Мерзон

(п - к)!

неупорядоченного к-элементного набора можно получить ровно к! упорядоченных.

Решение 2. Докажем индукцией по п следующую последовательность утверждений Ап: «Для любого целого 0 ^ к ^ п выполнено равенство

п\

Кк) Щп-ку.'*

База индукции очевидна.

Шаг индукции. Пусть Ап верно. Докажем Ап+1. Для к е {0, п + 1}

У п+1 И         (п + 1)!      (п + 1)! ,-т                  п 7^,1

получаем [ к )=1 =                  = Щп+1_к)Г Пусть теперь 0<к< п+1.

Тогда

+1 п п

Г'г + 11 = Г'О + Г ,г 1 = п! + ■

V к ) \к) \k-\J к\(п — к)\

к!(п - к + 1)!    к!(п - к +1)!'

.                     Шаг индукции доказан. Следовательно, все утверждения Ап верны.

Задача 13. Докажите, что:                                                                                 ^

а)  У 0 И2+У п И2+- +Уп И2=У и И;

б) У 0 И+(" Г)+ ■ +Уп; -Г) +(п Г) Кп+к+‘);

в) УпИ +2(22)+ •У + п(^= п• 2п-1;

г) о •( т и =( т) ■(:) ■

Указание. а) Воспользуйтесь задачей 3.

Решение. В = {1, 2,..., 2п}, Аг = {1, 2,. . . , п} и А2 = {п +1,. . . , 2п}. Каж­дому п-элементному подмножеству X множества В поставим в со­ответствие два подмножества: X п Аг и X п А2. Заметим, что мы получили биекцию между множеством всех п-элементных подмно­жеств множества В и множеством пар подмножеств множеств А1 и А2, сумма количеств элементов в которых равна п. Следовательно,

(?) = ( 0)( п) +( ЮС",)+■■+(п) О-

Осталось воспользоваться тем, что п = п

128                    Комбинаторика 2. Бином Ньютона

а)  Разобьем все к-элементные подмножества множества {1,2,...

..., п + к + 1} на классы подмножеств, содержащих все числа от 1 до I, но не содержащих число I +1. Например, подмножества, не содер­жащие единицу, будут отнесены при этом в класс А0; подмножества, содержащие 1, но не содержащие 2, — в класс А1, и т. д.