Лекции. Теория графов и комбинаторика (стр. 10 )

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

Теорема 2 (свойства чисел ).

1. 

2. 

3. 

4. 

5.  Числа образуют треугольник Паскаля:

	0	1	2	3	...	k
0	1
1	1	1
2	1	2	1
3	1	3	3	1
n

6. 

7.  – биноминальные коэффициенты.

8. 

9. 

10. 

11. 

12.  (сумма усечённого k-ого столбца треугольника Паскаля).

13. 

4

7. . Преобразуем в сумму произведений. Каждое произведение содержит n множителей a или b. Нужно выбрать k скобок, из которых возьмём множитель b. Они же однозначно определяют n – k скобок, откуда берём a. Число таких скобок .

8. I способ.

Воспользуемся формулой 7 при a = b = 1 .

II способ.

– число всех подмножеств n-множества.

– число k-подмножеств n-множества.

.

9. В формуле Бинома положим a = 1, b = –1 .

10.

11. .

12. .3

Теорема 3.

.

4Универсальное множество . Рассмотрим выборку G объёма k: .

Поставим G в соответствие вектор число вхождений в выборку G.

Положим , т. е. установим соответствие .

Число выборок G равно числу таких векторов y, что

.

Число таких векторов y равно количеству разбиений числа n+k в сумму n натуральными слагаемых .

Изобразим число в виде m точек на 1 строке. n+k точек надо разбить на n групп точек палочками. Палочки можно ставить в промежутках между этими точками. Промежутков n+k–1. На эти промежутки надо поставить n – 1 палочку. способов. 3

Пример.

Лекция № 13.

ПРОИЗВОДЯЩИЕ ФУНКЦИИ.

Определение 1.

Рассмотрим последовательность комбинаторных чисел и рассмотрим формальный степенной ряд . Этот ряд называется производящей функцией для последовательности а.

Пример.

Последовательность

Свойства производящих функций:

1.  Линейность.

Если , то

2.  Сдвиг влево на m элементов.

3.  Сдвиг последовательности вправо на m элементов.

4.  Дифференцирование и интегрирование производящих функций.

Если , то

Рассмотрим производящие функции для часто встречающихся последовательностей:

1.

2.

I способ.

II способ.

3.

Интегрируем 2й пример

4. по свойству 1.

Метод построения производящей функции для числа сочетаний с заданной спецификацией .

– число вхождений элементов типа в сочетание.

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

2. 

3.  – коэффициент при в разложении .