Yulduzlar va ustunlar

Yulduzlar va ustunlar

Kirish

Yulduzlar va ustunlar — bu klassik kombinator usul bo‘lib, bir xil obyektlarni turli konteynerlar bo‘yicha taqsimlash usullari sonini hisoblashga imkon beradi.

G‘oya juda sodda:

• yulduzchalar * obyektlarni bildiradi,
• ustunlar | konteynerlarni ajratadi.

Teorema

Masalaning qo‘yilishi

Berilgan:

• $k$ ta bir xil obyekt,
• $n$ ta turli konteyner.

Bu $k$ obyektni $n$ konteynerga nechta usul bilan taqsimlash mumkin?

Biz taqsimotni quyidagilardan iborat ketma-ketlik sifatida tasavvur qilishimiz mumkin:

• $k$ ta yulduzcha *,
• $n-1$ ta ustun .