Kombinatorika
Partície
Kombinácie s opakovaním
Nech
je množina kategórií (druhov, prvkov). Vytvorme -tice z týchto
prvkov, v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Zrejme môže nastať aj prípad .
Definícia.
-kombinácie s opakovaním definujeme ako -tice prvkov z druhov , v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Počet všetkých -kombinácií s opakovaním z prvkov budeme označovať symbolom .
-kombinácie s opakovaním definujeme ako -tice prvkov z druhov , v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Počet všetkých -kombinácií s opakovaním z prvkov budeme označovať symbolom .
Príklad.
V obchode predávajú tri druhy cukru: kryštálový , práškový a hnedý v kilogramovom balení. Vypíšte všetky možnosti pri nákupe 2 resp. 3 kilogramov cukru. V nákupe sa môže opakovať ten istý druh cukru.
Riešenie. Uvedieme nejaké možné nákupy, napríklad 2 kilogramový nákup môže byť {1 kg práškového cukru, 1 kg kryštálového cukru} alebo 3 kilogramový nákup môže byť {2 kg práškového cukru, 1 kg hnedého cukru} .
Všetky nákupy dvoch kilogramov budú predstavovať 2-kombinácie s opakovaním z troch druhov cukru - . Všetky nákupy troch kilogramov budú predstavovať 3-kombinácie s opakovaním z troch druhov cukru - .
Pokúste sa vymenovať všetky možné nákupy. Pri nákupe
V obchode predávajú tri druhy cukru: kryštálový , práškový a hnedý v kilogramovom balení. Vypíšte všetky možnosti pri nákupe 2 resp. 3 kilogramov cukru. V nákupe sa môže opakovať ten istý druh cukru.
Riešenie. Uvedieme nejaké možné nákupy, napríklad 2 kilogramový nákup môže byť {1 kg práškového cukru, 1 kg kryštálového cukru} alebo 3 kilogramový nákup môže byť {2 kg práškového cukru, 1 kg hnedého cukru} .
Všetky nákupy dvoch kilogramov budú predstavovať 2-kombinácie s opakovaním z troch druhov cukru - . Všetky nákupy troch kilogramov budú predstavovať 3-kombinácie s opakovaním z troch druhov cukru - .
Pokúste sa vymenovať všetky možné nákupy. Pri nákupe
Dôkaz.
Nech označuje počet výskytu prvku v nejakej -kombinácií s opakovaním. Potom zrejme musí platiť rovnosť
.
Napríklad pre nákup ide o rovnosť
Nech označuje počet výskytu prvku v nejakej -kombinácií s opakovaním. Potom zrejme musí platiť rovnosť
.
Napríklad pre nákup ide o rovnosť
- Ak k obidvom stranám tejto rovnosti pripočítame číslo , tak po menšej úprave dostaneme rovnosť ,
- Na rovnosť sa môžeme pozerať ako na rozdelenie čísla na častí alebo ako na partície (navzájom rôznych aspoň poradím) čísla na častí.
- Počet takýchto partícií je rovný číslu
.Tým sme dokázali tvrdenie.
Pre nákup dvoch litrov dostávame .
kde pre .
Pre nákup ide o rovnosť .
Na úlohy (pozrite tiež predchádzajúci príklad) typu:
"V obchode majú tri druhy sirupu: jahodový, malinový a pomarančový. Určite počet všetkých možností nákupu piatich fliaš sirupu v obchode."
sa môžeme pozerať aj ako na permutácie s opakovaním. Úlohu vyriešime tak, že určíme počet spôsobov, ako rozmiestniť fliaš sirupu do druhov/košov.
Použijeme dva symboly: • - fľaša; ↑-oddeľovač. Potom rozmiestnenia budú predstavovať -tice, v ktorých sa symbol "•" vyskytuje -krát (fľaše) a symbol "↑" -krát (\\small ( n-1 \) oddelení medzi košmi).
Rozmiestnenie symbolov predstavuje 2 jahodové sirupy, 0 malinový a 3 pomarančové sirupy alebo (122).
Počet takých -tíc zodpovedá počtu permutácií zo 7 prvkov s opakovaním, kde sa prvý prvok opakuje/vyskytuje -krát a druhý -krát. Tým sme ukázali platnosť vzťahu
=.
"V obchode majú tri druhy sirupu: jahodový, malinový a pomarančový. Určite počet všetkých možností nákupu piatich fliaš sirupu v obchode."
sa môžeme pozerať aj ako na permutácie s opakovaním. Úlohu vyriešime tak, že určíme počet spôsobov, ako rozmiestniť fliaš sirupu do druhov/košov.
Použijeme dva symboly: • - fľaša; ↑-oddeľovač. Potom rozmiestnenia budú predstavovať -tice, v ktorých sa symbol "•" vyskytuje -krát (fľaše) a symbol "↑" -krát (\\small ( n-1 \) oddelení medzi košmi).
Rozmiestnenie symbolov predstavuje 2 jahodové sirupy, 0 malinový a 3 pomarančové sirupy alebo (122).
Počet takých -tíc zodpovedá počtu permutácií zo 7 prvkov s opakovaním, kde sa prvý prvok opakuje/vyskytuje -krát a druhý -krát. Tým sme ukázali platnosť vzťahu
=.