partitioihin

Partitioihin viitataan yleisesti kahteen toisiinsa liittyvään käsitteeseen: joukkojen partitioihin ja kokonaislukujen partitioihin. Molemmissa tapauksissa idea on jakaa jokin kokonaisuus pienempiin osiin siten, että osien yhteenlaskettu määrä vastaa alkuperäistä kokonaisuutta, ja että osat sopivat keskenään yhteen niin, ettei niillä ole päällekkäisyyksiä. Eri konteksteissa järjestyksen merkitys vaihtelee: joissakin partitioissa järjestys ei ole tärkeä, toisissa taas voidaan tarkastella järjestettyjä jakautumia.

Joukon partitio on joukko ei-tyhjiä, disjunktteja osajoukkoja, joiden yhteenlaskettu union on alkuperäinen joukko. Osat ovat epäjärjestettyjä, eli partitionin sisällä ei ole oleellista, missä järjestyksessä lohkot esiintyvät: P = {B1, ..., Bk}. Esimerkki: S = {a,b,c,d} voidaan partitionoida esimerkiksi {a,b} ja {c,d}, tai {a} ja {b,c,d}.

Kokonaislukujen partitio tarkoittaa tapaa kirjoittaa n positiivisena kokonaislukuna summina: n = λ1 + λ2 + ... + λr, missä λ1 ≥ λ2 ≥ ... ≥ λr ≥ 1. Järjestyksellä ei ole merkitystä. Esimerkkejä luvulle 4 ovat 4; 3+1; 2+2; 2+1+1; 1+1+1+1. Partitioiden määrää p(n) tutkitaan ja lasketaan erilaisten laskukaavojen ja generaattorifunktioiden avulla.

Sovelluksia partitioilla esiintyvät laajasti kombinatoriikassa, tilastotieteessä, todennäköisyyslaskennassa sekä klusteroinnissa ja hierarkisessa luokittelussa.