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

Обозначим это число через х.

Обозначим это число через х.

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

Решение 2. Из задачи 7 следует, что подмножеств, состоящих из более чем 8 элементов, столько же, сколько и подмножеств, состоящих из менее чем 8 элементов. Обозначим это число через х. Достаточ­но сравнить х с С86 = 12870. Заметим для этого, что 2х + 12870 — это число всех подмножеств в множестве из 16 элементов, то есть 2х + 12870 = 65536, откуда х = 26333 > 12870.

Задача 15. Найдите число таких последовательностей длины 16 из нулей и единиц, в которых не менее чем три единицы.

Указание. Заметьте, что это число равно разности числа всех после­довательностей длины 16 из нулей и единиц и числа таких последо­вательностей, в которых не более двух единиц.

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

Решение. Учитывая указание, получаем ответ: 216 — С06 — С^6 — С26 = = 65536 — 1 — 16 — 120 = 65399.

Задача 16. Решите указанные преподавателем задачи из листка «Комбинаторика 1» для произвольных п и к.

Задача 17*. Сколькими способами можно выбрать неотрицательные целые числа х1, х2,..., хт такие, что х1 + х2 +... + хт = п?

Указание. Это число способов поставить в очередь т — 1 манекен и п человек.

Решение. Заметим, что искомое число — это число способов поста­вить в очередь т — 1 манекен и п человек. Действительно, каждой такой очереди можно поставить в соответствие следующий набор чисел: х1 —количество людей, стоящих в очереди перед первым ма­некеном, х2 — между первым и вторым манекеном, ., хт — после по­следнего манекена. Построенное соответствие взаимно однозначно (проверьте!). Но число способов поставить в очередь т — 1 манекен и п человек — это в точности число способов выбрать в этой очереди

( п + т — 1Л

п мест для людей, то есть I            I.