CS 30: Discrete MathematicsAmit%Chakrabarti%%Basic%Counting%Principles%Counting ProblemsHow%many%people%are%signed%up%on%this%course’s%canvas%page?%• Students%∪!Staff%• |Students|%=%37%• |Staff|%=%7%%Answer:%37%+%7%=%44.%Sum PrincipleBasic%sum%principle:%• If%A%and%B%are%disjoint:%|A%∪!B|%=%|A|%+%|B|.%%Extended%sum%principle:%• If%A1,%A2,%…,%Ak%are%pairwise%disjoint:%%|A1%∪%A2%∪!…%∪!Ak|%=%|A1|%+%|A2|%+%…%+%|Ak|.%%Extended Sum Principle: ApplicationExchange%sort%algorithm%(pseudocode)for i = 1 to n-1: for j = i+1 to n: if A[i] > A[j]: exchange A[i] and A[j]%%How%fast%is%this?%How%many%comparisons?%%SimpliRication:%record%comparison%“A[i] > A[j]”%as%pair%(i,%j).%Extended Sum Principle: ApplicationHow%many%pairs%(i,%j)%occur%below?for i = 1 to n-1: for j = i+1 to n: [...]%S1%=%{%(1,2),%(1,3),%(1,4),%…,%(1,n)%}%S2%=%{%(2,3),%(2,4),%…,%(2,n)%}%…%…%Sn–1%=%{%(n–1,%n)%}%%Total:%|S1%∪%S2!∪%…!∪%Sn–1|%=%(n–1)%+%(n–2)%+%…%+%1%=%n(n–1)/2.%|S1|%=%n–1%|S2|%=%n–2%…%…%|Sn–1|%=%1%General (Non-Disjoint) UnionsS%=%set%of%all%current%Dartmouth%students%A%=%{s%∈!S:%s%has%registered%for%CS%30}%B%=%{s%∈!S:%s%has%registered%for%CS%75}%C%=%{s%∈!S:%s%registered%for%CS%30%or%CS%75}%%|A|%=%37,%%|B|%=%25%|C|%=%|A%∪!B|%=%37%+%25%???%%What%if%I%told%you%|A%∩%B|%=%3%?%%Sum PrincipleBasic%sum%principle:%• If%A%and%B%are%disjoint:%|A%∪!B|%=%|A|%+%|B|.%%Extended%sum%principle:%• If%A1,%A2,%…,%Ak%are%pairwise%disjoint:%%|A1%∪%A2%∪!…%∪!Ak|%=%|A1|%+%|A2|%+%…%+%|Ak|.%%Generalized%sum%principle:%• For%all%A%and%B:%|A%∪!B|%=%|A|%+%|B|%–%|A%∩%B|.%Another Counting ProblemDartmouth%invited%to%send%a%delegation%of%one%student%and%one%professor%to%the%International%Awesomeness%Convention.%%How%many%ways%to%choose?%• Students%×%Professors%• |Students|%=%4500%• |Professors|%=%650%Product PrincipleBasic%product%principle:%• For%all%A%and%B:%|A%×!B|%=%|A|%×%|B|.%%Extended%product%principle:%• For%all%A1,%A2,%…,%Ak:%%|A1%×%A2%×!…%×!Ak|%=%|A1|%×%|A2|%×%…%×%|Ak|.%%Counting Telephone NumbersThe%North'American'numbering'plan'(NANP)%says:%a%telephone%number%has%a%3-digit%area%code,%a%3-digit%ofRice%code,%and%a%4-digit%station%code.%%There%are%some%restrictions%on%the%digits.%• Let%X%denote%a%digit%from%0%through%9.%• Let%N%denote%a%digit%from%2%through%9.%• Let%Y%denote%a%digit%that%is%0%or%1.%• In%the%old%plan%(1960s)%the%format%was%NYX-NNX-XXXX.%• In%the%new%plan,%the%format%is%NXX-NXX-XXXX.%How%many%different%telephone%numbers%are%possible%under%the%old%plan?%Under%the%new%plan?%Counting Telephone NumbersRules:!• Let%X%denote%a%digit%from%0%through%9.%• Let%N%denote%a%digit%from%2%through%9.%• Let%Y%denote%a%digit%that%is%%0%or%1.%• In%the%old%plan%(in%use%in%the%1960s)%the%format%was%NYX-NNX-XXXX.%• In%the%new%plan,%the%format%is%NXX-NXX-XXXX.%Solution:%%Use%the%product%principle.%There%are…%• 8 × 2 ×%10 =%160%area%codes%with%the%format%NYX.'• 8 ×%10 ×%10 =%800%area%codes%with%the%format%NXX.''• 8 ×%8 ×%10 =%640%ofRice%codes%with%the%format%NNX.'''• 10 ×%10 ×%10 ×%10 =%10,000%station%codes%with%the%format%XXXX.''Old%plan:%160 ×%640 ×%10,000 =%1,024,000,000%telephone%numbers.%New%plan:%800 ×%800 ×%10,000 =%6,400,000,000%telephone%numbers.%%Counting Variable Names in Minimal BASICRules:!• At%most%two%characters.%• Each%character%is%either%an%uppercase%letter%or%a%digit.%• The%Rirst%character%cannot%be%a%digit.%Solution:!• V1%=%{v%:%v%is%a%one-character%variable%name}.%• V2%=%{w%:%w%is%a%two-character%variable%name}%%“=”%{x:%x%is%a%letter}%×%{y%:%y%is%a%letter%or%a%digit}.%• V1%∩%V2%=%∅.%• #names%=%|V1%∪!V2|%=%|V1|%+%|V2|%=%26%+%26%×%36%=%962.%%Bijection PrincipleFor%Rinite%sets:%If%there%exists%a%bijection%f%:%A%→%B%then%|A|%=%|B|. % %[We’ve%seen%this%before.]%• V2%=%{w%:%w%is%a%two-character%variable%name}%• L%=%{letters},%D%=%{digits}%• We%said%V2%“=”%L%×%(L%∪!D)%• Actually:%there%is%a%natural%bijection%from%V2%to%L%×%(L%∪!D).%%“AA”%⟼%(A,A)% %“AB”%⟼%(A,B)%%“FX”%⟼%(F,X) % %“J2”%⟼%(J,2) % %etc.%Bit StringsA%3-bit%string%is%a%sequence%of%3%bits:%• 000,%001,%010,%011,%100,%101,%110,%111%• (0,0,0),%(0,0,1),%(0,1,0),%(0,1,1),%(1,0,0),%(1,0,1),%(1,1,0),%(1,1,1)%• Elements%of%{0,1}%×%{0,1}%×%{0,1}%=%{0,1}3%%An%n-bit%string%is%a%sequence%of%n%bits:%• 00…000,%%00…001,%%00…010,%%………,%%11…111%• Elements%of%{0,1}%×%…%×%{0,1}%=%{0,1}n'• Problem:%How%many%n-bit%strings%in%all?%%Use%product%principle:%answer%=%|%{0,1}n'|%=%2n.'Counting the Power SetProblem:%Determine%|P(S)|%in%terms%of%|S|.%Assume%S%Rinite.%Let%n%=%|S|.%List%all%elements:%S%=%{e1,%e2,%…,%en}.%We’ll%deRine%a%bijection%f%:%P(S)%→%{0,1}n%as%follows:%• for%A%∈%P(S),%let%f(A)%=%(b1,%b2,%…,%bn),%where%• for%each%i:%%bi%=%1%if%ei%∈%A,%%and%bi%=%0%if%ei%∉!A.%%Why%bijection?%Because%this%f%has%an%inverse:%• f–1(b1,%b2,%…,%bn)%=%{ei%∈%S:%bi%=%1}.%%Bijection%principle:%|P(S)|%=%|%{0,1}n%|%=%2n.%%%%%%Super-important!'Subsets of Size 2Let%T%=%{1,2,…n}.%Let%U%=%{A%⊆%T:%|A|%=%2}.%What%is%|U|?%%(1,1) (1,2) (1,3) (1,4) … (1,n)(2,1) (2,2) (2,3) (2,4) … (2,n)(3,1) (3,2) (3,3) (3,4) … (3,n)… … …(n,1) (n,2) (n,3) (n,4) … (n,n)%How%many%pairs%above?%• Can’t%quite%use%product%principle.%• Not%what%we%wanted%to%count%anyway.%Generalized Product PrincipleNeed%to%make%a%sequence%of%k%choices:%(a1,%a2,…,%ak).%• n1%ways%to%choose%a1;%• for%each%a1,%there%are%n2%ways%to%choose%a2;%• for%each%(a1,%a2),%there%are%n3%ways%to%choose%a3;%• …%…%…%• for%each%(a1,%a2,%…,%ak–1),%there%are%nk%ways%to%choose%ak;%%Then%there%are%n1n2n3…nk%ways%to%choose%the%sequence.%%Subsets of Size 2: SolutionLet%T%=%{1,2,…n}.%Let%U%=%{A%⊆%T:%|A|%=%2}.%What%is%|U|?%%(1,1) (1,2) (1,3) (1,4) … (1,n)(2,1) (2,2) (2,3) (2,4) … (2,n)(3,1) (3,2) (3,3) (3,4) … (3,n)… … …(n,1) (n,2) (n,3) (n,4) … (n,n)%• Generalized%product%principle:%#%pairs%=%n(n-1)%• 2%pairs%for%every%subset%A%in%U,%%so%|U|%=%n(n-1)/2.%k-to-1 CorrespondenceThis%function%is%a%3-to-1%correspondence%564231xyA%function%f%:%A→B%such%that%∀%b∈B:%|{a:%f(a)=b}|%=%k'Division