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
Example: there are n seats in a row in a doctors waiting room. There are k patients who want to choose sears with no two adjacent. In how many ways can the k seats be chosen
Example 13
We are choosing k seats out of n however
—|p ₁——|p₂————|n
Let x_i = # free seats directly to the LH of p_i
We then have x_1, x_2 ,…,x_k
But we also have the RH of p_k up to the edge giving the total n seats ( however we have the free number of seats as n-k)
The sum of these includes SEATS BETWEEN not including their own seat so must equal n-k
So we have
x₁+x₂+x₃ +… x_k + x_(k+1) = n-k
Where the x_i have to be larger than 1( POSITIVE) except for x_1 and x_(k+1), which can be 0 (NON NEGATIVE)
So subsitutiting y_i -1 for those postituve and y_i for the non negative
y_1 + … y_k+1 = n-k -( k-1) = n-2k +1
Sub in solution from previous proposition (n-2k+1) + k -1 Choose (k+1) -1 (n-k+1) C ( k)
Example 14: of the lottery combinations 52057474 which proportion have at least two of their numbers consecutive
This can be found by finding which proportion have no two consecutive numbers
—-|x_1—-|2-|3-|4—-|5—|6——59
This relates to the previous example in seating k people in n seats with no two adjacent=
Choosing k out of n-k seats st lhs are positive except first and RH of last
=
Subsets A of {1,..,59} |A| =6 st at least two consecutive
Choosing k numbers out of 59 st no two adjacent
54C6 possibilities of No adjacent
So 59C6 -54C6 are adjacent combinations
Example 16:
Let m and n be integers with 1 ≤ m ≤ n
By considering choosing m meme era from {1,2,3,..,n} and by looking at the highest choice show that
nCm =
(n-1)C(m-1) + (n-2)C(m-1) + (n-2)C(m-1) + (n-3)C(m-1) +…
+ (m-1)C(m-1)
= from k=m to n Σ (k-1)C(m-1)
For example choosing 3 from 16 chapters = listing with maximum or lowest first to avoid repetition:
Eg 15C2 of the triples begin with 1…
… 13C2 begin with 3 ( eg could be {3,4,5} or {3,7,9})
…
2C2 begin with a 14 ( only choice is {14,15,16})
Summing these gives all possibilities
= the sum of each collection with the lowest element as k ( for k=1,2,….,16)
To choose subset of a size choose max element, eg A with max m |A| =4 . After m we have 3 more elements in {1,..,m-1} —> m-1 C 3 ways
Hence we sum for m=4,5,..8
8C4 = 3C3 + 4C3 + ..+ 7C3
Max is 4, 5,…, 8
For A as above A= B U{m} for some B which is a subset in {1,…m-1}. So the possibilities of B = (m-1)C (k-1) |B| = k-1
Example 17: total of numbers
1
1 2
1 2 3
1 2 3 4
. . . . . . ... .
1 2 3 4 ... N1+2+ …+7 = 8C2
=Average
Found also by
1+2+..+7 = 1C1 + 2C1 +..+ 7C1
=8C2 by previous example
( this is choosing 1, choosing 2 or 1, choosing 1,2 or 3…. which is equal to 1, 2,3,.. choices )
Hence 1+ 2+..+ N = (N+1)C2
For N of these rows we are summing one less each time, hence we have
(N+1)C2 + (NC2) + (N-1)C2+..+ 2C2
Which equals (N+2)C3 by example 16 For N rows
(summing members of sets by first choosing the highest element)
Example 18:
Counting nested subtriangles pointing upwards
We use the previous triangle
1 12 123 ... 123..N In each sub triangle Size T we write the numbers of triangles that have T as the bottom right corner
For each row there are the numbers corresponding to the triangles but counting them all they correspond to how many so we just sum them (draw pictures to see this)
This is (N+2)C3 That’s the total number of sub triangles is the sum of all the numbers
Example 19 the Fibonacci sequence (f_n) st n is bigger than or equal to 1
is defined by
f_1 =1, f_2 = 2
f_(n+2) = f_(n+1) + f_n. For all n bigger than or equal to 1
show that
f_n = (nC0) + (n-1)C1 + (n-2)C2 +…
= sum from k=0 of (n-k)Ck
By induction:
claim
Example 20: Mark n different points on the circumference of a circle. Each pair of points is joined by a straight line in such a way that no three of the lines meet at a point inside the circle.
•How many lines are there
•how many internal crossings
•how many regions
- nC2 each pair is joined, so subsets of size to of all the points ( as order DOESNT matter)
- nc4 each intersection corresponds to any 4 points so correspond to subsets of size 4
- R-C-L stays constant
R = ^ + nC2 + nc4
Adding new line splits regions it crosses in half and crossings are added but only corresponding to two other lines
(Notes explain subsets)
Extra examples:
C
