PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (213)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (40)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: High
binomial coefficient (Definition)

For integers $ n\ge r \ge 0$ we define

$\displaystyle {n\choose r} = \frac{n!}{(n-r)!r!} $
and call such numbers binomial coefficients.

Properties.

  1. $ n\choose r$ is an integer (proof.).
  2. $ {n\choose r}={n\choose n-r}$.
  3. $ {n\choose r-1}+{n\choose r}={n+1\choose r}$ (Pascal's rule).
  4. $ {n\choose 0}=1={n\choose n}$ for all $ n$.
  5. $ {n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots+{n\choose n}=2^n$.
  6. $ {n\choose 0}-{n\choose 1}+{n\choose 2}-\cdots+(-1)^n{n\choose n}=0$ for $ n>0$.
  7. $ \sum_{t=1}^n {t\choose k }={n+1\choose k+1}$.

Properties 5 and 6 are the binomial theorem applied to $ (1+1)^n$ and $ (1-1)^n$, respectively, although they also have purely combinatorial meaning.

Motivation

Suppose $ n\ge r$ are integers. The below list shows some examples where the binomial coefficients appear.
  • $ n\choose r$ constitute the coefficients when expanding the binomial $ (x+y)^n$ - hence the name binomial coefficients. See Binomial Theorem.
  • $ n\choose r$ is the number of ways to choose $ r$ objects from a set with $ n$ elements.
  • On the context of computer science, it also helps to see $ {n\choose r}$ as the number of strings consisting of ones and zeros with $ r$ ones and $ n-r$ zeros. This equivalency comes from the fact that if $ S$ be a finite set with $ n$ elements, $ {n\choose r}$ is the number of distinct subsets of $ S$ with $ r$ elements. For each subset $ T$ of $ S$, consider the function
    $\displaystyle X_T\colon S \rightarrow \{0,1\} $
    where $ X_T(x) = 1$ whenever $ x \in T$ and 0 otherwise (so $ X_T$ is the characteristic function for $ T$). For each $ T \in \mathcal{P}(S)$, $ X_T$ can be used to produce a unique bit string of length $ n$ with exactly $ r$ ones.

Notes

The $ {n\choose r}$ notation was first introduced by von Ettinghausen [1] in 1826, altough these numbers have been used long before that. See this page for some notes on their history. Although the standard mathematical notation for the binomial coefficients is $ n\choose r$, there are also several variants. Especially in high school environments one encounters also $ {C}(n,r)$ or $ {C}^n_r$ for $ {n\choose r}$.

Bibliography

1
N. Higham, Handbook of writing for the mathematical sciences, Society for Industrial and Applied Mathematics, 1998.



"binomial coefficient" is owned by matte. [ full author list (4) | owner history (1) ]
(view preamble)

View style:

See Also: Pascal's rule, binomial theorem, binomial distribution, multinomial theorem, proof of Lucas's theorem, factorial, central binomial coefficient, Pascal's triangle, Taylor series via division, combinations with repeated elements

Other names:  combinations, choose
Keywords:  Combinatorics

Attachments:
Kummer's theorem (Theorem) by Thomas Heye
upper and lower bounds to binomial coefficient (Theorem) by rspuzio
sum of powers of binomial coefficients (Result) by Andrea Ambrosio
an algebraic identity leading to Wilson's theorem (Result) by GeraW
generalized binomial coefficients (Definition) by pahio
${n\choose r}$ is an integer (Theorem) by matte
Log in to rate this entry.
(view current ratings)

Cross-references: length, characteristic function, function, subsets, finite set, strings, objects, binomial, coefficients, binomial theorem, properties, Pascal's rule, integers
There are 81 references to this entry.

This is version 25 of binomial coefficient, born on 2001-10-17, modified 2007-08-01.
Object id is 273, canonical name is BinomialCoefficient.
Accessed 35567 times total.

Classification:
AMS MSC: 05A10 (Combinatorics :: Enumerative combinatorics :: Factorials, binomial coefficients, combinatorial functions)
 11B65 (Number theory :: Sequences and sets :: Binomial coefficients; factorials; $q$-identities)
Pending Errata and Addenda
None.
[ View all 12 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)