Сочетание

Разделы:

В комбинаторике сочетанием из n{displaystyle n} $n$ по k{displaystyle k} $k$ называется набор k{displaystyle k} $k$ элементов, выбранных из данного множества, содержащего n{displaystyle n} $n$ различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

К примеру набор из трёх-элементного созвучия

3n по k=1 {TAR} = 3, состоит из 3ёх звуков , имеет в себе комбинации 6ть групп элементов разложений или отслоений,

по k=2 {TAR + (TA. + .AR) + (T.. + .A. + ..R) } = 6=3+!2соответствует трёх-значному треугольнику из шаров , где группы шести элементов с учётом общего количества количеств имеют в себе 10ть единичных элементов

по k=3 {3*1 + 2*2 + 1*3} =10=3+!3 трёх-значный тетраэдр.

К примеру набор пяти-элементного созвучия

5n при k=1 {ENTAR} = 5, состоит из 5ти звуков и имеет в себе комбинации 15ть групп элементов разложений или отслоений,

по k=2 {ENTAR + (ENTA. + .NTAR) + (ENT.. + .NTA. + ..TAR) + (EN… + .NT.. + ..TA. + …AR) + (E…. + .N… + ..T.. + …A. + ….R)} = 15=5+!2 это равносильно пяти-значному треугольнику из шаров , где группы 15ти элементов при подсчёте имеют в себе 35ть единичных элементов,

по k=3 {5*1 + 4*2 + 3*3 + 2*4 + 1*5} =35=5+!3 трёх-значный тетраэдр. , (до конца не обдумал)

Так, например, наборы (3-элементные сочетания, подмножества, k=3{displaystyle k=3} $k=3$ ) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} (n=6{displaystyle n=6} $n=6$ ) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать k{displaystyle k} $k$ элементов из множества, содержащего n{displaystyle n} $n$ различных элементов, стоит на пересечении k{displaystyle k} $k$ -й диагонали и n{displaystyle n} $n$ -й строки треугольника Паскаля.[1]

Содержание

1 Число сочетаний
2 Сочетания с повторениями
3 См. также
4 Примечания
5 Ссылки

Число сочетаний

Основная статья: Биномиальный коэффициент

Число сочетаний из n{displaystyle n}

$n$ по k{displaystyle k} $k$ равно биномиальному коэффициенту

(nk)=Cnk=n!k!(n−k)!.{displaystyle {n choose k}=C_{n}^{k}={frac {n!}{k!left(n-kright)!}}.}

{n choose k}=C_{n}^{k}={frac {n!}{k!left(n-kright)!}}.

При фиксированном n{displaystyle n}

$n$ производящей функцией последовательности чисел сочетаний (n0){displaystyle {tbinom {n}{0}}} ${tbinom {n}{0}}$ , (n1){displaystyle {tbinom {n}{1}}} ${tbinom {n}{1}}$ , (n2){displaystyle {tbinom {n}{2}}} ${tbinom {n}{2}}$ , … является:

∑k=0n(nk)xk=(1+x)n.{displaystyle sum _{k=0}^{n}{binom {n}{k}}x^{k}=(1+x)^{n}.}

sum _{k=0}^{n}{binom {n}{k}}x^{k}=(1+x)^{n}.

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

∑n=0∞∑k=0n(nk)xkyn=∑n=0∞(1+x)nyn=11−y−xy.{displaystyle sum _{n=0}^{infty }sum _{k=0}^{n}{binom {n}{k}}x^{k}y^{n}=sum _{n=0}^{infty }(1+x)^{n}y^{n}={frac {1}{1-y-xy}}.}

sum _{n=0}^{infty }sum _{k=0}^{n}{binom {n}{k}}x^{k}y^{n}=sum _{n=0}^{infty }(1+x)^{n}y^{n}={frac {1}{1-y-xy}}.

Сочетания с повторениями

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

Число сочетаний с повторениями из n{displaystyle n}

$n$ по k{displaystyle k} $k$ равно биномиальному коэффициенту

(n+k−1n−1)=(n+k−1k)=(−1)k(−nk)=(n+k−1)!k!⋅(n−1)!.{displaystyle {binom {n+k-1}{n-1}}={binom {n+k-1}{k}}=(-1)^{k}{binom {-n}{k}}={frac {(n+k-1)!}{k!cdot (n-1)!}}.}

{binom {n+k-1}{n-1}}={binom {n+k-1}{k}}=(-1)^{k}{binom {-n}{k}}={frac {(n+k-1)!}{k!cdot (n-1)!}}.

Доказательство

Пусть имеется n{displaystyle n}

$n$ типов объектов, причём объекты одного типа неотличимы. Пусть имеется неограниченное (или достаточно большое, во всяком случае, не меньше k{displaystyle k} $k$ ) количество объектов каждого типа. Из этого ассортимента выберем k{displaystyle k} $k$ объектов; в выборке могут встречаться объекты одного типа, порядок выбора не имеет значения. Обозначим через xj{displaystyle x_{j}} $x_{j}$ количество выбранных объектов j{displaystyle j} $j$ -го типа, xj≥0{displaystyle x_{j}geq 0} $x_{j}geq 0$ , j=1,2,…,n{displaystyle j=1,2,dots ,n} $j=1,2,dots ,n$ . Тогда x1+x2+⋯+xn=k{displaystyle x_{1}+x_{2}+dots +x_{n}=k} $x_{1}+x_{2}+dots +x_{n}=k$ . Но число решений этого уравнения легко подсчитывается с помощью «шаров и перегородок»: каждое решение соответствует расстановке в ряд k{displaystyle k} $k$ шаров и n−1{displaystyle n-1} $n-1$ перегородок так, чтобы между (j−1){displaystyle (j-1)} $(j-1)$ -й и j{displaystyle j} $j$ -й перегородками находилось ровно xj{displaystyle x_{j}} $x_{j}$ шаров. Но таких расстановок в точности (n+k−1k){displaystyle {tbinom {n+k-1}{k}}} ${tbinom {n+k-1}{k}}$ , что и требовалось доказать.■

При фиксированном n{displaystyle n}

$n$ производящей функцией чисел сочетаний с повторениями из n{displaystyle n} $n$ по k{displaystyle k} $k$ является:

∑k=0∞(−1)k(−nk)xk=(1−x)−n.{displaystyle sum _{k=0}^{infty }(-1)^{k}{-n choose k}x^{k}=(1-x)^{-n}.}

sum _{k=0}^{infty }(-1)^{k}{-n choose k}x^{k}=(1-x)^{-n}.

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

∑n=0∞∑k=0∞(−1)k(−nk)xkyn=∑n=0∞(1−x)−nyn=1−x1−x−y.{displaystyle sum _{n=0}^{infty }sum _{k=0}^{infty }(-1)^{k}{-n choose k}x^{k}y^{n}=sum _{n=0}^{infty }(1-x)^{-n}y^{n}={frac {1-x}{1-x-y}}.}

sum _{n=0}^{infty }sum _{k=0}^{infty }(-1)^{k}{-n choose k}x^{k}y^{n}=sum _{n=0}^{infty }(1-x)^{-n}y^{n}={frac {1-x}{1-x-y}}.

См. также

Примечания

↑ Удивительный треугольник великого француза.

Ссылки

Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990.