Yhdistelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3. joulukuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Kombinatoriikassa by -yhdistelmä on elementtijoukko , joka on valittu -elementtijoukosta , jossa alkioiden järjestystä ei oteta huomioon. $n$ $k$ $k$ $n$

Vastaavasti yhdistelmiä, jotka eroavat vain elementtien järjestyksestä (mutta ei koostumuksesta), pidetään samoina - näin yhdistelmät eroavat sijoitteluista . Joten esimerkiksi 3-elementtiset yhdistelmät 2 ja 3 ( (ei-tiukat) osajoukot , joille ) 6-elementtijoukosta 1 ( ) ovat samat (vaikka järjestelyt olisivat erilaisia) ja koostuvat samoista elementeistä 1. $k = 3$ $n = 6$

Yleensä -elementtijoukon kaikkien mahdollisten -elementtiosajoukkojen lukumäärä on Pascalin kolmion -: nnen diagonaalin ja -:nnen rivin leikkauspisteessä . [yksi] $k$ $n$ $k$ $n$

Yhdistelmien määrä

Yhdistelmien määrä $n$ $k$ yhtä suurella binomikertoimella

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

Yhdistelmälukujen sarjan kiinteälle generoivalle funktiolle , , , … on $n$ ${\tbinom {n}{0))$ ${\tbinom {n}{1))$ ${\tbinom {n}{2))$

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

Yhdistelmälukujen kaksiulotteinen generointifunktio on

\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}}.

Yhdistelmät toistoilla

Yhdistelmä toistojen kanssa on sellainen -elementtijoukko -elementtijoukosta, johon kukin elementti voi osallistua useita kertoja, mutta jossa järjestystä ei oteta huomioon ( multiset ). Erityisesti monotonisten ei- pienenevien funktioiden määrä joukosta joukkoon on yhtä suuri kuin yhdistelmät, joissa on toistoja välillä - . $n$ $k$ $k$ $n$ ${\näyttötyyli \{1,2,\pisteet ,k\))$ $\{1,2,\pisteet,n\}$ $n$ $k$

Yhdistelmien määrä, joiden toistot ovat yhtä suurella binomikertoimella $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)!}}.

Todiste

Olkoon esinetyyppejä, ja samantyyppiset esineet ovat erottamattomia. Olkoon kutakin tyyppiä rajaton (tai riittävän suuri, vähintään vähintään ) määrä. Tästä valikoimasta valitsemme esineitä; valinta voi sisältää samantyyppisiä objekteja, valintajärjestyksellä ei ole väliä. Merkitään valittujen -: nnen tyypin objektien lukumäärällä, , . Sitten . Mutta tämän yhtälön ratkaisujen määrä voidaan helposti laskea "pallojen ja väliseinämien" avulla: jokainen ratkaisu vastaa pallojen ja väliseinien järjestelyä peräkkäin siten, että -: nnen ja -nnennen osion välissä on täsmälleen pallot . Mutta tällaiset järjestelyt olivat juuri sitä, mitä vaadittiin todistettavaksi. ■ $n$ $k$ $k$ $x_{j}$ $j$ $x_{j}\geq 0$ $j=1,2,\pisteet ,n$ $x_{1}+x_{2}+\pisteet +x_{n}=k$ $k$ $n-1$ $(j-1)$ $j$ $x_{j}$ ${\tbinom {n+k-1}{k))$

Kiinteälle , toistojen lukumäärän generointifunktio alkaen by on yhtä suuri kuin $n$ $n$ $k$

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

Toistojen yhdistelmien lukumäärän kaksiulotteinen generointifunktio on

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

Katso myös

Muistiinpanot

↑ Suuren ranskalaisen hämmästyttävä kolmio. . Haettu 20. huhtikuuta 2010. Arkistoitu alkuperäisestä 21. huhtikuuta 2010. (määrätön)

Linkit

R. Stanley. Enumeratiivinen kombinatoriikka. - M .: Mir, 1990.