Binomialkoefficient

Fra Wikipedia, den frie encyklopædi

Inden for den matematiske gren kombinatorik er binomialkoefficienten af det naturlige tal n over heltallet k antallet af kombinationer der eksisterer af at vælge k ud af n mulige.

[redigér] Definition

Givet et ikke-negativt heltal n og et heltal k, er binomialkoefficienten defineret som det naturlige tal


  {n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}
  {k \cdot (k-1) \cdots 1} = \frac{n!}{k!(n-k)!} \quad \mbox{hvis}\ n\geq k\geq 0,

og

 {n \choose k} = 0 \quad \mbox{hvis } k<0 \mbox{ eller } k>n,

hvor n! betyder n fakultet.


Binomialkoefficienterne er nok bedst kendt fra binomialformlen

 (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k.

[redigér] Eksempel

Hvis man skal købe en pizza med tre slags "fyld" (og man ikke tillader gentagelser) og der er 20 forskellige slags "fyld" at vælge imellem, kan man vælge

{20\choose 3}=\frac{20!}{3!\,17!}=1140

forskellige pizzaer.

[redigér] Se også

organisation