Pike in pregrade (angleško stars and bars) so v kombinatorični matematiki grafična pomoč pri izpeljavi določenih kombinatoričnih izrekov. Populariziral jo je William Feller v svoji knjigi o verjetnosti. Uporablja se za reševanje veliko preprostih problemov preštevanja, kot recimo: koliko je načinov, da razvrstimo n enakih krogel v k enakih posod.

Izreki Metoda pik in pregrad se pogosto uporablja za dokaz sledečih dveh izrekov elementarne kombinatorike.

1. izrek Za katerikoli par naravnih števil n in k, je število k-urejenih množic naravnih števil, katerih vsota je enaka n, enako številu (k − 1)-elementni podmnožici množice z n − 1 elementi.Obe števili sta podani z binomskim koeficientom . Ko je na primer n = 3 in k = 2, sta urejeni množici, ki jih šteje izrek, enaki (2, 1) in (1, 2), obstaja pa natanko takšnih množic.

2. izrek Za katerikoli par naravnih števil n in k, je število k-urejenih množic nenegativnih celih števil, katerih vsota je n, enako številu večkratnih množic kardinalnosti k − 1, ki jih vzamemo iz množice velikosti n + 1.Obe števili sta podani s številom večkratne množice , ali ekvivalentno z binomskim koeficientom ali številom večkratne množice . Za n = 3 in k = 2 so urejeni pari, ki jih šteje izrek, enaki (3, 0), (2, 1), (1, 2) in (0, 3). Takih urejenih parov je .

Dokazi z metodo pik in pregrad

1. izrek Naj je n teles (ki jih tu predstavljajo pike; v primeru spodaj n = 7) položenih v k posod (v tem primeru k = 3), tako da vse posode vsebujejo najmanj eno telo. Posode so prepoznavne (recimo da so oštevilčene od 1 do k), toda n pik ni (torej se konfiguracije razlikujejo le po številu pik, ki so v posamezni posodi). Konfiguracija je torej predstavljena s k-urejeno množico naravnih števil, kot v matematičnem izrazoslovju izreka. Namesto da polagamo pike v posode, najprej položimo pike v vrsto.kjer bodo pike z leve šle v prvo posodo, sledile jim bodo pike za v drugo posodo in tako naprej. Iz tega sledi, da bo konfiguracija znana, ko bo znana prva pika, ki bo šla v drugo posodo in prva pika, ki bo šla v tretjo posodo in tako naprej. To se lahko označi s polaganjem ločitvenih pregrad med dvema pikama. Ker ne sme biti nobena posoda prazna, je lahko med dvema pikama največ ena pregrada:Poglejmo na n zvezd kot stalne objekte, ki definirajo prostih mest med zvezdami, v katerih je lahko ali pa ni ena pregrada (razdeljevanje na posode). Konfiguracijo se dobi z izbiro teh prostih mest, ki bodo dejansko vsebovala pregrado. Iz tega sledi, da je možnih konfiguracij (glej kombinacije).

2. izrek V tem primeru je predstavitev urejene množice kot zaporedja pik in pregrad nespremenjena, saj pregrade še vedno delijo pike v posode. Edin pogoj, ki ga bomo spremenili, je ta, da je lahko na enem prostem mestu tudi več pregrad, ki pa jih lahko postavimo tudi pred prvo in za zadnjo piko. Ko je n = 7 in k = 5, se lahko urejena množica (4, 0, 1, 2, 0) predstavi v sledečem diagramu.

To vzpostavi bijekcijo med urejenimi množicami želene oblike in izbirami z zamenjavo prostih mest izmed le-teh. Ekvivalentno: ()-elementne večkratne množice iz množice velikosti . Po definiciji se takšni objekti štejejo iz števila večkratnih množic .

Zgoraj dobljeni rezultat lahko izrazimo tudi kot . Da bi to lahko dobili tudi po drugi poti, moramo videti, da je želena konfiguracija sestavljena iz teles (n pik in pregrad). Z izbiro položaja pik dobimo natanko praznih mest za pregrad. Z izbiro položaja pik, ki ga določa celotna razporeditev, dobimo izbir. Toda velja , kar je posledica tega, da se lahko enak rezultat dobi z izbiro pregrad.

Primeri Za n = 5, k = 4 in za množico velikosti k, ki je {a, b, c, d}, bi ★|★★★||★ predstavljalo večkratno množico {a, b, b, b, d} ali 4-urejeno množico (1, 3, 0, 1). Predstavitev katerekoli večkratne množice za ta primer bi uporabljala n = 5 pik in k − 1 = 3 pregrad.

Veliko elementarnih besedilnih nalog v kombinatoriki se da rešiti z zgornjima izrekoma. Če želi nekdo prešteti število načinov za razporeditev sedem enakih evrskih kovancev med Anžeta, Benjamina in Ceneta, da vsak dobi najmanj en evro, lahko opazi, da so porazdelitve kovancev enake urejenim množicam treh naravnih števil, katerih vsota je enaka 7. (Prva vrednost je število Anžetovih kovancev in tako naprej.) Tukaj lahko uporabimo pike in pregrade z n = 7 in k = 3 in dobimo možnih načinov za porazdelitev kovancev.

Glej tudi

Particija (teorija števil)

Sklici

Nadaljnje branje

Kategorija:Kombinatorika