Ѕвезди и прачки

Ѕвезди и прачки — поими во комбинаториката, кои нудат графичка помош при изведувањето на неколку комбинаторни теореми. Овие поими биле попларизирани до страна на Вилијам Фелер во неговото дело „Вовед во теоријата на веројатност и нејзината примена“ од 1950 година. Тие може да се употребат за решавање на многу едноставни проблеми со пребројување, како на пример на колку начини може да се стават n идентични топчиња во k различни корпи.

Тврдења на теоремите

Прва теорема

За секоја двојка на позитивни броеви n и k, бројот на подредени низи k од позитивни броеви чиј збир n е зададен со биномниот коефициент $\textstyle {n-1 \choose k-1}$.

Втора теорема

За секоја двојка на позитивни броеви n и k, бројот на различни подредени низи k од ненегативни броеви чиј збир n е зададен со биномниот коефициент ${\tbinom {n+k-1}{n}}$ или еквивалентно со повеќемножествениот број $\left(\!{\tbinom {k}{n}}\!\right)$, којшто ги вбројува повеќемножествата со кардиналност n и елементи преземени од множество со k елементи (за $n=k=0$ и двата броја е одредено да изнесуваат 1).

Пример

На пример, ако n = 5, k = 4 и множеството со големина k е {a, b, c, d}, тогаш ★|★★★||★ го претставува повеќемножеството {a, b, b, b, d} или подредената низа од четири члена (1,3,0,1). Приказот на било кое повеќемножество во овој пример користи пет ѕвезди (n) и три прачки (k - 1).

Седум идентични монети од по еден денар треба да бидат расптределени меѓу три лица, така што секој од нив да добие најмалку еден денар. Во овој случај, бројот на ѕвезди n = 7 и бројот на прачки k = 3, па оттаму има $\textstyle {7-1 \choose 3-1}=15$ начини да се распределат монетите.

Литература

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 0-387-97974-3.
• Weisstein, Eric W. „Multichoose“. Mathworld -- A Wolfram Web Resource. Посетено на 18 November 2012.