Moniyhdistelmien

Moniyhdistelmien käsite viittaa combinatorian alueeseen, jossa alkioita valitaan suuremmasta perusjoukosta siten, että toistojen käyttö on sallittua ja järjestyksellä ei ole merkitystä. Tällaisia yhdistelmiä kutsutaan usein multiset-yhdistelmäksi: kukin perusjoukon alkio voi esiintyä valinnassa useammankin kerran, ja kokonaismäärä on kiinteä.

Matemaattinen kuvaus on seuraava: olkoot perusjoukko, jolla on n erilaista alkiota, ja halutaan moniyhdistelmä, jossa valittavien alkioiden määrä on k. Merkitään kunkin alkioen multipliciteettiä x1, x2, ..., xn, missä xi on ei-negatiivinen kokonaisluku ja x1 + x2 + ... + xn = k. Näin moniyhdistelmien lukumäärä on binomiaalinen luku C(n + k − 1, k). Tämä tulos tunnetaan stars and bars -menetelmänä.

Esimerkki: Jos perusjoukko on {A, B, C} (n = 3) ja halutaan moniyhdistelmä kooltaan k = 3, löytyy 10 erilaista moniyhdistelmää: A A A, A A B, A A C, A B B, A B C, A C C, B B B, B B C, B C C, C C C.

Ominaisuudet ja sovellukset: moniyhdistelmien tutkiminen liittyy weak compositions -käsitteeseen ja generating function -menetelmiin. Generating function on (1 + x + x^2 + ...)^n = (1 − x)^−n, ja k:n kertoimen saadaan koeffisienttina tästä. Käytännön sovelluksia ovat todennäköisyyslaskenta, tilastot, kemialliset sekoitukset sekä mistä tahansa tilanteista, joissa toistoja sallitaan ja järjestyksellä ei ole väliä.

Lisätermit: multisetit, yhdistelmät toistojen kanssa, stars and bars, vahvat/heikot koostumukset.