Свойства сочетаний (биномиальных коэффициентов)

1)

2)

3) основное

4)

5) .

Сочетаниями с повторениями из n -типов по k -элементам (k и n в любом соотношении) называются все k -элементные последовательности из n -типов, отличающиеся составом элементов. .

3.Сколькими способами можно разложить предметов одного сорта, …, предметов k-го сорта в 2 ящика? Следствия.

Так как в каждый ящик может попасть от 0 до предметов i -го сорта (во второй все оставшиеся), по правилу произведения получаем ( +1)*( +1)*...*( +1) способов раскладки.

Следствие 1. Если , то их можно разложить способами.

Следствие 2. Если в каждый ящик нужно положить не менее предметов i -того сорта, то получаем:

4.Даны n различных предметов и k ящиков. Надо положить в первый ящик предметов, …, в k -тый - , где . Сколькими способами можно сделать такое распределение, если не интересует порядок распределения предметов в ящике?

Так как элементы 1-го типа можно переставлять способами, …, k-го типа способами, то по правилу произведения элементы перестановки можно переставить способами так, что она останется неизменной. То же самое верно и для любого другого расположения элементов. Поэтому множество всех n! перестановок распадается на части, состоящие из одинаковых перестановок каждая. Поэтому число различных перестановок с повторениями, равно: .

5.Даны n различных предметов и k одинаковых ящиков. Надо положить в каждый ящик n=n/k предметов. Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике?

Так как ящики не пронумерованы, то их тоже нужно переставлять, число таких перестановок, равно k!. Поэтому, полученный в предыдущей задаче результат необходимо разделить на k!. Получаем: .

6.Сколькими способами можно распределить n одинаковых предметов в k ящиков?

Выложим все предметы в один ряд, добавим к ним k–1 одинаковых разделяющих предмета. Переставим всеми возможными способами n данных одинаковых предметов и k–1 разделяющих. Каждая такая перестановка определяет один из способов распределения. А именно предметы, расположенные до первого разделителя, положим в первый ящик, предметы, расположенные между первым и вторым разделителем – во второй ящик и так далее, предметы расположенный после k–1 разделителя, – в k ящик. По формуле перестановок с повторениями число таких перестановок равно: .

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

Так как каждый предмет можно положить в любой из k ящиков, получаем: .

8.Сколькими способами можно положить n различных предметов в k ящиков, если не должно быть пустых ящиков?

Пусть r ящиков – пустые ( =1, 2, 3, …, k -1).

пустых ящиков можно выбрать способами, а в оставшихся ящиках предметы можно разложить способами.

Тогда число распределений, при которых нет пустых ящиков, равно:

9.Имеется предметов одного сорта, …, предметов s -ого сорта. Сколькими способами их можно разложить по k ящикам, если не должно быть пустых ящиков?

Пусть r ящиков – пустые (r =1, 2, 3, …, k -1).

– число способов когда есть пустых ящиков.

Тогда число распределений, при которых нет пустых ящиков, равно:

, где

10.Сколько существует способов разложить n различных предметов в k различных ящиков, с учетом расположения предметов в ящиках, если все предметы должны быть использованы? Следствие.

Выложим все предметы в один ряд, добавим к ним k–1 одинаковых разделяющих предмета. Переставим всеми возможными способами n данных различных предметов и k–1 разделяющих. Каждая такая перестановка определяет один из способов распределения. Представим , тогдав сего таких перестановок: .

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

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

Всего в s класс войдут комбинаций.

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