Ѕвезди и прачки
Ѕвезди и прачки — поими во комбинаториката, кои нудат графичка помош при изведувањето на неколку комбинаторни теореми. Овие поими биле попларизирани до страна на Вилијам Фелер во неговото дело „Вовед во теоријата на веројатност и нејзината примена“ од 1950 година. Тие може да се употребат за решавање на многу едноставни проблеми со пребројување, како на пример на колку начини може да се стават n идентични топчиња во k различни корпи.[1]
Тврдења на теоремите
Прва теорема
За секоја двојка на позитивни броеви 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, па оттаму има начини да се распределат монетите.
Наводи
Литература
- ↑ Feller, W. (1950) An Introduction to Probability Theory and Its Applications, Wiley, Vol 1, 2nd ed.