Kombination

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 3 december 2021; kontroller kräver 2 redigeringar .

I kombinatorik är en kombination av by en uppsättning element valda från en -elementuppsättning , där ordningen på elementen inte tas med i beräkningen. $n$ $k$ $k$ $n$

Följaktligen anses kombinationer som bara skiljer sig i ordningen på elementen (men inte i sammansättningen) vara desamma - det är så kombinationer skiljer sig från placeringar . Så till exempel, 3-elementskombinationer 2 och 3 ( (icke-strikt) delmängder för vilka ) från en 6-elementsuppsättning 1 ( ) är desamma (medan arrangemangen skulle vara olika) och består av samma element 1. $k=3$ $n=6$

I allmänhet är antalet av alla möjliga -elementdelmängder av en -elementuppsättning i skärningspunkten mellan den -th diagonalen och den -th raden i Pascals triangel . [ett] $k$ $n$ $k$ $n$

Antal kombinationer

Antal kombinationer av $n$ $k$ lika binomial koefficient

{n \choose k}=C_{n}^{k}={\frac {n!}{k!\left(nk\right)!}}).

För en fast genererande funktion av sekvensen av kombinationsnummer är , , … $n$ ${\tbinom {n}{0))$ ${\tbinom {n}{1))$ ${\tbinom {n}{2))$

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

Den tvådimensionella genererande funktionen av kombinationsnummer är

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

Kombinationer med upprepningar

En kombination med upprepningar från till är en sådan -elementuppsättning från -elementuppsättning, där varje element kan delta flera gånger, men där ordningen inte beaktas ( multiset ). I synnerhet är antalet monotona icke- minskande funktioner från uppsättning till uppsättning lika med antalet kombinationer med upprepningar från till . $n$ $k$ $k$ $n$ ${\displaystyle \{1,2,\dots ,k\))$ $\{1,2,\dots,n\}$ $n$ $k$

Antalet kombinationer med upprepningar med en lika stor binomial koefficient $n$ $k$

{\overline {C_{n}^{k}}}=C_{(n)}^{k}=\left(\!\!{\binom {n}{k}}\!\! \right)={\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n }{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.

Bevis

Låt det finnas typer av objekt, och objekt av samma typ går inte att särskilja. Låt det finnas ett obegränsat (eller tillräckligt stort, åtminstone inte mindre än ) antal objekt av varje typ. Från detta sortiment kommer vi att välja objekt; urvalet kan innehålla objekt av samma typ, urvalsordningen spelar ingen roll. Beteckna med antalet markerade objekt av den -e typen, , . Sedan . Men antalet lösningar till denna ekvation kan enkelt beräknas med hjälp av "kulor och skiljeväggar": varje lösning motsvarar ett arrangemang av kulor och skiljeväggar i en rad så att det är exakt kulor mellan -: e och -te partitionerna. Men sådana arrangemang är precis vad som krävdes för att bevisas. ■ $n$ $k$ $k$ $x_{j}$ $j$ $x_{j}\geq 0$ $j=1,2,\prickar ,n$ $x_{1}+x_{2}+\dots +x_{n}=k$ $k$ $n-1$ $(j-1)$ $j$ $x_{j}$ ${\tbinom {n+k-1}{k))$

För fast är den genererande funktionen för antalet kombinationer med upprepningar från by lika med $n$ $n$ $k$

\sum _{k=0}^{\infty }\left[(-1)^{k}{-n \choose k}\right]x^{k}=(1-x)^{ -n}.

Den tvådimensionella genererande funktionen av antalet kombinationer med upprepningar är

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

Se även

Anteckningar

↑ Den stora fransmannens fantastiska triangel. . Hämtad 20 april 2010. Arkiverad från originalet 21 april 2010. (obestämd)

Länkar

R. Stanley. Enumerativ kombinatorik. — M .: Mir, 1990.