13. Комбинаторные объекты и комбинаторные числа

Комбинаторный анализ занимается изучением объектов из конечного мн-ва Е = {а1,а2,…,аn}, эл-тами аi и их св-вами.

Этими объектами моб подмн-ва мн-ва Е, подмн-ва мн-ва Е с опред св-вами. Напр., с повтор-мися или упоряд. эл-тами.

Задачи типа перечислить объекты с заданными св-вами и определить их кол-во.

Мн-во всех подмн-в мн-ва Е — Сигма_n.

Сигма_3 = {пустое мн-во,{a1},{a2},{a3},{a1,a2},{a1,a3},{a2,a3},{a1,a2,a3}}.

Размещения

Размещением эл-тов из Е по к называется упорядоченное(!) подмн-во из k эл-тов, принадлежащее мн-ву Е.

(A^k)_n — число возможных размещений, к-рые -~ построить из E/

----------

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

с повторениями U(m,n) = m^n.

---------

(A^k)_n = n!/(n-k)!

----------

(A^k)_n = 0 при k > n;

(A^0)_n = (A^0)_0 = 1.

----------

Существуют рекуррентные соотношения:

(A^k)_n = n*(A^(k-1))_(n-1);

(A^k)_n = (A^(k-1))_n * (n-k+1);

[/доказать по св-вам факториала\]

Перестановки

Перестановки — частный случай размещения эл-тов из мн-ва E.

Перестановки — упорядоченные подмн-ва из n эл-тов мн-ва Е = {a1,a2,…,an}.

Pn — число перестановок из мн-ва Е

Pn = (A^n)_n = n!

Сочетания

Сочетание из мн-ва Е по k называется неупорядоченное подмн-во из k эл-тов, принадлежащих мн-ву Е.

(C^k)_n = n!/(k!(n-k)!)

[/т.к. k! повторений, это легко понять\]

--------

В записи (C^k)_n C -~ опускать, в скобках пишут n сверху, а k — снизу.

(0,0) = (n,0) = (n,n) = 1;

(n,k) = (n,n-k);

(n,i)*(i,r) = (n,r)*(n-r,i-r) при 0<=r<=i<=n;

(n,k) = (n-1,k) + (n-1,k-1);

(n,k) = 0 при k > n.

[/доказать по св-вам факториала\]

[/Построить таблицу (n,k), юзая треугольние Паскаля\]

--------

Бином Ньютона

(1+x)^n = SUM[k=0..n]((C^k)_n * x^k);

(a+b)^n = SUM[k=0..n]((C^k)_n * a^k * b^(n-k));

--------

Сочетания с повторениями из A по k — неупорядоченный набор из k эл-тов, в к-ром эл-ты -~ повторяться и любой эл-т сочетания встречается в A.

(H^k)_n = (C^k)_(n+k-1).

-P:

Пусть a’ — произвольное сочетание с повторяющимися эл-тами из A по k эл-тов. Данному сочетанию поставим в соответствие набор 0 и 1 длины n+k-1. Длина — число 0 и 1, заданных в наборе. Набор содержит n-1 нулей и k единиц.

В данном наборе нули отделяют единицы, число к-рых указывает, сколько эл-тов ai входит в сочетание a’.

Данное соответствие му сочетаниями с повторениями и наборами a’ взаимно однозначно, но число взаимных наборов длины n+k-1, содержащих n-1 нулей и k единиц = числу сочетаний (C^k)_(n+k-1).

Стирлинга II

E={a1,a2,..,an}.

|E|=n, n>0.

K — число разбиений мн-ва Е на непустые подмн-ва.

Ф(n,k) — число разбиений мн-ва Е на k непустых частей (0<k<=n).

Ф(n,k) — числа Стирлинга II-го рода.

--------

Ф(4,2) = 7:

{1,2,3}{4}

{1,2,4}{3}

{1,3,4}{2}

{2,3,4}{1}

{1,2}{3,4}

{1,3}{2,4}

{1,4}{2,3}

--------

Ф(0,0)=1

Ф(n,0)=0 при n>0

Ф(n,n)=1

Ф(n,k)=0 при k>n

--------

Ф(n,k) = Ф(n-1,k-1) + k*Ф(n-1,k),

0<k<n

1) Ф(n-1,k-1) — те, которые получаются, когда k-ый элемент состоит в отдельном мн-ве;

2) + k*Ф(n-1,k), т.к. -~ добавить k-ый элемент поочерёдно во все блоки мн-ва {1,2,..n-1}, к-рое нужно разбить на k блоков.

--------

Рассмотрим мн-во многочленов вида

1,х,x^2,…,x^k.

Pk(x) = SUM(i=0..k)(ai*x^i).

{x^i} — базис в пр-ве многочленов.

1,x,x(x-1),x(x-1)(x-2),…,x(x-1)*…*(x-k+1).

[x]_i = x(x-1)*…*(x-i+1).

{[x]_i} — базис в пр-ве многочленов.

Pk(x) = SUM(i=0..k)(ai*x^i).

Pk(x) = SUM(i=0..k)(ci*[x]_i).

x^n = SUM(k=0..n)(Ф(n,k) * [x]_k)

Стирлинга I

-~ поставить обратную задачу. Разложить элемент [x]n на SUM(k=0..n)(C_k * x^k)

[x]_n = SUM(k=0..n)(C_k * x^k)

C_k - числа Стирлинга I рода.

[x]_n = SUM(k=0..n)( фи(n,k) * x^k )

фи(n,k) — обозначение чисел Стирлинга I рода.