Kompozicija i particija broja

#fax #math #ds2 [deo kombinatorike]

Kompozicija broja

Def. Kompozicija broja na sabiraka je uređena -torka prirodnih brojeva takva da

Primer:
—
—
—
—
Ukupno:

Teorema. Broj kompozicija broja na sabiraka iz je

Dokaz:
Treba rasporediti pluseva na mesta. To moguće uraditi na načina

Teorema. Broj kompozicija broja je .

Dokaz:

Particija broja

Def. Particija broja na sabiraka je multiskup (dozvoljeno ponavljanje, redosled nije bitan) prirodnih brojeva takav da

Primer:
—
—
—
—
Ukupno:

Broj particija broja na sabiraka iz :
Broj particija broja :

Niz particija brojeva:

Teorema.

Dokaz:

Ferersov dijagram

Def. Ferersov dijagram neke particije broja na sabiraka sastoji od markera raspoređenih u vrste tako da svakoj vrsti odgovara jedan sabirak i ona sadrži markera. Vrste uređene opadajuće po broju markera.

Primer:

Def. Dve particije su konjugovane (jedna u odnosu na drugu) ako jedna se dobija zamenom mesta vrsta i kolona drugoj.

Primer:

Def. Particija je samokonjugovana ako je konjugovana samoj sebi.

Teorema. Važe identiteti:

$č$