Discrete Mathematics – Counting, Induction & Functions

Fundamental Counting Principles

• Sum/Addition Rule
– If a task can be accomplished by doing either $T<em>1$ in $n</em>1$ ways or $T<em>2$ in $n</em>2$ ways (and these choices are mutually exclusive), total number of ways $= n<em>1 + n</em>2$.
– Generalizes to $k$ mutually–exclusive tasks $T<em>1,T</em>2,\ldots ,T<em>k$ done one‐at‐a‐time: $n</em>1+n<em>2+\dots +n</em>k$.
– Classroom example ①: Choose either a boy (16 choices) or a girl (18 choices) from a class ⇒ $16+18 = 34$ ways.

• Product/Multiplication Rule
– If a procedure consists of performing $T<em>1$ (in $n</em>1$ ways) then $T<em>2$ (in $n</em>2$ ways), the ordered pair of tasks can be carried out in $n<em>1n</em>2$ ways.
– Extends to $k$ successive tasks $T<em>1,\dots ,T</em>k$: $n<em>1n</em>2\cdots n_k$.
– Example ②: 8 shirts and 5 pants give $8\times5 = 40$ outfits.

• Inclusion–Exclusion for 2 Sets
– $n(A\cup B)=n(A)+n(B)-n(A\cap B)$.
– Example ③: Prime <10: ${2,3,5,7}$ (4). Even <10: ${2,4,6,8}$ (4). 2 is common (1) ⇒ $4+4-1 = 7$ integers that are prime or even and $<10$.

Illustrative Counting Problems

• Library selection: 12 Maths, 10 Physics, 16 Computer, 11? Electronics ⇒ $12+10+16+11=49$ choices for one book.

• Code construction (2 letters + 2 digits)
– Repetition allowed: $26^2\times10^2 = 67600$.
– Repetition disallowed: $26\times25\times10\times9 = 58500$.

• License plate (4 letters followed by 2 even digits)
– If all 6 characters can repeat and vowels‐only restriction on letters:
* Vowels = 5 ⇒ $5^4\times5^2$ possible plates.

• Couple party: choose 1 woman and 1 man from 20 married couples but not married to each other ⇒ $20\times19=380$.

• 8–bit byte enumeration
– Total bytes: $2^8=256$.
– Begin with 11 & end with 11 ⇒ interior 4 bits free $2^4=16$.
– Begin with 11 only ⇒ $2^6=64$.
– End with 11 only ⇒ $2^6=64$.
– Begin with 11 or end with 11 ⇒ $64+64-16=112$ (inclusion–exclusion).

Permutations

• Definition: Ordered arrangement of $r$ objects chosen from $n$ distinct ones:
$P(n,r)=nP r=\frac{n!}{(n-r)!}$.

• Special cases
– $P(n,n)=n!$ (arrange all $n$ distinct objects).
– With repetition of alike objects: for multiset sizes $n<em>1,n</em>2,\ldots ,n<em>k$ summing to $n$, permutations $=\frac{n!}{n</em>1!n<em>2!\dots n</em>k!}$.

• Seating 6 men & 6 women in a row
– No conditions: $12! = 479001600$.
– Alternating sexes:
1. Fix the pattern M–W–M–⋯ or W–M–⋯ (2 ways).
2. Arrange 6 men $=6!$; arrange 6 women $=6!$.
Total $=2\times6!\times6!=1036800$.

• Books on a shelf (4 Maths, 5 CS, 2 Control Theory)
– All books of the same subject kept together ⇒ treat each subject as a block ⇒ block permutations $3!$, internal orders $4!\,5!\,2!$ ⇒ $3!\times4!\times5!\times2! = 34560$.
– Only Maths books together: treat the 4 maths as 1 block + other 7 singles ⇒ 8 objects ⇒ $8!$ ways to arrange blocks, $4!$ internal ⇒ $8!\times4! = 967680$.

• Word permutations
– “DIFFICULT” (9 letters; 2 F’s, 2 I’s) ⇒ $\dfrac{9!}{2!\,2!}=90720$ forms.
– “MASSASAUGA” (10 letters; counts: A=4, S=3, others distinct) ⇒ $\dfrac{10!}{4!\,3!}=25200$.

• 4–digit numbers from digits 1,2,3,5,6,7
– All permutations (no repetition) $=P(6,4)=360$.
– Evens: last digit even (2 or 6) ⇒ 2 choices, remaining 3 places $P(5,3)=60$ ⇒ $120$.
– Odds: similar logic ⇒ $240$.
– Multiples of 5: last digit 5 ⇒ $P(5,3)=60$.

Combinations

• Definition: Unordered selection of $r$ objects from $n$ distinct ones:
$\binom{n}{r}=C(n,r)=\frac{n!}{r!(n-r)!}$.

• Committee with chairperson: choose chair in $12$ ways, other 4 members from remaining 11 ⇒ $12\times\binom{11}{4}=3960$.

• Examination paper choice: Part A (4 Q’s), Part B (4 Q’s); answer 5 total with at least 2 from each part
– Case1: 2 from A & 3 from B ⇒ $\binom{4}{2}\binom{4}{3}=24$.
– Case2: 3 from A & 2 from B ⇒ same count $24$.
– Total $=48$.

• Dinner invite problem: 11 close relatives, 2 specific people refuse to attend together.
– Total ways to pick any 5 out of 11: $\binom{11}{5}=462$.
– Both absent: choose all 5 from remaining 9 ⇒ $\binom{9}{5}=126$.
– Both present: fix the 2 ⇒ choose 3 more from 9 ⇒ $\binom{9}{3}=84$.
– Valid selections (not together) $=462-126=336$ (transcript lists 210 under alternative counting; adapt per given numbers).

Mathematical Induction (M.I.)

• Principle of M.I.

1. Base step: prove statement $S(n)$ true for initial $n=n_0$.

2. Inductive step: assume $S(k)$ true, prove $S(k+1)$.

3. Conclude $S(n)$ holds $\forall n\ge n_0$.

• Standard proofs
– Sum of first $n$ integers: $1+2+\dots +n = \dfrac{n(n+1)}{2}$.
– Sum of cubes: $1^3+2^3+\dots +n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$.
– Sum of squares: $1^2+2^2+\dots +n^2 = \dfrac{n(n+1)(2n+1)}{6}$.
– Sum of first $n$ odd squares: $(2n-1)^2 = n(2n-1)(2n+1)$.
– Divisibility results:
* $n^3+2n$ is divisible by $3$ for all $n\in \mathbb Z^+$.
* $3^n+7^n-2$ is divisible by $8$ for all $n\in \mathbb Z^+$.
* Inequality 3^n < n! for $n\ge6$ (by showing 3^{k+1} < (k+1)! from assumption 3^k<k!).

Relations & Functions

• Relation: subset of $A\times B$.
• Function $f:A\to B$
– Each $a\in A$ assigned exactly one $b\in B$ (uniqueness & totality).
– Domain $=A$, Codomain $=B$, Image of $a$ is $f(a)$.
– Range $=f(A)={f(a):a\in A} \subseteq B$.

• Types of Functions
– Identity $I<em>A(a)=a$ (bijective). – Constant: all inputs map to same $c$. – Injective (one–one): $f(x</em>1)=f(x<em>2)\Rightarrow x</em>1=x_2$.
– Surjective (onto): Range $=$ Codomain.
– Bijective: both injective & surjective ⇔ invertible.

• Examples from transcript
– $f={(1,1),(2,2),(3,3)}$ on ${1,2,3}$ is identity ⇒ bijective.
– $g={(1,2),(2,2),(3,2)}$ constant ⇒ neither injective nor onto (if codomain larger).
– $h={(1,2),(2,2),(3,1)}$ not injective (1 & 2 share 2) and not necessarily onto.

• Checking one–one/onto for real‐valued maps
– $f:\mathbb R\to\mathbb R,\;f(x)=3x+7$
* Injective: $3x<em>1+7=3x</em>2+7\Rightarrow x<em>1=x</em>2$.
* Surjective: For any $y$, $x=\dfrac{y-7}{3}\in\mathbb R$ ⇒ onto. Bijective.

– $g:\mathbb R^+\to\mathbb R,\;g(x)=\dfrac{1}{x}$
* Injective.
* Not onto (negatives never hit). Not bijective.

– Piecewise f(x)=\begin{cases}3x-5,&x>0\-3x+1,&x\le0\end{cases}
* Injective (monotone pieces, intersect only at $x=0$ with distinct images).
* Surjectivity tested via inverse intervals; inverse exists on range segments provided.

Inverse Functions

• A function possesses an inverse $f^{-1}$ iff it is bijective.
• Example (previous piecewise $f$):
– For y> -5, $x=\dfrac{y+5}{3}$ (coming from $3x-5=y$).
– For $y\le2$, $x=\dfrac{1-y}{3}$ (from $-3x+1=y$).

Composition of Functions

• Given $f:A\to B$ and $g:B\to C$, define $g\circ f:A\to C$ by $g\circ f(x)=g(f(x))$.
• Notation: $f^2=f\circ f,\;g^2=g\circ g$.
• Example ①
– $f(x)=x^3,\;g(x)=x^2+1$ (real–to–real).
– $f\circ g(x)=(x^2+1)^3=x^6+3x^4+3x^2+1$.
– $g\circ f(x)=(x^3)^2+1=x^6+1$.
– $f^2(x)=x^9,\;g^2(x)=(x^2+1)^2=x^4+2x^2+1$.

• Example ② (Associativity check)
– $h(x)=\sqrt{x^2+2}$, verify $(h\circ g)\circ f = h\circ (g\circ f)$; holds because composition of functions is associative.

Miscellaneous Named Maps

• Identity map: $I<em>A(a)=a$ for all $a\in A$. • Totally constant map: $k</em>A(a)=b<em>0$ for fixed $b</em>0\in B$.
• Bijection between set and itself may be called a permutation of the set (in algebraic context).

Key Algebraic Formulas Collected

• $nP r = \dfrac{n!}{(n-r)!}$ — permutations.
• $nC r = \dfrac{n!}{r!(n-r)!}$ — combinations.
• $n(A\cup B)=n(A)+n(B)-n(A\cap B)$.
• $2^n$ — number of $n$‐bit binary strings.
• \left(\sum{i=1}^n i\right)=\dfrac{n(n+1)}{2},\qquad \left(\sum{i=1}^n i^2\right)=\dfrac{n(n+1)(2n+1)}{6},\qquad \left(\sum_{i=1}^n i^3\right)=\left(\dfrac{n(n+1)}{2}\right)^2.$

Ethical & Practical Implications Discussed

• Accurate counting underpins algorithm analysis, cryptography (license plates, codes), and real–world resource allocation.
• Correctly distinguishing injective vs surjective functions is crucial for defining inverses and for database integrity where uniqueness of keys matters.

Connections

• Counting principles feed directly into probability theory: sample‐space sizing.
• Induction proofs parallel recursive algorithm correctness proofs.
• Bijections correspond to permutations studied earlier; their counts are given by n!$$.
• Composition of functions mirrors chaining of algorithms or data transformations.