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

Бином Ньютона Решение.

Бином Ньютона Решение.

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

Ответ. а) С^00 = 100; б) С^ = 6; в) С52 = 10; г) С^ = 15.

Решение. Перечислим все подмножества, число которых надо найти.

а)  {1},..., {100}.

б)  {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

в)  Двухэлементное подмножество множества {1,2, 3,4, 5} либо содержит число 5, либо не содержит. Если подмножество не содержит число 5, то оно является подмножеством множества {1, 2, 3, 4}. Двух­элементных подмножеств множества {1, 2, 3, 4} ровно 6 (см. преды­дущий пункт). Остальных подмножеств четыре: {1, 5}, {2, 5}, {3, 5}, {4,5}.

г)  Когда мы выбираем из множества {1, 2, 3, 4, 5, 6} четыре эле­мента, остается два невыбранных элемента. При этом каждая пара невыбранных элементов однозначно определяет четверку выбранных (все остальные элементы), и наоборот. Следовательно, подмножеств из четырех элементов столько же, сколько и пар.

Итак, достаточно выписать все двухэлементные подмножества множества {1, 2, 3, 4, 5, 6}. Аналогично предыдущему пункту, мы по­лучим все двухэлементные подмножества множества {1, 2, 3, 4, 5} и еще пять: {1, 6}, {2, 6}, {3, 6}, {4, 6}, {5, 6}.

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

Решение. а) Каждому к-элементному подмножеству соответствует (п - к)-элементное подмножество, состоящее из элементов, не принадлежащих данному подмножеству, и наоборот.

б)  Покрасим один элемент в красный цвет, а остальные — в синий.

Тогда все т-элементные подмножества разобьются на два класса: множества, содержащие красный элемент, и множества, не содер­жащие его. Заметим, что т-элементное подмножество, не содержа­щее красный элемент, — это в точности т-элементное подмножество (п - 1)-элементного множества синих элементов. Следовательно, та­ких подмножеств ровно ст-Ц. Аналогично, т-элементное подмноже­ство, содержащее красный элемент, — это объединение множества, состоящего из красного элемента, и (т - 1)-элементного подмноже­ства множества синих элементов. Следовательно, таких подмножеств Ст-1. Итак, Ст = Ст 1 + Ст-1.