Discrete Mathematics – Counting, Induction & Functions

Fundamental Counting Principles

• Sum/Addition Rule
– If a task can be accomplished by doing either T1 in n1 ways or T2 in n2 ways (and these choices are mutually exclusive), total number of ways = n1 + n2.
– Generalizes to k mutually–exclusive tasks T1,T2,\ldots ,Tk done one‐at‐a‐time: n1+n2+\dots +nk.
– 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 T1 (in n1 ways) then T2 (in n2 ways), the ordered pair of tasks can be carried out in n1n2 ways.
– Extends to k successive tasks T1,\dots ,Tk: n1n2\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 n1,n2,\ldots ,nk summing to n, permutations =\frac{n!}{n1!n2!\dots nk!}.

• 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 IA(a)=a (bijective). – Constant: all inputs map to same c. – Injective (one–one): f(x1)=f(x2)\Rightarrow x1=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: 3x1+7=3x2+7\Rightarrow x1=x2.
* 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: IA(a)=a for all a\in A. • Totally constant map: kA(a)=b0 for fixed b0\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.