C(n,k) (n choose k) is the combination of n things taken k at a time,
for n >= k >= 0
The closed form definition of C(n,k) is:
n!
---------
(n-k)! k!, for n >= k >= 0 and where C(n,k) = 0, for k < 0 or k > n
The recursive definition for C(n,k) is:
if (k=0) or (n = k) then 1
else C(n-1,k) + C(n-1,k-1)
Def: A binomial is the sum of two monomials. Example: x + y. The terms could have coefficients. A binomial can be raised to a power. Example: (x + y)^4 Expanding such a binomial means provide all terms as you compute (x+y)(x+y)(x+y)(x+y). Example:
(x + y)^2 = x^2 + 2xy + y^2.
The Binomial Expansion Theorem provides a formula for expanding a binomial of the form (x + y) raised to a power n. The formula also works for binomials of the form 2x + 5y and that will be covered later.
C(n,k) for k from 0 to n gives the coefficients of each term in the expansion of the binomial (x + y)^n:
n
Σ C(n,k) x^(n-k) y^k // the Binomial Expansion Theorem
k=0
Expanded form:
C(n,0)x^n + C(n,1)x^(n-1)y^1 + C(n,2)x^(n-2)y^2 + ... + C(n,n)y^n
Observations:
+ The sum of the exponents in each term is n
+ If S is a set containing n things; i.e., |S| = n, then the sum of all
coefficients in (x + y)^n is |P(S)|, which is 2^n. Why? Because C(n,k) for
k=0->n is all the ways you can construct subsets from S.
Example 1.
(x + y)^4 and (x + y)^5
The coefficients for the expansion of this binomial are the values of C(5,k),
as k moves from 0 to 5.
C(5,0) = 1
C(4,0) = 1 C(5,1) = 5
C(4,1) = 4 C(5,2) = 10 5*4/2
C(4,2) = 6 C(5,3) = 10 5*4*3/3*2
C(4,3) = 4 C(5,4) = 5
C(4,4) = 1 C(5,5) = 1
=== ====
16 =2^4 32 = 2^5
Expanded forms:
1x^4y^0 + 4x^3y^1 + 6x^2y^2 + 4x^1y^3 + 1x^0y^4
1x^5y^0 + 5x^4y^1 + 10x^3y^2 + 10x^2y^3 + 5x^1y^4 + 1x^0y^5
Observation.
C(n,k) = C(n,n-k)
If x and y have constant multipliers, multiply the binomial coefficient by
the constant to the appropriate power of x or y:
Example 3.
(2x + 3y)^4
Expanded form:
1(2x)^4(3y)^0 + 4(2x)^3(3y)^1) + 6(2x)^2(3y)^2 + 4(2x)^1(3y)^3 + 1(2x)^0(3y)^4
---------------------
| Pascal's Triangle |
---------------------
C(n,k) makes up the entries of Pascal's Triangle, where n is a row and k
is a column. Pascal's Triangle displays all values of C(n,k); e.g. Pascal's
Triangle for n<=6 (rows) and k<=6 (columns) is:
k
0 1 2 3 4 5 6
n ---------------------------
0| 1 1 <= the sum of each row is 2^n
1| 1 1 2
2| 1 2 1 4
3| 1 3 3 1 8
4| 1 4 6 4 1 16
5| 1 5 10 10 5 1 32
6| 1 6 15 20 15 6 1 64
7| 1 7 21 35 35 21 7 1 .. 128
k
0 1 2 3 4 5 6
n ---------------------------
0| 1 1 <= the sum of shallow diagonals is fib(n)
1| 1 1 1
2| 1 2 1 2 (1+1) fib(n)
3| 1 3 3 1 3 (1+2) if (n<=1) return 1
4| 1 4 6 4 1 5 (1+3+1) else return fib(n-1) + fib(n-2)
5| 1 5 10 10 5 1 8 (1+4+3)
6| 1 6 15 20 15 6 1 13 (1+5+6+1)
7| 1 7 21 35 35 21 7 1 21 (1+6+10+4)
Pascal's Triangle in pyramid form, where n is the row.
Sum of Shallow Diags Sum of Rows
n=0 1 1 1
n=1 1 1 1=1 1+1=2
n=2 1 2 1 1+1=2 1+2+1=4
n=3 1 3 3 1 1+2=3 1+3+3+1=8
n=4 1 4 6 4 1 1+3+1=5 1+4+6+4+1=16
n=5 1 5 10 10 5 1 1+4+3=8 1+5+10+10+5+1=32
n=6 1 6 15 20 15 6 1 1+5+6+1=13 64
n=7 1 7 21 35 35 21 7 1 1+6+10+4=21 128
n=8 1 8 28 56 70 56 28 8 1 1+7+15+10+1=34 256
n=9 1 9 36 84 126 126 84 36 9 1 512
n=10 1 10 45 120 210 252 210 120 45 10 1 1024
n=11 1 11 55 165 330 462 462 330 165 55 11 1 2048
Observation:
+ the sum of the coefficients in each row i, from 0 to n is 2^n
+ the diagonal next to the edge contains the counting numbers
+ the next diagonals are the sequence 1,3,6,10,... defined by
F_n = n(n+1)/2, n>=1 (also called the triangular numbers)
+ the shallow diagonals of the triangle sum to the Fibonacci numbers ; e.g.
1, 1, 2, 3, 5, 8, 13, 21,...
Recursive definition:
C(n,k) = C(n-1,k-1) + C(n-1,k)
C(n,0) = 1
C(n,n) = 1 */
/* ----------------------------------------------------------------
Code to calculate C(n,k) and display Pascal's triangle
-------------------------------------------------------------------*/
#include
#include
#define MAX 12
using namespace std;
static int cnt = 0;
typedef int PascalArray [MAX][MAX];
PascalArray p;
int C( int n, int k ); // recursive function to calculate C(n,k)
void C2(int n,int k); // display triangle using nonrecursion and an array
int C3(int n,int k); // nonrecursive function to calculate C(n,k)
int main ()
{
int result;
cout << "recursive function C(6,4): \n";
result = C(6,4);
cout << "Result: " << result << endl;
cout << "\nnon-recursive function C2(5,2) using array" << endl;
C2(5,2);
cout << "\nnon-recursive function C3(7,4): " << C3(7,4) << endl;
return 0;
}
/* ----------recursive algorithm to compute C(n,k) */
int C( int n, int k ){
cnt++;
cout << cnt << " n: " << n << " k: " << k << endl;
if ( !k || (n == k))
return 1;
else
return ( C(n-1,k) + C(n-1,k-1) );
}
/* ----------display triangle using nonrecursive algorithm and an array */
void C2( int n, int k )
{
int row, col;
for (row = 0; row < MAX; row++)
for(col = 0; col <= row; col++) {
if (col == 0 || row == col)
p[row][col] = 1;
else
p[row][col] = p[row-1][col] + p[row-1][col-1];
}
/* display the triangle */
for (row = 0; row < MAX; row ++){
cout << setw( (2* MAX - 2 * row)) << " "; // move over an offset
for (col=0; col <= row; col++)
cout << setw(4) << p[row][col];
cout << endl;
}
}
/* A non-recursive function that uses neither an array nor a stack.
The answer to this problem required knowledge of the formula:
C(n,k) = (the product as i goes from 1 to k of (n-i + 1))/i
pre: n >= k >= 0 */
int C3(int n,int k){
int i, answer = 1;
for (i = 1; i <= k; i++)
answer = (answer * (n + 1 - i)) / i;
return answer;
}
/*------------------------------------------------------------------------
The recursive function requires space proportional to n and time
proportional to 2*C(n,k) = 2 (n/k(n-k))
The non-recursive function requires constant time for each entry in
a n*n array, hence time proportional to n*n and space proportional to n*n.
The nonrecursive function requires time proportional to k and
constant space. */