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

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето

Ѕвезди и прачки — поими во комбинаториката, кои нудат графичка помош при изведувањето на неколку комбинаторни теореми. Овие поими биле попларизирани до страна на Вилијам Фелер во неговото дело „Вовед во теоријата на веројатност и нејзината примена“ од 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, па оттаму има начини да се распределат монетите.

Наводи[уреди | уреди извор]

  1. Feller, W. (1950) An Introduction to Probability Theory and Its Applications, Wiley, Vol 1, 2nd ed.

Литература[уреди | уреди извор]

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