Сборник задач по математике с решениями - А. А. Рывкин, Е. Б. Ваховский 2003

Задачи
Соединения и бином

Эта глава содержит задачи по комбинаторике, а также задачи, связанные с возведением в степень двучлена ax + b. Выражение (ax + b) называют биномом Ньютона и рассматривают, как правило, его разложение в ряд по степеням x и коэффициенты этого разложения — они зависят от а и b — при различных степенях x.

Комбинаторика изучает всевозможные комбинации из элементов данного конечного множества. Простейшие из таких комбинаций: перестановки, размещения и сочетания.

Перестановки состоят из одних и тех же элементов некоторого множества и отличаются одна от другой только порядком их расположения. Число всех возможных перестановок для множества, состоящего из n различных элементов, обозначают P(n):

P(n) = 1 · 2 · 3 · ... · n = n! (1)

Символ n! (читается «эн факториал») обозначает произведение первых n чисел натурального ряда: 1! = 1, 2! = 2, 3! = 6, 4! = 24, ... . По определению 0! = 1.

Следующий вид комбинаций — размещения из n различных элементов, образующих множество, в группы по k различных элементов в каждой. При этом два размещения считают разными, если они отличаются либо элементами, либо порядком их расположения. Подобные ситуации возникают при размещении постояльцев в гостинице, зрителей в театральном зале, пассажиров в поезде. Число всех возможных размещений по k различных элементов в каждом размещении, формируемых из n различных элементов данного множества, обозначают А_n^k. Имеет место формула:

Сочетания из n элементов по k элементов — комбинации, составленные из данных n элементов и содержащие по k (k ≤ n) элементов в каждой, отличающиеся одна от другой хотя бы одним элементом. С — число сочетаний из n по k:

Наряду с соединениями, в которые каждый из n различных элементов некоторого фиксированного множества входит один раз, можно рассматривать соединения с повторениями, допускающие появление одного и того же элемента более одного раза.

Если задан алфавит из n различных букв и поставлена задача составить всевозможные слова по k букв в каждом, то речь идет о размещениях с повторениями. Обратите внимание на то обстоятельство, что слова могут быть любой длины, а потому нет необходимости в выполнении ограничения k ≤ n. Слова aba и baa считаются различными (входящие в них элементы образуют разные последовательности).

Число

всевозможных различных размещений с повторениями из n различных элементов по k элементов в каждом находится по формуле

Доказывается эта формула с помощью рекуррентного соотношения

которое устанавливается следующим рассуждением. Если первая буква в слове из k букв фиксирована, то в оставшиеся k − 1 ячеек можно разметить буквы

способами. Для каждого из этих способов остается n возможностей для выбора буквы, стоящей на первом месте. В результате мы получим все размещения с повторениями из n по k.

Размещения с повторениями, образованные из n элементов a₁, a₂, ..., а_n так, что каждый из этих элементов входит в размещение по крайней мере один раз, называются перестановками с повторениями. Если известно, что элемент a₁ входит α₁ раз, элемент a₂ входит α₂ раз, ..., элемент a_n входит α_n раз, то число всевозможных таких перестановок обозначают

и оно может быть найдено по формуле

Два сочетания с повторениями из n элементов по k в каждом считаются различными тогда и только тогда, когда они отличаются по крайней мере одним элементом или какой-нибудь элемент входит в эти соединения различное число раз. Число всевозможных сочетаний с повторениями определяется по формуле

вывод которой состоит в доказательстве того факта, что допущение о возможности повторений элементов равносильно увеличению числа элементов, из которых образуются сочетания, на k − 1.

Для любого натурального n справедливы разложения

Для биномиальных коэффициентов справедливы равенства:

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

21.2. Имеется одна перестановка из пяти элементов: а₁, а₂, а₃, а₄, а₅. Найдите число всех перестановок из этих элементов, в каждой из которых на первом месте стоит элемент, отличный от а₁, а на втором — элемент, отличный от а₂.

21.3. Сколько можно образовать семизначных чисел из цифр 1, 2, 3, ..., 8 с тем, чтобы цифра 2 входила в каждое число не меньше, чем три раза?

21.4. Сколько восьмизначных чисел можно образовать из цифр 0, 1, 2, 3, 4, 5, если в каждом числе цифра 1 содержится три раза, а остальные цифры по одному разу?

21.5. Экскурсанты заказали на пароходе 8 четырехместных кают. Все места в каждой из кают и все каюты равноценны. Сколькими способами могут экскурсанты разместиться в каютах, если их 32 человека?

21.6. Вычислите сумму

21.7. Найдите все значения n, при которых какие-либо три последовательных коэффициента разложения бинома (x + а)ⁿ являются тремя последовательными членами арифметической прогрессии.

21.8. Найдите число неподобных между собой членов разложения

(а + b + с + d)ⁿ.

21.9. Найдите коэффициент при х^k в разложении

(1 + x + x² + ... + х^{n − 1})².

21.10. Для бинома (¹/₅x + ²/₅)ⁿ найдите натуральный показатель n, если известно, что десятый член разложения этого бинома имеет наибольший коэффициент.

21.11. Определите число отличных от нуля коэффициентов в разложении

(1 + x² + х⁵)²⁰ = а₀ + а₁х + а₂х² + ... + а₁₀₀х¹⁰⁰.

21.12. Дана последовательность а₁, а₂, а₃, ..., а₁₀. Сколькими способами, сохраняя фиксированный порядок элементов последовательности, ее можно разбить на группы, каждая из которых состоит из одного элемента или двух рядом стоящих элементов?

21.13. На плоскости проведены m параллельных прямых и n прямых, пересекающих эти прямые и друг друга. Никакие три прямые не проходят через одну точку. На сколько областей (частей) эти прямые разбивают плоскость?