Counting Principles
Sum Rule
Product Rule
Combination
Generation of Permutation
Binomial Theorem
Sum Rule
If S = A U B and A and B are disjoint i.e. A ∩ B = ϕ then
|S| = |A| + |B|
Product Rule
We have, A and B are non empty sets and |A|=n, |B|=m, then number of elements in the
cartesian product of A and B is equal to n x m.
|A x B| = n x m
Combination
For repetition, C(n+r-1, r)=C(n+r-1, n-1)
The number of integer solutions to a1 + a2 + a3 + .... + an = r when when a1 ≥
b1 , a2 ≥ b2 , ..., an ≥ bn is C(n + r − 1 − b1 − b2 − b3 − ...bn , r − b1 − b2 −
b3 − ...bn )
The number of ways to select r things from n categories with b total restrictions on the r
things is c(n+r-1-b, r-b)
The number of ways to select r things from n categories with at least 1 thing from each
category is C(r-1,r-n)
Counting Principles 1
Counting Principles
Sum Rule
Product Rule
Combination
Generation of Permutation
Binomial Theorem
Sum Rule
If S = A U B and A and B are disjoint i.e. A ∩ B = ϕ then
|S| = |A| + |B|
Product Rule
We have, A and B are non empty sets and |A|=n, |B|=m, then number of elements in the
cartesian product of A and B is equal to n x m.
|A x B| = n x m
Combination
For repetition, C(n+r-1, r)=C(n+r-1, n-1)
The number of integer solutions to a1 + a2 + a3 + .... + an = r when when a1 ≥
b1 , a2 ≥ b2 , ..., an ≥ bn is C(n + r − 1 − b1 − b2 − b3 − ...bn , r − b1 − b2 −
b3 − ...bn )
The number of ways to select r things from n categories with b total restrictions on the r
things is c(n+r-1-b, r-b)
The number of ways to select r things from n categories with at least 1 thing from each
category is C(r-1,r-n)
Counting Principles 1
