Discrete Structure207910 marksNumerical: inclusion-exclusion countingInclusion and exclusion principle
Why do we need principle of inclusion and exclusion? How many ways can we express the four character words ending with a digit and beginning three are lowercase alphabets. Be sure that none of the character can be repeated. Using induction, show that 3n - 1 is multiple of 2 for n geq 1. [5+5]
Why do we need principle of inclusion and exclusion? How many ways can we express the four character words ending with a digit and beginning three are lowercase alphabets. Be sure that none of the character can be repeated. Using induction, show that $3^n - 1$ is multiple of 2 for $n \geq 1$. [5+5]
- Word length: 4 characters - Positions 1, 2, 3: lowercase alphabets (26 available) - Position 4: a digit (10 available: 0-9) - Constraint: no character repeated - Induction claim: $3^n - 1$ is a multiple of 2 for $n \geq 1$ --- When we count elements in a union of overlapping sets, simply adding...