Решить уравнение относительно m сочетания без повторений. Формулы комбинаторики. Размещения с повторением

Подсчитаем в MS EXCEL количество сочетаний из n элементов по k. С помощью формул выведем на лист все варианты сочетаний (английский перевод термина: Combinations without repetition).

Сочетаниями из n различных элементов по k элементов называются комбинации, которые отличаются хотя бы одним элементом. Например, ниже перечислены ВСЕ 3-х элементные сочетания, взятые из множества, состоящего из 5 элементов {1; 2; 3; 4; 5}:

(1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5)

Примечание : Это статья о подсчете количества сочетаний с использованием MS EXCEL. Теоретические основы советуем прочитать в специализированном учебнике. Изучать сочетания по этой статье - плохая идея.

Отличие Сочетаний от Размещений

Вывод всех комбинаций Сочетаний

В файле примера созданы формулы для вывода всех Сочетаний для заданных n и k.

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

Задача

Автовоз может перевозить по 4 легковые машины. Необходимо перевезти 7 разных машин (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). Сколькими различными способами можно заполнить первый автовоз? Конкретное место машины в автовозе не важно.

Нам нужно определить число Сочетаний 7 машин на 4-х местах автовоза. Т.е. n=7, а k=4. Оказывается, что таких вариантов =ЧИСЛКОМБ(7;4) равно 35.

Произвольным образом сопоставим маркам машин числовые значения и сделаем сокращения названий марок: LADA Granta (LG=1), Hyundai Solaris (HS=2), …

В этом разделе будут рассмотрены три вида соединений без повторений: размещения, перестановки и сочетания. Ради краткости добавку «без повторений» будем опускать.

1. Размещения. Размещения из n элементов по – это упорядоченные наборы из попарно различных элементов -множества . Таким образом, два размещения из элементов по различаются либо порядком, либо составом входящих в них элементов. Например, размещения из 3-множества по 2 исчерпываются следующими упорядоченными парами:

, , , , , .

Нас будет интересовать задача нахождения числа всех размещений из элементов по . В качестве первого элемента можно выбрать любой из элементов множества . После того как выбран первый элемент, второй элемент можно выбрать лишь способами (можно взять любой элемент, исключая выбранный). После выбора первых двух элементов остаются лишь возможности выбрать третий элемент и т. д. Последний -й элемент можно выбрать способами – ведь до него уже выбраны элемент, а потому осталось лишь элементов. По правилу произведения получаем, что число всевозможных упорядоченных наборов равно произведению чисел , , , …, , т.е. справедлива следующая

Т е о р е м а 1. Число размещений из элементов по находится по формуле

Напомним, что произведение первых n натуральных чисел, т.е. , называют n-факториалом и обозначают . Произведение можно записать в виде дроби = и поэтому формулу (1) можно переписать следующим образом

В частности, при из формулы (2) получаем

Это означает, что существует единственный упорядоченный набор длины 0 – пустой кортеж, не имеющий ни одной компоненты.

Пример 1. Найти число пятизначных чисел в десятичной системе счисления, в записи которых цифры не повторяются.

□ Рассуждая по аналогии с тем, как это делалось при рассмотрении примера 1 (2-й способ) из § 2, приходим к выводу, что искомое число есть .

2. Перестановки. Рассмотримтеперь различные линейные упорядочения данного -множества . Получаемые при этом упорядоченные наборы отличаются друг от друга лишь порядком входящих в них элементов. Их называют перестановками (без повторений) из n элементов, а их число обозначают через . Например, если , то = 6, так как из трех элементов можно составить шесть перестановок:

, , , , , .

Общая формула для получается из формулы (1), поскольку перестановка из элементов – это то же самое, что размещение без повторений из элементов по . Полагая в (1) получим = = = = . Итак, справедлива

Т е о р е м а 2. Число перестановок из элементов равно -факториал, т.е.

Полагая в формуле (2) , получаем

Сравнивая (3) и (4), приходим к выводу, что 0! = 1. На первый взгляд это равенство кажется парадоксальным. Но для всех справедливо равенство = . Если потребовать, чтобы это равенство было справедливо и при , то получим . Отсюда вновь следует, что естественно положить0! = 1 .

Пример 2. Сколькимиспособамиможно расположить на полке 7 различных учебников так, чтобы «Алгебра» и «Геометрия» не стояли рядом?

□ Условимся указанные учебники обозначать для краткости буквами А и Г соответственно. Число всевозможных способов расстановки учебников равно числу перестановок из семи элементов, т.е. . Но при этом сосчитаны и те, в которых встречаются рядом учебники А и Г, причем в двух позициях: АГ и ГА. Считая АГ и ГА за одну книгу, для каждого такого расположения получим расстановок, в которых учебники А и Г встречаются рядом. Искомое число расстановок учебников равно .

3. Сочетания. Одной из важнейших задач комбинаторики является подсчет числа k -подмножеств данного n -множества . Такие неупорядоченные подмножества называются сочетаниями из элементов по , а их число обозначают через (от французского слова combinaison – сочетание). Например, из элементов 4-множества можно составить следующие 2-множества: , , , , , . Число этих подмножеств равно 6. Следовательно, = 6. Отметим, что = 1, так как каждое множество имеет лишь одно 0-множество, а именно, пустое множество . Далее понятно, что = , поскольку в ‑множества содержится одноэлементных подмножеств. Ясно также, что .

Выведем формулу, выражающую через и . Для этого укажем способ получения всех размещений из элементов по . Выберем любое k -подмножество данного n -множества . Это можно сделать способами. Каждое такое k -подмножество упорядочим всевозможными способами. Таких различных упорядочений столько, сколько можно составить перестановок из элементов, т.е. = . Понятно, что таким способом получатся все размещений из элементов по . Значит, имеет место равенство = . Отсюда вытекает справедливость следующего утверждения.

Т е о р е м а 3. Число сочетаний из n элементов по k вычисляется по формуле :

= = = . (5)

Пример 3. Найти число всех диагоналей правильного n -угольника.

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

Таким образом, искомое число равно

Например, при получаем, что правильный 10-угольник имеет = 35 диагоналей.

Свойства сочетаний.

□ В самом деле, в силу формулы (5) имеем

= = = .

□ Действительно,

= = = . =

Непосредственно свойств ‑ сочетаний вытекают следующие

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N! . Действительно:

на первое место может быть помещен любой из N элементов (всего вариантов N ),
на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1) ),
если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1 , то есть всего N! перестановок.

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .

Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:

Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).
Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.
Поменять местами два полученных элемента.
Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
using namespace std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3);
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат выполнения

Перестановки с повторениями

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main() ).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат работы приведенного выше алгоритма:

КОМБИНАТОРИКА

Комбинаторика - раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В - n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

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

Решение

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Решение

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Решение

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

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение.

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Перестановки без повторений . Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Решение

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

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

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Решение

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"

НЕУПОРЯДОЧЕННЫЕ УПОРЯДОЧЕННЫЕ РАЗБИЕНИЯ С ФИКСИРОВАННЫМИ РАЗМЕРАМИ ЧАСТЕЙ

Цель: Изучить на практике методику расчета числа перестановок без повторений и с повторениями

Задание 4 () .

Задание 5 (начисло перестановок с повторениями).

Задание 6 (начисло неупорядоченных разбиений с фиксированными размерами частей) .

Задание 7 () .

Задание 4 (начисло перестановок без повторений) .

Сколько различных n n штук цифр: 1,3,5,7,9?

ЧИСЛО ПЕРЕСТАНОВОК БЕЗ ПОВТОРЕНИЙ. КРАТКАЯ ТЕОРИЯ

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

Пример. Перестановки из 3 различных элементов а, b и с: аbс, bса, саb, сbа, bас, асb.

Число всех перестановок из п различных элементов (обозначается Р п) есть Р п = 1 2 3 ... n = п ! (п ! читается "эн-факториал").

В таблице ниже приведены числовые значения факториалов первых натуральных чисел и нуля.

Таблица. Значения факториалов первых натуральных чисел и нуля.

n=
n!=

КОНЕЦ ТЕОРИИ.

Решение.

В задании 4 n =5, ибо переставляются местами всевозможными способами n =5 штук различных цифр: 1,3,5,7,9. При этом каждой новой перестановке цифр соответствует новый телефонный номер (натуральное число). Поэтому искомое число различных телефонных номеров равно числу различных перестановок без повторений из n =5 штук различных элементов.

Согласно теории, искомое число равно Р 5 = 5!= 120 различных 5– значных телефонных номеров.

Ответ: 120 различных 5– значных телефонных номеров.

Задание 5 (на число перестановок с повторениями.)

Сколько различных n – значных телефонных номеров (натуральных чисел) можно написать, переставляя следующий набор n штук цифр: 1,1,1,3,3,5?

ЧИСЛО ПЕРЕСТАНОВОК С ПОВТОРЕНИЯМИ. КРАТКАЯ ТЕОРИЯ

Перестановки с повторениями

Перестановками с повторениями из т элементов n различных типов, среди которых k 1 одинаковых элементов 1-го типа, k 2 одинаковых элементов 2-го типа, ... , k n одинаковых элементов п -го типа (k 1 + k 2 + ... + k п = m ) , называются их последовательности, отличающиеся только порядком входящих в них элементов.

Пример. Перестановки из 3 элементов, среди которых 2 одинаковых элемента типа а и 1 элемент типа b: ааb, аbа, bаа.

Число перестановок из т элементов, среди которых k 1 - одинаковых элементов 1-го типа, k 2 одинаковых элементов2-го типа,..., k п - одинаковых элементов n -го типа [обозначается Р (m ; k 1 ,k 2 ,..., k п) ] равно:

Р (m ; k 1 ,k 2 ,..., k п) = т!/ (k 1 !k 2 !... k п !).

Для примера перестановок с повторениями из 3 элементов, среди которых 2 одинаковых типа а и 1 элемент типа b, имеем Р (m=3 ; k 1 =2,k 2 =1) = 3!/ (2 !1!).

КОНЕЦ ТЕОРИИ.

Решение.

В задание 5 m =6, ибо переставляются местами всевозможными способами m =6 штук различных цифр: 1,1,1,3,3,5, среди которых есть повторяющиеся (одинаковые). При этом каждой новой перестановке цифр соответствует новый телефонный номер (натуральное число). Поэтому искомое число различных телефонных номеров равно числу различных перестановок с повторениями из m =6 штук элементов, среди которых k 1 =3 одинаковых элементов 1-го типа (цифра 1), k 2 =2 одинаковых элементов2-го типа (цифра 3), k 3 =1одинаковых элементов 3 -го типа (цифра 5), равно Р (m ; k 1 ,k 2 ,..., k п) = т!/ (k 1 !k 2 !... k п !), Р (6; 3, 2, 1) = 6!/(3! 2! 1!)= =60.

Ответ: Р (6; 3, 2, 1) = 60, т. е 60 различных вариантов 6– значных телефонных номеров (6-значных чисел), содержащих цифру 1 трижды, 3 -дважды и 5 - один раз.

Задание 6 (на число неупорядоченных разбиений с фиксированными размерами частей) .

Сколько всего вариантов можно получить, разбивая группу из пяти человек (из пяти солдат) на три подгруппы - две подгруппы по два человека (по два автоматчики) и одна подгруппа из одного человека (из одного пулеметчика)?

НЕУПОРЯДОЧЕННЫЕ РАЗБИЕНИЯ. КРАТКАЯ ТЕОРИЯ

Неупорядоченное разбиение n -элементного множества X - это любое семейство {X 1 , X 2 ,…, X k }, где 1≤k≤п; X 1 , X 2 ,…, X k - непустые попарно непересекающиеся подмножества множества X , объединение которых равноX.

Называем такое разбиение неупорядоченным, так как семейство - это неупорядоченная совокупность.

Пример. Для множества {а,b,с} неупорядоченное разбиение это, например, {{а},{b,с}}. Причем {{а},{b,с}}={{b,с},{а}}.

Для множества с п элементами обозначим через D (n ; k 1 , k 2 ,…, k n) число всех таких неупорядоченных разбиений, в которых есть k 1 подмножеств с одним элементом, k 2 подмножеств с двумя элементами и т.д., где k 1 ≥0, k 2 ≥0,…, k n ≥0; k 1 +2 k 2 +…+n k n = n.

КОНЕЦ ТЕОРИИ.

Решение.

Каждый вариант- это неупорядоченное разбиение { Иванов, Петров, Сидоров, Андреев, Борисов }. Множество из 5 элементов Один из вариантов разбиения {{Иванов, Петров}, {Сидоров, Андреев}, {Борисов}}

Имеем п = 5, k 1 =1, k 2 =2, k 3 =0, k 4 =0, k 5 =0 (так как по условию нет подгрупп из трех, четырех, пяти человек).

Ответ: 15 вариантов.

Задание 7 (начисло упорядоченных разбиений с фиксированными размерами частей) .

Сколькими способами можно выбрать из десяти солдат трех пулеметчиков, трех гранатометчиков и четырех автоматчиков (3 пулеметчика 3 гранатометчика 4 автоматчика, всего 10 солдат)?

УПОРЯДОЧЕННЫЕ РАЗБИЕНИЯ. КРАТКАЯ ТЕОРИЯ

Упорядоченным разбиением конечного множества X с n элементами называется любой кортеж вида <X 1 , X 2 ,…, X k >, где 1 ≤k ≤n ; X 1 , X 2 ,…, X k - непустые попарно непересекающиеся, подмножества множества X, объединение которых равно X.

Называем такое разбиение упорядоченным , так как элементы кортежа упорядочены.

Пример. Для множества {а,b,с} упорядоченное разбиение это, например, кортеж <{{а},{b,с}} >. Причем <{{а},{b,с}}> ¹<{{b,с},{а}} >.

Для множества с п элементами обозначим через E (n ; m 1 , m 2 ,…, m k ,) число всех таких упорядоченных разбиений на подмножества X 1 , X 2 ,…, X k , содержащие m 1 , m 2 ,…, m k , где m 1 ≥0, m 2 ≥0,…, m k ≥0; m 1 + m 2 +…+ m k = n.

Число всех упорядоченных разбиений <X 1 , X 2 ,…, X k > множества с п элементами на подмножества X 1 , X 2 ,…, X k , содержащие m 1 , m 2 ,…, m k , элементов соответственно. определяется по полиномиальной формуле

где m 1 ≥1, m 2 ≥1,…, m n ≥1; m 1 + m 2 +…+m k = n.

КОНЕЦ ТЕОРИИ.

Решение.

В задании имеем упорядоченное разбиение < X 1 , X 2 , X 3 > множества с десятью элементами, где X 1 - подмножество пулеметчиков, Х 2 - подмножество гранатометчиков, Х 3 - подмножество автоматчиков;

поэтому п = 10, m 1 = 3, т 2 , = 3, т 3 = 4.

Тогда всего есть

Ответ: 4200 вариантов