1 Flashcards
Binomial coefficient
The binomial coefficient n choose k Is defined by
(n)
(k)
=
n• (n-1)• ….•(n-k +1) / k•(k-1)•(k-2)• 2•1
= n! / [k! • (n-k)! ] if 0 is less than or equal to k is less than or equal to n, for integers n and k
O/w =0.
This is the number of ways of choosing k from n items when the order doesn’t matter so dividing by the possible permutations for each
Eg choosing 3 which can be re ordered 321 times
Theorem 6 the Binomial theorem
(1+x) ^n
(n) + (n) x + ….
(0) (1)
(n) x^k +….+ (n) x^n
(k) (n)
= (from k= 0 to k=n) ∑( nCk) • x^k
Sum of all x^ (powers of sizes of all subsets of 1,..,n )
To get x^k from n brackets must have chosen entries x from brackets out of n
Pascal’s triangle
Coefficients of the binomial coefficients in binomial theorem
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
•line of symmetry •each (except for row 0 is sum of two above) • note patterns: 1’s for k=0 and k=n 1,2,3,4,5.6,... k=1 1,3,6,10,15,...k=2 1,4,10,20,... k=3 1,5,15,,.... k=4 1,6,... k=5 For sequence of nCk
Proposition 7:
Pascals identity
For n not equal to 0 and all k
(nCk) = ( (n-1)C( k-1)) + ((n-1)C(k))
Sum of the top two above equal below on Pascal’s triangle
The #subsets A from {1,..,n} with size |A|=m can be divided into
•those that contain element n
So choosing, from n-1, m-1 elements (one is n)
A= B U {n}
• those that don’t contain element n
So choosing, from n-1 elements, m elements
And summing
Addition rule works everywhere except the top
How many subsets does a set of n elements have
A set of n has 2^n subsets
For each element there are two choices: in or out
222…. n times
Also..
•{1} has itself and the empty sets as a subset
•{1,2} has the same ones plus the same ones with an extra 2 (DOUBLES)
Doubles each time so *2
Lists of k distinct elements from n
Lists of k distinct elements ( ie order matters they’re DISTINCT)
From n elements
n• (n-1)•…•(n-k-1)
(n) . + (n) + ….
(0) . (1)
+ (n)
(n)
=2^n
Lhs = sum of the # subsets of all sizes ( 0,1,2,3,…,n)
0 element subsets +
1 element subsets +
2 element subsets
+…
Can also consider choosing the first element as maximum and choosing the rest
Eg choosing 2 means we get 2, 1 in sets : 2 elements etc
RHS=
Set of n elements has this many subsets
Combination examples:
•medals for 3/100 people
•choosing 3/100 people
•lottery combinations
Combination examples: •medals for 3/100 people ORDER MATTERS 100*99*98 •choosing 3/100 people ORDER DOESNT MATTER binomial coeff 100C3 or 100*99*98 / 6
•lottery combinations
ORDER DOESNT MATTER
Binomial coeff again
5958…5554/65…21. Or 59C6
nC0
nC1
nC0 =0
nC1 =n
How many x^3,s in (1+x)^7
(7C3)
Ie subsets of size 3
Proposition 8: for all n and k (nCk is equal to… (symmetry of pascals triangle)
nCk = nC(n-k)
By pairing complements we can see subsets of size k and unions with their complements ( the remaining n-k elements) form unions of the full set
So form a one to one bijection mapping
Grid routes shortest route from A to B
(n+k)Cn
Choosing n right from n+k
grid is n spaces right and k spaces up
Corresponding to subsets A of {1,…,n+m} with the size of A |A| =n
Example: A to B for 3x4 grid has 7C4 = 7C3 = 35 shortest routes
Proposition 11:
The number of solutions involving non-negative integers x_i of the equation
x₁+x₂+x₃ +… x_k = n
x₁+x₂+x₃ +… x_k = n
Must have solutions which are NON NEGATIVE ( can be 0) and so their sum equals n
Eg k groups of n total where some groups can be 0
This is (n + k -1) C (k-1)
This is the same as grid routes with n horizontal steps with k-1 steps between groups each corresponding to a vertical step= #grid routes (0,0) to (n, k-1)
• choosing k horizontal roads and n moves right regarded as # of moves in a row i, x_i
•in this route there are n+k-1 moves of which any k-1 must be up
Row k.
Row k-1
.
.
Row 2
Row 1
————— n moves accross
For k lines/ rows we have k-1 moves up
Symmetry : (n+k-1) C (n) = (n+k-1) C(k-1)
Solutions of the equation
x₁+x₂+x₃ +… x_k = n where the x_i must be non zero
Taking this as : y₁+y₂+y₃ +…+ y_k = n for POSITIVE integers y_i
Zeros aren’t allowed
Equivalent to (x₁-1) +(x₂-1) +(x₃-1) +…+( x_k-1) = n
x₁+x₂+x₃ +… +x_k = n - k
Equivalent to non negative (zeros allowed) as xi = y_i -1 > 0
So substituting in (n-1) C (k-1)
Equivalence of arranging symbols * & | / dividing into groups of certain sizes
||**| k =4 n=6
Bars divide into groups of sizes x₁,
x₂,…, x_k with their sum equal to n
So number of solutions is the number of placing k-1 symbols in n+k-1 places.
( which we found as (n+k-1)C(k-1) sols to equation x₁+x₂+x₃ +… x_k = n where x_i are …)
Example
Divide n stars into k non-empty groups
Right hand ends of groups are r ₁, r₂, ..,rk
The right hand ends r₁,r₂,… r_(k-1) can be subsets of {1,…,n-1}
(Last one is minimum of 1)
Eg group sizes 2,1,2,1 are r_1 etc
One option is {r ₁, r₂, r ₃} ={2,} which is a subset of {1,2,…,5}
2+1+2+1 = 6
- k =4 n=6
