Ситораҳо ва сутунҳо

Ситораҳо ва сутунҳо

Муқаддима

Stars and Bars — ин як усули классикии комбинаторӣ аст, ки имкон медиҳад шумораи роҳҳои тақсим кардани объектҳои якхела ба контейнерҳои гуногун ҳисоб карда шавад.

Ғоя хеле содда аст:

• ситорачаҳо * объектҳоро нишон медиҳанд,
• сутунҳо | контейнерҳоро ҷудо мекунанд.

Теорема

Гузориши масъала

Дода шудааст:

• $k$ объекти якхела,
• $n$ контейнерҳои гуногун.

Бо чанд роҳ метавон ин $k$ объектро ба $n$ контейнер тақсим кард?

Мо метавонем тақсимотро ҳамчун пайдарпаии зерин тасаввур кунем:

• $k$ ситорача *,
• $n-1$ сутун .