Просолупов Е.В. Конспект курса: Основы дискретной математики

Подождите немного. Документ загружается.

Следовательно, выполняется выражение (*).

Таким образом установлено взаимнооднозначное соответствие между

множеством сочетаний из n + k − 1 по k и множеством мультимножеств

мощности k над множеством из n элементов. Следовательно мощности

этих множеств равны.

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

Можно привести другое доказательство утверждения 1.5.9, используя

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

каждому (0,1)-вектору из n элементов с ровно k единицами однозначно

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

Каждому мультимножеству мощности k на n-элементном множестве

S = {s

, s

, ..., s

} можно поставить в соответствие (0,1)-вектор длины

n + k − 1 из k нулей и n − 1 единицы, такой что число нулей,

находящихся между i−1-й и i-й единицами, будет равно числу вхождений

в мультимножество элемента s

, 2 ≤ i ≤ n − 1; число нулей перед

первой единицей равно числу вхождений в мультимножество элемента

; число нулей после n − 1-й единицы равно числу вхождений в

мультимножество элемента s

. Это соответствие между множеством

¡¡

¢¢

и множеством (0,1)-векторов длины n + k − 1 c n − 1-й единицей

является взаимнооднозначным.

Таким образом, каждому (0,1)-вектору длины n + k − 1 с n −

1-й единицей однозначно соответствует сочетание из n + k − 1 по

n − 1 и в тоже время ему соответствует мультимножество мощности

k на n-элементном множестве. Следовательно, мы установили

взаимнооднозначное соответствие между множеством всех сочетаний из

n + k − 1 по n − 1 и множеством всех мультимножеств мощности k

на n-элементном множестве. Значит,

n+k−1

n−1

¡¡

¢¢

, что и

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

1.5.8 Полином Ньютона

Утверждение 1.5.10 .

+ x

+ ... + x

)

(α

,...,α

+α

+...+α

=m,

∈N

, i=1,k

!α

!...α

...x

. (14)

Доказательство. Докажем по индукции. Для k = 2 утверждение верно

в силу формулы бинома Ньютона (8

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

(α

,α

+α

=n,

,α

∈N

!α

k∈{0,...,n},

=k,

=n−k

k=0

n−k

= (a + b)

Пусть утверждение верно для всех k ≤ K для любых m.

Пусть теперь k = K + 1.

+ x

+ ... + x

+ x

K+1

)

= ((x

+ ... + x

) + x

K+1

)

по индукционному предположению

α+β=m,

α,β∈N

α!β!

+ ... + x

)

K+1

α+β=m,

α,β∈N

α!β!

K+1

(α

,...,α

+α

+...+α

=α,

∈N

, i=1,K

α!

!α

!...α

...x

(α

,...,α

,β),

+α

+...+α

+β=m,

∈N

, i=1,K, β∈N

!α

!...α

!β!

...x

K+1

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

Благодаря формуле (14) числа

!α

!...α

при α

+ α

+ ... + α

= m,

∈ N

, i = 1, k, m ∈ N

, получили название мультиномиальных

коэффициентов. Обычно их обозначают

, α

, ..., α

В этих обозначениях биномиальные коэффициенты имеют вид

k, n − k

Легко доказать следующее свойство мультиномиальных

коэффициентов:

Утверждение 1.5.11 . Пусть m ∈ N

(α

,...,α

+α

+...+α

=m,

∈N

, i=1,k

, α

, ..., α

= k

Доказательство. Следует из утверждения 1.5.10 при подстановке x

1, i = 1, k.

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

Рассмотрим комбинаторный смысл мультиномиальных коэффициентов.

Рассмотрим множество S = {s

, s

, ..., s

}. Пусть разбиение множества

S на множеста S

, S

, ..., S

таково, что каждое S

содержит α

элементов:

S = S

∪ S

∪ ... ∪ S

; S

∩ S

= ∅, i 6= j; |S

| = α

, i = 1, k.

Отметим, что некоторые S

могут быть пустыми и, очевидно, что m =

+ α

+ ... + α

Утверждение 1.5.12 . Число таких разбиений множества S равно

мультиномиальному коэффициенту

,α

,...,α

Пример 1.5.9 . Пусть имеется m шаров с различными номерами на

них и имеется k коробок: B

, B

, ..., B

. Сколькими способами можно

разложить эти m шаров по k коробкам таким образом, чтобы в коробке

оказалось ровно α

шаров, i = 1, k.

Для начала можем выбрать α

шаров, которые мы положим в

коробку B

. Это можно сделать столькими различными способами,

сколько существует сочетаний из m по α

—

Аналогично, α

шаров, которые мы положим в коробку B

можно

выбрать

m−α

способами.

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

которыми можно разложить все m шаров по k коробкам с соблюдением

количеств шаров в коробках равно

m − α

− α

· ... ·

m − α

− ... − α

k−1

!(m − α

(m − α

!(m − α

− α

(m − α

− α

!(m − α

− α

· · · ·

(m − α

− α

− ... − α

k−1

!(m − α

− α

− ... − α

k−1

− α

!α

!...α

, α

, ..., α

Замечание 1.5.2 . В примере 1.5.9 содержится докозательство

утверждения 1.5.12. Действительно, выбрать α

элементов из m

для первого подмножества можно

способами, α

из оставшихся

элементов для второго подмножества —

m−α

способами и так далее.

Итак, в комбинаторном смысле мультиномиальный коэффициент

,α

,...,α

равен числу разбиений m-элементного множества на k

подмножеств мощностей α

, α

, ..., α

Пример 1.5.10 . В студенческой группе, состоящей из 25 человек, при

выборе профорга за выбранную кандидатуру проголосовало 12 человек,

против — 10, воздержалось — 3. Сколькими способами могло быть

проведено такое голосование?

Пусть S — множество студентов группы, S

— множество

студентов проголосовавших за выдвинутую кандидатуру, S

— множество проголосовавших против, S

— множество

воздержавшихся. Тогда |S| = 25, |S

| = 12, |S

| = 10, |S

| = 3,

S = S

∪ S

, S

∩ S

= ∅, i 6= j.

Следовательно искомое число равно

12, 10, 3

25!

12!10!3!

= 1 487 285 800.

Тепеь рассмотрим, как можно подсчитать число неупорядоченных

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

Пусть дано множество S мощности m и числа n

, n

, ..., n

таковы,

что

i=1

· i = m. Рассмотрим такие разбиения множества S

на подмножества, что среди множеств разбиения ровно n

множеств

мощности i, для каждого i = 1, m, причем порядок множеств разбиения

не важен. Обозначим число таких разбиений за N(n

, n

, ..., n

Утверждение 1.5.13 . Пусть m ∈ N и n

, n

, ..., n

∈ N

— такие

числа, что что

i=1

· i = m.

Тогда

N(n

, n

, ..., n

) =

! · · · n

!(1!)

(2!)

· · · (m!)

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

рассмотренных при определении величины N(n

, ..., n

), можно,

нумеруя множества в этом разбиении, привести n

! · · · n

! способами

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

можно расставить n

! способами, множества мощности 2 — n

! способами,

..., множества мощности m — n

! способами. С другой стороны,

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

утверждению 1.5.12. Тогда получим

(1!)

, (2!)

, ..., (m!)

= N(n

, n

, ..., n

) · n

! · · · n

что и доказывает утверждение.

Пример 1.5.11 . Сколькими способами можно разбить множество

из десяти элементов на четыре подмножества (порядок подмножеств

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

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

N(1, 2, 0, 0, 1, 0, 0) =

10!

1!2!1!(1!)

(2!)

(5!)

2 · 4 · 5!

= 3780

Пример 1.5.12 . Сколькими способами из группы в 20 человек можно

сформировать 4 каолиции по 5 человек?

Пусть S множество людей в группе, n

— число каолиций по i человек,

i = 1, 25. Тогда ответ:

N(0, 0, 0, 0, 4, 0, ..., 0) =

20!

4!(5!)

1.5.10 Приложение: программа перебора сочетаний

Приведем код программы, которая перебирает все (0,1)-вектора длины n

с k единицами (а значит все сочетания из n по k).

#include<iostream.h>

const

n=7,

m=4;

void main()

{

cout << "Перебор сочетаний из " << n << " по " << m << ":"

<< endl << endl ;

int i,j,k;

int x[m];// Вектор номеров позиций единиц

int c[n];// (0,1)-вектор текущего сочетания.

// Вспомогательный массив для вывода на печать.

// Исходная инициализация

for(i=0;i<m;i++)

x[i]=i;

///////////////////////////////

// Стандартный шаг алгоритма //

do {

////////////////////

// Вывод на экран //

// Инициализируем массив c[]

for(i=0; i<n; i++)

c[i]=0;

for(i=0; i<m; i++)

c[x[i]]=1;

// Выведем его на экран

for(i=0; i<n; i++)

cout << c[i];

cout << endl;

/////////////////////////////////////////

// Очередной шаг модификации сочетания //

k=m-1; // номер позиции самой последней единицы,

// которую можно сдвинуть.

while( (k>=0) && (x[k]==n-m+k) )

k--;

///////////////////////////////

// Если позиция k существует //

if(k>=0)

{

// Увеличиваем номер позиции k-той единицы

// и выстраиваем все следующие единицы за ней

x[k]++;

for(i=k+1; i<m; i++)

x[i]=x[k]+(i-k);

}

while(k>=0);

}

Результатом работы будут все возможные (0,1)-вектора длины семь с

четырьмя единицами:

1111000

1110100

1110010

1110001

1101100

1101010

1101001

1100110

1100101

1100011

1011100

1011010

1011001

1010110

1010101

1010011

1001110

1001101

1001011

1000111

0111100

0111010

0111001

0110110

0110101

0110011

0101110

0101101

0101011

0100111

0011110

0011101

0011011

0010111

0001111

Замечание 1.5.3 . Покскольку, как показано в параграфе 1.5.7,

существует взаимнооднозначное соответствие между (0,1)-

векторами и мультимножествами, приведенную программу легко

представить и как программу перебора мультимножеств.

1.6 Разложения и разбиения натуральных чисел

1.6.1 Разложения натуральных чисел

Определение 1.6.1 . Разложением числа n ∈ N называется

представление n в виде упорядоченной суммы натуральных чисел

, a

, ..., a

) : n = a

+ a

+ ... + a

, a

∈ N.

Пример 1.6.1 . Существует всего 8 различных разложений числа n =

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1

2 + 2

Обозначим d

(n) — число разложений n на k частей.

Утверждение 1.6.1 . Число разложений n на k частей равно

(n) =

n − 1

k − 1

. (15)

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

, a

, ..., a

) — произвольное разложение n на

k частей: n = a

+ a

+ ... + a

. Тогда

1 ≤ a

< a

+ a

< a

+ a

< ... < a

+ a

+ ... + a

k−1

≤ n − 1.

Обозначим b

= a

+ a

+ ... + a

, 1 ≤ i ≤ k − 1. Тогда {b

, ..., b

k−1

} ⊂

{1, ..., n−1}, причем никакие два b

и b

не совпадают. Значит {b

, ..., b

k−1

}

— некоторая выборка k − 1 элемента из n − 1. При этом, различным

разложениям n на k частей будут соответствовать разные выборки из

n − 1 по k − 1. Следовательно, d

(n) ≤

n−1

k−1

Пусть теперь, {b

, ..., b

k−1

} произвольная выборка мощности k − 1 из

n − 1. Пусть, для определенности, b

< b

< ... < b

k−1

. Тогда,

+ (b

− b

) + (b

− b

) + · · · + (b

k−1

− b

k−2

) + (n − b

k−1

) = n.

Обозначим a

= b

, a

= n − b

k−1

и a

= b

− b

i−1

, i = 2, k − 1. Тогда, n =

+ a

+ · · · + a

— разложение n на k частей. Причем разным выборкам

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

(n) ≥

n−1

k−1

Таким образом, d

(n) =

n−1

k−1

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

+ x

+ · · · + x

= n, (∗)

где n — заданное число из N

. Пусть, N

(n, k) — число решений этого

уравнения на неотрицательных целых числах (x

∈ N

). Тогда

(n, k) =

n + k − 1

k − 1

. (16)

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

+ c

+ · · · + c

, c

∈ N

. Тогда n + k =

+ 1) +(c

+ 1) + · · · + (c

+ 1), c

∈ N. Таким образом, любому решению

уравнения (*) соответствует разложение n + k на k частей. И наоборот,

для любого разложения

n = a

+ a

+ ... + a

, a

∈ N

набор {(a

− 1), (a

− 1), ..., (a

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

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

множеством решений уравнеия и множеством разложений n + k на k

слогаемых. Следовательно, по утверждению 1.6.1

(n, k) = d

(n + k) =

n + k − 1

k − 1