CS 30: Discrete MathematicsAmit%Chakrabarti%%Binomial%Coef2icients%Sum and Product NotationA%more%precise%shorthand%than%“...”%%nXXXi=1i2= 12+22+32+ ···+ n2nXXXj=12j  1j2=112+322+532+ ···+2n  1n2nYYYi=1i = 1 ⇥ 2 ⇥ 3 ⇥ ···⇥ nPermutations and FactorialsProblem:%How%many%permutations%does%a%list%of%n%distinct%items%have?%)Solution:%Assume%WLOG%that%the%list%is%(1,2,3,...,n).%Permutation:%(a1,a2,...,an),%terms%distinct,%each%ai%∈%{1,2,...,n}.%%Generalized%product%principle:%number%of%choices%is%n%×%(n–1)%×%(n–2)%×%......%×%1%%%%This%product%is%denoted%n! % %[pronounced%“n%factorial”]%=nYYYi=1iCounting Subsets of Fixed SizeProblem:%How%many%k-element%subsets%does%S%have%if%|S|%=%n?%Solution:%Let%U%=%{A%⊆%S%:%%|A|%=%k}.%%We%want%|U|.%%De2ine%T%=%{%(a1,a2,...,ak)%∈%Sk%:%%ai%≠%aj%for%i%≠%j%}%De2ine%MakeSet%:%T%→%U%by%MakeSet(a1,a2,...,ak)%=%{a1,a2,...,ak}.%By%our%previous%result,%this%is%a%(k!)-to-1%correspondence.%Using%the%division%and%product%principles,%%%%This%result%has%a%symbol:% % %[pronounced%“n%choose%k”]%|U| =|T |k!=n(n  1)(n  2) ···(n  k + 1)k!=kYYYj=1n  j +1j✓nk◆Practice With n-choose-k Formula✓n0◆= 1✓n1◆= n✓n2◆=n(n  1)2✓n3◆=n(n  1)(n  2)6✓nn◆=n(n  1) ···(n  n + 1)n!= 1Alternate Formula and SymmetryNotice%the%symmetry%between%k%and%n–k.%%This%shows:%%%Can%you%prove%this%identity%another%way?%Hint:%%Bijection%principle.%✓nk◆=n(n  1) ···(n  k + 1)k!=n(n  1) ···(n  k + 1)k!⇥(n  k)(n  k  1) ···1(n  k)!=n!k!(n  k)!✓nk◆=✓nn  k◆Pascal’s TriangleValues%of%%%%%%%%%%for%small%n%and%k%=%0,1,2,...,n:%%%%%%%%%%Pattern%revealed:n!=!0!→%n!=!1!→!!n!=!2!→!n!=!3!→!n!=!4!→!n!=!5!→!n!=!6!→!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!✓nk◆✓nk◆+✓nk  1◆=✓n +1k◆Pascal’s Identity%Theorem:%For%all%1%≤%k%≤%n:%)Proof)1:%Algebraic%manipulation%(on%whiteboard).%)Proof)2:%Bijective%proof%(hands%in%pockets,%tell%a%story).%The%town%of%Bijectiville%has%population%n+1.%The%town%hall%serves%free%lunch%to%the%2irst%k%citizens%to%take%a%spot%at%its%High%Table.%%When%the%Mayor%is%too%busy%to%join,%clearly%there%are%(n-choose-k)%ways%to%2ill%the%k%spots.%If%the%Mayor%joins,%leaving%k–1%spots,%there%are%(n-choose-(k–1))%ways%to%2ill%the%table.%%Either%way,%the%k%spots%are%2illed%from%the%total%population%of%n+1,%so%there%are%((n+1)-choose-k)%ways%to%do%it.%✓nk◆+✓nk  1◆=✓n +1k◆Pascal’s Identity: Bijective ProofLet%S%be%a%set%with%|S|%=%n+1.%%Let%T%=%{A%⊆%S:%|A|%=%k}.%Choose%x%∈%S.%%Put%• Tinc%=%{A%∈%T:%x%∈%A},%%Texc%=%{A%∈%T:%x%∉%A}. %%%%%(disjoint!)%• U%=%{A%⊆%S–{x}:%|A|%=%k–1}, V%=%{A%⊆%S–{x}:%|A|%=%k}.%Observe:%• The%function%f%:%Tinc→%U%given%by%f(A)%=%A–{x}%is%a%bijection.%• Also,%Texc%=%V.%So,%%%%%%%%%%%%%%|T|%=%|Tinc|%+%|Texc|%=%|U|%+%|V|%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=✓nk  1◆+✓nk◆✓n +1k◆=Exercises: More Bijective ProofsGive%bijective%proofs%of%these%identities:%%✓nk◆=✓nn  k◆nXXXk=0✓nk◆=2nnXXXk=0(1)k✓nk◆=0Binomial Theorem(x+y)2%=%x2%+%2xy%+%y2%(x+y)3%=%x3%+%3x2y%+%3xy2%+%y3%%...%...%...%(x+y)6%=%x6%+%6x5y%+%15x4y2%+%20x3y3%+%15x2y4%+%6xy5%+%y6%%Theorem:))Proof:%(outline,%bijective)%Consider%formation%of%all%x2y4%terms%(x+y)6%=%(x+y)(x+y)(x+y)(x+y)(x+y)(x+y))(x + y)n=nXXXk=0✓nk◆xnkykStudy%Bee%%Concepts:%• Sum%(Σ)%and%product%(Π)%notation%• n-choose-k%notation%• (–1)n,• Pascal’s%triangle%• Bijective%proofs%%Theorems:%• Symmetry%of%binom.%coef2icients%• Pascal’s%identity%• Binomial%theorem%%Skills:%• Finding%patterns%in%binom.%coeffs.%•