Лекции Просолупов

§21. Связь мультимножеств и (0,1)-векторов

Можно привести другое доказательство утверждения 20.5, используя связь мультимножеств с (0,1)-векторами. Как мы помним из пункта , каждому (0,1)-вектору из элементов с ровно

единицами однозначно соответствует некоторое сочетание из элементов по .

Каждому мультимножеству мощности на -элементном множестве = { 1, 2, ..., } можно поставить в соответствие такой (0,1)-вектор длины + − 1 из нулей и − 1 единицы, что число

нулей, находящихся между −1-й и -й единицами, будет равно числу вхождений в мультимножество элемента , 2 ≤ ≤ − 1; число нулей перед первой единицей равно числу вхождений в

соответствует сочетание из + − 1 по − 1 и в тоже время ему соответствует мультимножество мощности на -элементном множестве. Следовательно, мы установили взаимно-однозначное

§22. Мультиномиальная формула Ньютона

..., ),

1+ 2+...+ = ,N0, =1,

Доказательство. Докажем по индукции. Для = 2 утверждение верно в силу формулы бинома Ньютона (7′). Действительно,

41

Что и требовалось доказать.

1+ 2+...+ = ,N0, =1,

Доказательство. Следует из утверждения 22.1 при подстановке = 1, = 1, .

§23. Разбиения множеств.

Рассмотрим комбинаторный смысл мультиномиальных коэффициентов. Пусть= { 1, 2, ..., } — произвольное множество из элементов. Рассмотрим такие

разбиения множества на подмножества 1, 2, ..., , что каждое содержит элементов. Очевидно, что = 1 + 2 + ... + . Отметим, что некоторые могут быть пустыми, если соответствующее = 0.

42

( )

Доказательство. Выберем элементы для множества 1. Это можно сделать 1

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

имеется коробок: 1, 2, ..., . Сколькими способами можно разложить эти шаров по коробкам таким образом, чтобы в коробке оказалось ровно шаров,

Замечание 23.3 . Следствие 22.2 к утверждению 22.1 показывает, что число упорядоченных разбиений множества из элементов на подмножеств (включая подмножества нулевой мощности) равно .

( )

Итак, в комбинаторном смысле мультиномиальный коэффициент 1, 2,..., равен числу упорядоченных разбиений -элементного множества на подмножеств

мощностей 1, 2, ..., соответственно.

Пример 23.4 . В студенческой группе, состоящей из 25 человек, при выборе профорга за выбранную кандидатуру проголосовало 12 человек, против — 10, воздержалось — 3. Сколькими способами могло быть проведено такое голосование?

Пусть — множество студентов группы, 1 — множество студентов, проголосовавших за выдвинутую кандидатуру, 2 — множество проголосовавших против, 3 — множество воздержавшихся. Тогда | | = 25, | 1| = 12, | 2| = 10,

| 3| = 3, = 1 2 3, ∩ = ?, ̸= . Следовательно, искомое число равно

43

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

Пусть дано множество мощности и числа 1, 2, ..., таковы, что

среди множеств разбиения ровно

причем порядок множеств разбиения не важен. Обозначим число таких разбиений за ( 1, 2, ..., ).

Утверждение 23.5 . Пусть N и 1, 2, ..., N0 — такие числа, что

∑

· = .

=1

Тогда

!

( 1, 2, ..., ) = 1! 2! · · · !(1!) 1 (2!) 2 · · · ( !) .

Доказательство. Каждое неупорядоченное разбиение, заданное числами1, ..., в условиях выше, можно упорядочить, расставив подмножества по возрастанию мощности и как-нибудь упорядочив подмножества одинаковой мощности. Подсчитаем, сколькими способами это можно сделать.

Множества мощности 1 можно расставить 1! способами, множества мощности 2

— 2! способами, и так далее до множеств мощности . Таким образом, каждому неупорядоченному разбиению из условий этого утверждения можно однозначно сопоставить набор из 1! 2! · ... · ! упорядоченных разбиений в смысле условий утверждения 23.1, заданных вектором

( 1, ..., ) неупорядоченных сопоставлены ровно 1! 2! · ... · ! упорядоченных разбиений из утверждения 23.1. То есть упорядоченных разбиений в 1! 2! · ... · ! раз больше и можно записать

!

( 1, 2, ..., ) · 1! 2! · ... · ! = (1!) 1 , (2!) 2 , ..., ( !) ,

или

!

( 1, 2, ..., ) = (1!) 1 , (2!) 2 , ..., ( !) · 1! 2! · ... · !.

Пример 23.6 . Сколькими способами можно разбить множество из десяти элементов на четыре подмножества (порядок подмножеств не важен), чтобы

44

в одном из подмножеств был один элемент, в двух — по два элемента и в одном

— пять элементов? Ответ:

Пример 23.7 . Сколькими способами из группы в 20 человек можно сформировать 4 коалиции по 5 человек?

Пусть множество людей в группе, — число коалиций по человек, = 1, 20.

Тогда ответ:

20!20(0, 0, 0, 0, 4, 0, ..., 0) = 4!(5!)4

45

Лекция 6. Композиция и разбиение числа, группа перестановок

§24. Композиция натурального числа

Определение 24.1 . Композицией (или разложением) числа N называется представление в виде упорядоченной суммы натуральных чисел

( 1, 2, ..., ) : = 1 + 2 + ... + , N, N.

Слагаемые, входящие в композицию, называют частями.

Пример 24.2 . Существует всего 8 различных композиций числа = 4:

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1

2 + 2

4

Обозначим ( ) — число композиций длины (композиций состоящих из частей).

−

Доказательство. Пусть ( 1, 2, ..., ) — произвольная композиция длины : =1 + 2 + ... + . Тогда

1 ≤ 1 < 1 + 2 < 1 + 2 + 3 < ... < 1 + 2 + ... + −1 ≤ − 1.

Обозначим = 1 + 2 + ... + , 1 ≤ ≤ − 1. Тогда { 1, ..., −1} {1, ..., − 1}, причем никакие два и не совпадают. Значит, { 1, ..., −1} — некоторая выборка −1 элемента из −1. При этом различным композициям длины будут

соответствовать разные выборки из − 1 по − 1. Следовательно, ( ) ≤ ( −−11). Пусть теперь { 1, ..., −1} произвольная выборка мощности −1 из −1. Пусть,

для определенности, 1 < 2 < ... < −1. Тогда,

1 + ( 2 − 1) + ( 3 − 2) + · · · + ( −1 − −2) + ( − −1) = .

46

Обозначим 1 = 1, = − −1 и = − −1, = 2, − 1. Тогда, = 1+ 2+· · ·+

— композиция числа длины . Причем разным выборкам будут соответствовать различные композиции и, следовательно, ( ) ≥ ( −−11).

Таким образом, ( ) = ( −1).

−1

Следствие 24.4 . Рассмотрим уравнение

1 + 2 + · · · + = , (*)

где — заданное число из N0. Пусть, =( , ) — число решений этого уравнения на неотрицательных целых числах ( N0). Тогда

набор {( 1 − 1), ( 2 − 1), ..., ( − 1)} является решением уравнения (*).

То есть, мы построили взаимно-однозначное соответствие между множеством решений уравнения и множеством композиций + на слагаемых. Следовательно,

по утверждению 24.3,

Доказательство. Пусть 1 + 2 + · · · + ≤ , N0. Тогда обозначим +1 =− 1 + 2 + · · · + . { 1, 2, ..., , +1} — решение уравнения

1 + 2 + · · · + + +1 = .

47

Обратно, для любого решения 1, 2, ..., , +1 уравнения 1 + 2 +· · ·+ + +1 =верно, что 1 + 2 + · · · + ≤ .

Таким образом, множеству решений неравенства (**) взаимооднозначно соответствует множество решений уравнения 1 + 2 + · · · + + +1 = . Тогда по

§25. Разбиения натурального числа

Определение 25.1 . Набор ( 1, 2, ..., ), N, называется разбиением числа

N, если = 1 + 2 + · · · + , 1 ≥ 2 ≥ · · · ≥ > 0

Пример 25.2 . Существует 5 различных разбиений числа = 4:

1 + 1 + 1 + 1

2 + 1 + 1

2 + 2

3 + 1

4

Замечание 25.3 . Можно использовать и другое определение разбиения натурального числа:

Определение 25.4 . Разбиением числа N называется представление в виде неупорядоченной суммы натуральных чисел.

Действительно, можно считать, что разбиение { 1, 2, ..., } — такой произвольный неупорядоченный набор, что = 1 + 2 + · · · + . Тогда,

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

Чтобы получить возможность определять, имеем ли мы дело с двумя различными разбиениями, или с одним и тем же набором, но с элементами,

следующими в другом порядке, удобно договориться расставлять элементы по

убыванию. В таком случае, любому разбиению будет однозначно соответствовать упорядоченная последовательность, удовлетворяющая определению 25.1.

Обозначим ( ) — число разбиений на частей.

Утверждение 25.5 . Пусть , N, > 1 и > . Тогда

48

Доказательство. Пусть

( ) = {( 1, 2, ..., ) | = 1 + 2 + · · · + ,

1 ≥ 2 ≥ · · · ≥ > 0, N, = 1, },

= {( 1, 2, ..., ) | ( 1, 2, ..., ) ( ), = 1},

= {( 1, 2, ..., ) | ( 1, 2, ..., ) ( ), ≥ 2}.

Тогда ( ) = и ∩ = ?; | ( )| = | | + | |.

| | = |{( 1, 2, ..., −1) | 1 + 2 + · · · + −1 = − 1,

1 ≥ 2 ≥ · · · ≥ −1 > 0, N}| = | −1( − 1)| = −1( − 1).

| | = |{( 1, 2, ..., ) | 1 + 2 + · · · + = ,

1 ≥ 2 ≥ · · · ≥ > 1, N}| =

Сделаем замену = − 1, = 1, .

= |{( 1, 2, ..., ) | 1 + 2 + · · · + = − ,

1 ≥ 2 ≥ · · · ≥ > 0, N}| = | ( − )| = ( − ).

| ( )| = ( ) = −1( − 1) + ( − ).

Замечание 25.6 . Несмотря на схожесть определений, вычисление величины

( ) оказывается гораздо более сложной задачей, чем вычисление ( ). Если

для числа композиций мы имеем явную формулу (14), то для числа разбиений мы получили только рекуррентное выражение (17), которое, тем не менее, позволяет

нам вычислить ( ) для любых натуральных и , пользуясь начальными условиями: N ( ) = 1, 1( ) = 1; если > , то ( ) = 0.

Пример 25.7 . Заполним таблицу первых значений ( ), пользуясь начальными значениями и формулой (17).

49

2(3) = 1(2) + 2(1) = 1(2) = 1,2(4) = 1(3) + 2(2) = 1 + 1 = 2,3(4) = 2(3) + 3(1) = 2(3) = 1,2(5) = 1(4) + 2(3) = 1 + 1 = 2,3(5) = 2(4) + 3(2) = 2(4) = 2,4(5) = 3(4) + 4(1) = 3(4) = 1,2(6) = 1(5) + 2(4) = 1 + 2 = 3,3(6) = 2(5) + 3(3) = 2 + 1 = 3,4(6) = 3(5) + 4(2) = 2,5(6) = 4(5) + 5(1) = 1,

2(7) = 1(6) + 2(5) = 1 + 2 = 3,3(7) = 2(6) + 3(4) = 3 + 1 = 4,4(7) = 3(6) + 4(3) = 3,5(7) = 4(6) + 5(2) = 2,6(7) = 5(6) + 6(1) = 1.

§26. Понятие перестановки

Определение 26.1 . Перестановкой на множестве {1, ..., } называется инъективная функция

: {1, ..., } → {1, ..., }.

Число называется порядком перестановки .

Замечание 26.2 . Как любая инъективная на конечном множестве функция, перестановка является биективной.

Замечание 26.3 . В общем случае, перестановкой произвольного множества называют биекцию

: → .

Обозначим множество всех перестановок порядка . Очевидно, что | | = !

В записи выше первая строка всегда одинакова. Для задания перестановки достаточно второй строки

= (1) (2)... ( ).

Также можно задать перестановку перечислением ее циклов, о чем мы скажем позже.

50