[SOLVED] CS Problem 19

Problem 19
Use the Binomial Theorem to prove the following identities
(a)
n n j=0 j
= 2n (b)
n k=1
(1)k
n k
= 1

The General Inclusion-Exclusion Principle

Inclusion-Exclusion on 3 sets
|AB| = |A|+|B||AB|
|AB C| = |A|+|B|+|C||AB||AC||B C|+|AB C|

Problem 20
How many permutations of the 26 letters of the alphabet do not contain any of the strings fish, rat or bird?

Inclusion-Exclusion on n sets
|A1 A2 An|
= |A1|+|A2|+|An|
|A1 A2||A1 A3||An1 An|
+|A1 A2 A3|+|A1 A2 A4|++|An2 An1 An|
+(1)n+1|A1 A2 An|
n
= (1)k+1 |Ai1 Aik|
k =1 1i1 <