Binomial coefficient

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is a stub and thus not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.

The binomial coefficient is a part of combinatorics. The binomial coefficient represent the number of possible choices of k elements out of n labelled elements (with the order of the k elements being irrelevant): that is, the number of subsets of size k in a set of size n. The binomial coefficients are written as ; they are named for their role in the expansion of the binomial expression (x+y)n.

Definition

Example

Formulae involving binomial coefficients

Specifying a subset of size k is equivalent to specifying its complement, a subset of size n-k and vice versa. Hence

There is just one way to choose n elements out of n ("all of them") and correspondingly just one way to choose zero element ("none of them").

The number of singletons (single-element sets) is n.

The subset of size k out of n things may be split into those which do not contain the element n, which correspond to subset of n-1 of size k, and those which do contain the element n. The latter are uniquely specified by the remaining k-1 element which are drawn from the other n-1.

There are no subsets of negative size or of size greater than n.

Examples

=

Usage

The binomial coefficient can be used to describe the mathematics of lottery games. For example the German Lotto has a system, where you can choose 6 numbers from the numbers 1 to 49. The binomial coefficient is 13,983,816, so the probability to choose the correct six numbers is .

Binomial coefficients and prime numbers

If p is a prime number then p divides for every . The converse is also true.