Binomial coefficient

Given a set x with n elements, the number of subsets of x that have r elements is the binomial coefficient of n in r and is denoted as:

equation2

The expression above can also be written as C (n, r) or nCr. The binomial coefficient indicates the number of ways in which an unordered subset of size r can be selected from a set of size n.

The binomial coefficient can be calculated using the following expression:

equation7

The formula above uses the factorial notation «!»; for any positive integer n, its factorial n! it is:

n! = n × (n - 1) × (n - 2)… × 3 × 2 × 1

Also, 0! = 1.

Pproperties

  • nCr + nCr + 1 = n + 1Cr + 1
  • nC0 +   nC1 + nC2 + ... + nCn = 2n
  • nC0 +   nC1 + nC2 + ... + (- 1)n nCn = 0
  • nC0 +   nC2 + nC4 + nC6 + ...  = 2n-1
  • nC0 +   nC3 + nC5 + nC7 + ...  = 2n-1
  • nCn –    n + 1C1 + n + 2C2  -… + n + mCn = n + m + 1Cn + 1  
  • nCn –    (nC1)2 + (nC2)2  - ... + (nCn)2 = 2nCn  
  • nC1 + 2nC2 + 3nC3 +… + N ·nCn = n · 2n-1
  • nC0 - two·nC1 + 3nC2 + ... + (-1)n + 1 · nCn = 0

Example: Determine the values of 10C4 y 30C18.

We know that:

nCr = n! / [(n - r)! ∙ r! ]

Thus:

  • 10C4 = 10! / [(10 - 4)! ∙ 4! ] = 10! / [6! ∙ 4! ] = 210
  • 30C18 = 30! / [(30 - 18)! ∙ 18! ] = 30! / [12! ∙ 18! ] = 8.6 x 107