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

Ѕвезди и прачки — поими во комбинаториката, кои нудат графичка помош при изведувањето на неколку комбинаторни теореми. Овие поими биле попларизирани до страна на Вилијам Фелер во неговото дело „Вовед во теоријата на веројатност и нејзината примена“ од 1950 година. Тие може да се употребат за решавање на многу едноставни проблеми со пребројување, како на пример на колку начини може да се стават n идентични топчиња во k различни корпи.Feller, W. (1950) An Introduction to Probability Theory and Its Applications, Wiley, Vol 1, 2nd ed.

 Тврдења на теоремите 
 Прва теорема 
За секоја двојка на позитивни броеви n и k, бројот на подредени низи k од позитивни броеви чиј збир n е зададен со биномниот коефициент .

 Втора теорема 
За секоја двојка на позитивни броеви n и k, бројот на различни подредени низи k од ненегативни броеви чиј збир n е зададен со биномниот коефициент  или еквивалентно со повеќемножествениот број , којшто ги вбројува повеќемножествата со кардиналност n и елементи преземени од множество со k елементи (за  и двата броја е одредено да изнесуваат 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, па оттаму има  начини да се распределат монетите.

 Наводи 

 Литература 

Категорија:Комбинаторика