NOTE: Multiplication/Division and Addition/Subtraction are evaluated left to right (not M before D or A before S).
Number systems, arithmetic fundamentals, inequalities, discrete counting principles, factorial explosion, Catalan numbers, and the Pigeonhole Principle.
Master the foundational concepts that underpin every branch of mathematics — from number classification and arithmetic rules to geometry essentials. This module ensures you have a rock-solid base before moving on to algebra, calculus, and beyond.
| # | Topic | Skill |
|---|---|---|
| 1 | Number Systems | Classify numbers (natural, integer, rational, real) |
| 2 | Arithmetic & PEMDAS | Apply order of operations correctly |
| 3 | Fractions, Decimals & Percentages | Convert and compute across formats |
| 4 | Ratios & Proportions | Solve direct and inverse proportion problems |
| 5 | HCF & LCM | Find HCF/LCM using prime factorization |
| 6 | Divisibility Rules | Quickly check divisibility by 2–11 |
| 7 | Basic Geometry & Mensuration | Calculate area, perimeter, and apply Pythagoras |
| 8 | Inequalities | Solve linear, quadratic, rational, and absolute value inequalities |
Every number you use fits into a hierarchy of number sets: ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ
| Set | Symbol | Examples | Description |
|---|---|---|---|
| Natural | ℕ | 1, 2, 3, 4, ... | Counting numbers |
| Whole | W | 0, 1, 2, 3, ... | ℕ + zero |
| Integers | ℤ | ..., -2, -1, 0, 1, 2, ... | Whole + negatives |
| Rational | ℚ | 1/2, 0.75, 0.333... | p/q where q ≠ 0 |
| Irrational | — | √2, π, e | Non-terminating, non-repeating decimals |
| Real | ℝ | All of the above | Rational ∪ Irrational (entire number line) |
Prime & Composite Numbers:
| Type | Definition | Examples |
|---|---|---|
| Prime | Exactly 2 factors (1 and itself) | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 |
| Composite | More than 2 factors | 4, 6, 8, 9, 10, 12, 14, 15 |
| Special | 1 is neither prime nor composite | 1 |
| Only even prime | 2 is the only even prime number | 2 |
def classify_number(n):
"""Classify a number into its number system categories"""
categories = []
if isinstance(n, int) and n > 0:
categories.append("Natural (ℕ)")
if isinstance(n, int) and n >= 0:
categories.append("Whole (W)")
if isinstance(n, int):
categories.append("Integer (ℤ)")
# Check rational (all ints are rational, and finite decimals)
try:
from fractions import Fraction
Fraction(n)
categories.append("Rational (ℚ)")
except (ValueError, TypeError):
categories.append("Irrational")
categories.append("Real (ℝ)")
return categories
# Examples
for num in [5, -3, 0, 0.75]:
print(f"{num}: {classify_number(num)}")
PEMDAS (Parentheses, Exponents, Multiplication, Division, Addition, Subtraction) — also known as BODMAS (Brackets, Orders, Division, Multiplication, Addition, Subtraction).
| Priority | PEMDAS | BODMAS | Example |
|---|---|---|---|
| 1st | Parentheses | Brackets | (2 + 3) = 5 |
| 2nd | Exponents | Orders | 4² = 16 |
| 3rd | Multiplication & Division | Division & Multiplication | 6 × 3 = 18, 12 ÷ 4 = 3 |
| 4th | Addition & Subtraction | Addition & Subtraction | 5 + 3 = 8, 9 - 4 = 5 |
NOTE: Multiplication/Division and Addition/Subtraction are evaluated left to right (not M before D or A before S).
# Python follows PEMDAS automatically
result1 = 2 + 3 * 4 ** 2 # = 2 + 3 * 16 = 2 + 48 = 50
result2 = (2 + 3) * 4 ** 2 # = 5 * 16 = 80
result3 = 12 / 4 * 3 # = 3 * 3 = 9 (left to right)
result4 = 10 - 3 + 2 # = 7 + 2 = 9 (left to right)
print(f"2 + 3 × 4² = {result1}") # 50
print(f"(2 + 3) × 4² = {result2}") # 80
print(f"12 ÷ 4 × 3 = {result3}") # 9.0
print(f"10 - 3 + 2 = {result4}") # 9
Algebraic Properties:
| Property | Addition | Multiplication |
|---|---|---|
| Commutative | a + b = b + a | a × b = b × a |
| Associative | (a + b) + c = a + (b + c) | (a × b) × c = a × (b × c) |
| Identity | a + 0 = a | a × 1 = a |
| Inverse | a + (-a) = 0 | a × (1/a) = 1 |
| Distributive | a(b + c) = ab + ac |
These three are just different ways to represent the same value:
| Fraction | Decimal | Percentage |
|---|---|---|
| 1/2 | 0.5 | 50% |
| 1/4 | 0.25 | 25% |
| 3/4 | 0.75 | 75% |
| 1/5 | 0.2 | 20% |
| 1/3 | 0.333... | 33.33...% |
Conversion Rules:
from fractions import Fraction
# Fraction operations
a = Fraction(3, 4)
b = Fraction(1, 6)
print(f"{a} + {b} = {a + b}") # 3/4 + 1/6 = 11/12
print(f"{a} × {b} = {a * b}") # 3/4 × 1/6 = 1/8
print(f"{a} ÷ {b} = {a / b}") # 3/4 ÷ 1/6 = 9/2
# Conversions
frac = Fraction(3, 8)
decimal_val = float(frac)
percentage = decimal_val * 100
print(f"Fraction: {frac}") # 3/8
print(f"Decimal: {decimal_val}") # 0.375
print(f"Percent: {percentage}%") # 37.5%
# Percentage problems
total = 800
discount_pct = 15
discount_amt = total * discount_pct / 100
print(f"{discount_pct}% of {total} = {discount_amt}") # 120
print(f"Price after discount = {total - discount_amt}") # 680
Ratio — compares two quantities: a : b = a/b
Proportion — states that two ratios are equal: a/b = c/d
| Type | Relationship | Example |
|---|---|---|
| Direct Proportion | If x increases → y increases | More hours worked → more pay |
| Inverse Proportion | If x increases → y decreases | More workers → less time to finish |
Direct: y = kx (constant k = y/x)
Inverse: y = k/x (constant k = x × y)
# Direct proportion: cost ∝ quantity
price_per_kg = 50
quantities = [2, 5, 10]
for q in quantities:
print(f"{q} kg costs ₹{price_per_kg * q}")
# Inverse proportion: workers × time = constant
# 6 workers take 12 days. How many days for 9 workers?
workers1, days1 = 6, 12
workers2 = 9
days2 = (workers1 * days1) / workers2
print(f"\n{workers1} workers → {days1} days")
print(f"{workers2} workers → {days2:.0f} days") # 8 days
# Dividing in a ratio
# Divide 120 in the ratio 3:5
total = 120
a, b = 3, 5
part_a = total * a / (a + b)
part_b = total * b / (a + b)
print(f"\n120 in ratio 3:5 → {part_a:.0f} and {part_b:.0f}") # 45 and 75
HCF (Highest Common Factor) — largest number that divides both numbers.
LCM (Lowest Common Multiple) — smallest number divisible by both numbers.
Key Relationship: HCF(a, b) × LCM(a, b) = a × b
Method — Prime Factorization:
| Step | Number 36 | Number 48 |
|---|---|---|
| Factorize | 2² × 3² | 2⁴ × 3 |
| HCF | Take minimum powers: 2² × 3¹ = 12 | |
| LCM | Take maximum powers: 2⁴ × 3² = 144 |
TIP: Verify: HCF × LCM = 12 × 144 = 1728 = 36 × 48 ✓
import math
# Built-in HCF/GCD
a, b = 36, 48
hcf = math.gcd(a, b)
lcm = (a * b) // hcf # or math.lcm(a, b) in Python 3.9+
print(f"HCF({a}, {b}) = {hcf}") # 12
print(f"LCM({a}, {b}) = {lcm}") # 144
print(f"Verify: {hcf} × {lcm} = {hcf * lcm} = {a} × {b} = {a * b}")
# Prime factorization
def prime_factors(n):
factors = {}
d = 2
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors
for num in [36, 48, 60]:
pf = prime_factors(num)
factored = " × ".join(f"{p}^{e}" if e > 1 else str(p) for p, e in sorted(pf.items()))
print(f"{num} = {factored}")
Quick mental-math checks — no calculator needed:
| Divisor | Rule | Example |
|---|---|---|
| 2 | Last digit is even (0, 2, 4, 6, 8) | 128 → 8 is even ✓ |
| 3 | Sum of digits divisible by 3 | 123 → 1+2+3 = 6 ÷ 3 ✓ |
| 4 | Last two digits form a number divisible by 4 | 312 → 12 ÷ 4 ✓ |
| 5 | Last digit is 0 or 5 | 245 → ends in 5 ✓ |
| 6 | Divisible by BOTH 2 and 3 | 132 → even & 1+3+2=6 ✓ |
| 8 | Last three digits divisible by 8 | 1016 → 016 ÷ 8 ✓ |
| 9 | Sum of digits divisible by 9 | 729 → 7+2+9 = 18 ÷ 9 ✓ |
| 10 | Last digit is 0 | 350 → ends in 0 ✓ |
| 11 | Alternating sum of digits divisible by 11 | 121 → 1-2+1 = 0 ÷ 11 ✓ |
def check_divisibility(n):
"""Check divisibility by 2-11 with rule explanations"""
results = []
digits = [int(d) for d in str(abs(n))]
# Rule for 2
results.append(("2", n % 2 == 0, f"last digit {digits[-1]} {'is' if digits[-1] % 2 == 0 else 'is not'} even"))
# Rule for 3
digit_sum = sum(digits)
results.append(("3", n % 3 == 0, f"digit sum = {digit_sum}"))
# Rule for 5
results.append(("5", n % 5 == 0, f"last digit is {digits[-1]}"))
# Rule for 9
results.append(("9", n % 9 == 0, f"digit sum = {digit_sum}"))
# Rule for 11
alt_sum = sum(d * (-1)**i for i, d in enumerate(digits))
results.append(("11", n % 11 == 0, f"alternating sum = {alt_sum}"))
print(f"Divisibility of {n}:")
for divisor, is_div, reason in results:
status = "✓" if is_div else "✗"
print(f" By {divisor}: {status} ({reason})")
check_divisibility(132)
print()
check_divisibility(729)
Angle Types:
| Type | Range | Example |
|---|---|---|
| Acute | 0° < θ < 90° | 45° |
| Right | θ = 90° | Corner of a page |
| Obtuse | 90° < θ < 180° | 120° |
| Straight | θ = 180° | A flat line |
| Reflex | 180° < θ < 360° | 270° |
Triangle Classification:
| By Sides | By Angles |
|---|---|
| Equilateral — all sides equal | Acute — all angles < 90° |
| Isosceles — two sides equal | Right — one angle = 90° |
| Scalene — no sides equal | Obtuse — one angle > 90° |
NOTE: Sum of angles in any triangle = 180°
Essential Formulas:
| Shape | Area | Perimeter |
|---|---|---|
| Rectangle | length × width | 2(l + w) |
| Square | side² | 4 × side |
| Triangle | ½ × base × height | a + b + c |
| Circle | π × r² | 2 × π × r |
| Parallelogram | base × height | 2(a + b) |
| Trapezium | ½ × (a + b) × h | a + b + c + d |
Pythagoras Theorem: In a right triangle: a² + b² = c² (where c is the hypotenuse)
Common Pythagorean triplets: (3,4,5), (5,12,13), (8,15,17), (7,24,25)
import math
# Area and perimeter calculations
def rectangle(l, w):
return {"area": l * w, "perimeter": 2 * (l + w)}
def circle(r):
return {"area": math.pi * r**2, "circumference": 2 * math.pi * r}
def triangle_area(base, height):
return 0.5 * base * height
# Examples
rect = rectangle(8, 5)
print(f"Rectangle 8×5: Area = {rect['area']}, Perimeter = {rect['perimeter']}")
circ = circle(7)
print(f"Circle r=7: Area = {circ['area']:.2f}, Circumference = {circ['circumference']:.2f}")
print(f"Triangle (base=10, height=6): Area = {triangle_area(10, 6)}")
# Pythagoras theorem
a, b = 3, 4
c = math.sqrt(a**2 + b**2)
print(f"\nPythagoras: {a}² + {b}² = {a**2} + {b**2} = {a**2 + b**2}")
print(f"Hypotenuse = √{a**2 + b**2} = {c}")
# Verify common triplets
triplets = [(3,4,5), (5,12,13), (8,15,17), (7,24,25)]
for a, b, c in triplets:
valid = a**2 + b**2 == c**2
print(f"({a},{b},{c}): {a}²+{b}²={a**2+b**2}, {c}²={c**2} → {'✓' if valid else '✗'}")
Inequalities compare expressions using relational operators. This section covers solving techniques for various inequality types.
Inequality Symbols:
| Symbol | Meaning | Example |
|---|---|---|
| < | Less than | x < 5 (x is less than 5) |
| > | Greater than | x > 3 (x is greater than 3) |
| ≤ | Less than or equal to | x ≤ 7 (x is at most 7) |
| ≥ | Greater than or equal to | x ≥ 2 (x is at least 2) |
Key Properties:
# Solving linear inequality: 3x - 7 < 8
# Step 1: Add 7 to both sides
# 3x < 15
# Step 2: Divide by 3
# x < 5
def solve_linear_inequality(a, b, c, inequality_type='<'):
"""
Solve ax + b < c (or >, <=, >=)
Returns solution boundary and direction
"""
boundary = (c - b) / a
if a > 0:
direction = '<' if inequality_type in ['<', '<='] else '>'
else:
direction = '>' if inequality_type in ['<', '<='] else '<'
return f"x {direction} {boundary}"
print(f"3x - 7 < 8 → {solve_linear_inequality(3, -7, 8, '<')}") # x < 5.0
print(f"-2x + 4 ≥ 10 → {solve_linear_inequality(-2, 4, 10, '>=')}") # x <= -3.0
Solutions to inequalities are often expressed using interval notation:
| Inequality | Interval | Number Line |
|---|---|---|
| a < x < b | (a, b) | Open circles at both ends |
| a ≤ x ≤ b | [a, b] | Closed circles at both ends |
| a < x ≤ b | (a, b] | Open at a, closed at b |
| a ≤ x < b | [a, b) | Closed at a, open at b |
| x > a | (a, ∞) | Arrow to right |
| x < a | (-∞, a) | Arrow to left |
| x ≥ a | [a, ∞) | Closed circle, arrow right |
| x ≤ a | (-∞, a] | Closed circle, arrow left |
Union of Intervals: Use ∪ to combine disjoint intervals
def interval_to_set(interval_str):
"""Parse interval notation (simplified)"""
examples = {
"(2, 5)": "2 < x < 5",
"[2, 5]": "2 ≤ x ≤ 5",
"(2, 5]": "2 < x ≤ 5",
"[2, 5)": "2 ≤ x < 5",
"(-∞, 3)": "x < 3",
"[3, ∞)": "x ≥ 3",
"(-∞, -2) ∪ (3, ∞)": "x < -2 or x > 3"
}
return examples.get(interval_str, "Unknown format")
for interval in ["(2, 5)", "[-1, 4)", "(-∞, 0)"]:
print(f"{interval} means: {interval_to_set(interval)}")
To solve quadratic inequalities like ax² + bx + c > 0:
Steps:
import numpy as np
def solve_quadratic_inequality(a, b, c, inequality_type='>'):
"""
Solve ax² + bx + c > 0 (or <, >=, <=)
Returns intervals where inequality holds
"""
# Find roots using quadratic formula
discriminant = b**2 - 4*a*c
if discriminant < 0:
# No real roots - parabola doesn't cross x-axis
if a > 0:
return "All real numbers" if inequality_type in ['>', '>='] else "No solution"
else:
return "No solution" if inequality_type in ['>', '>='] else "All real numbers"
sqrt_d = np.sqrt(discriminant)
x1 = (-b - sqrt_d) / (2*a)
x2 = (-b + sqrt_d) / (2*a)
critical_points = sorted([x1, x2])
return f"Critical points: x = {critical_points[0]}, {critical_points[1]}"
# Example: x² - 5x + 6 > 0
# Factors: (x - 2)(x - 3) > 0
print(f"x² - 5x + 6 > 0")
print(solve_quadratic_inequality(1, -5, 6, '>'))
print("Solution: x < 2 or x > 3, i.e., (-∞, 2) ∪ (3, ∞)")
# Example: x² - 4x + 4 ≤ 0
# Factors: (x - 2)² ≤ 0
print(f"\nx² - 4x + 4 ≤ 0")
print("Solution: x = 2 only (single point)")
Sign Analysis: For (x - 2)(x - 3) > 0:
| Interval | (x - 2) | (x - 3) | Product | Satisfies > 0? |
|---|---|---|---|---|
| x < 2 | Negative | Negative | Positive | ✓ |
| 2 < x < 3 | Positive | Negative | Negative | ✗ |
| x > 3 | Positive | Positive | Positive | ✓ |
Solution: x ∈ (-∞, 2) ∪ (3, ∞)
Rational inequalities have the form P(x)/Q(x) < 0, > 0, ≤ 0, or ≥ 0.
Critical Points:
Wavy Curve Method (Sign Chart Method):
def analyze_rational_inequality():
"""
Solve: (x - 1)(x + 2) / ((x - 3)(x + 1)) > 0
Critical points:
- Numerator zeros: x = 1, x = -2 (open circles since >)
- Denominator zeros: x = 3, x = -1 (always open - undefined)
Sign chart (right to left):
Interval | Sign | Satisfies > 0?
x > 3 | + | ✓
1 < x < 3 | - | ✗
-1 < x < 1 | + | ✓
-2 < x < -1 | - | ✗
x < -2 | + | ✓
"""
print("Solve: (x - 1)(x + 2) / ((x - 3)(x + 1)) > 0")
print()
print("Critical Points:")
print(" Numerator zeros: x = -2, 1 (open circles)")
print(" Denominator zeros: x = -1, 3 (undefined)")
print()
print("Sign Chart (right to left):")
print(" x > 3: + ✓")
print(" 1 < x < 3: - ✗")
print(" -1 < x < 1: + ✓")
print(" -2 < x < -1: - ✗")
print(" x < -2: + ✓")
print()
print("Solution: (-∞, -2) ∪ (-1, 1) ∪ (3, ∞)")
analyze_rational_inequality()
Example Problem:
Solve: (x² - 4) / (x - 1) ≥ 0
Solution:
Solution: [-2, 1) ∪ [2, ∞)
Type 1: |x| < a (or |x| ≤ a)
Type 2: |x| > a (or |x| ≥ a)
General Form: |f(x)| < a
import numpy as np
def solve_abs_inequality(a, inequality_type='<'):
"""
Solve |x| < a or |x| > a
"""
if a <= 0:
if inequality_type in ['<', '<=']:
return "No solution" if a < 0 else "x = 0"
else:
return "All real numbers except 0" if a == 0 else "All real numbers"
if inequality_type == '<':
return f"-{a} < x < {a}, i.e., (-{a}, {a})"
elif inequality_type == '<=':
return f"-{a} ≤ x ≤ {a}, i.e., [-{a}, {a}]"
elif inequality_type == '>':
return f"x < -{a} or x > {a}, i.e., (-∞, -{a}) ∪ ({a}, ∞)"
else: # >=
return f"x ≤ -{a} or x ≥ {a}, i.e., (-∞, -{a}] ∪ [{a}, ∞)"
print(f"|x| < 5 → {solve_abs_inequality(5, '<')}")
print(f"|x| ≥ 3 → {solve_abs_inequality(3, '>=')}")
# More complex: |x - 3| < 7
print(f"\n|x - 3| < 7")
print("Rewrite: -7 < x - 3 < 7")
print("Add 3: -4 < x < 10")
print("Solution: (-4, 10)")
Special Cases:
| Inequality | Solution | Reason |
|---|---|---|
| |x| ≥ 0 | All real numbers | Absolute value is always non-negative |
| |x| < 0 | No solution | Absolute value cannot be negative |
| |x| > -5 | All real numbers | Absolute value is always ≥ 0 > -5 |
When asked to find integer solutions in an interval:
Steps:
def find_integral_solutions(inequality_solution, interval_type='open'):
"""
Find integer solutions in a given interval
"""
# Example: Find integers in (-2, 5]
if interval_type == '(-2, 5]':
integers = [-1, 0, 1, 2, 3, 4, 5]
elif interval_type == '[-3, 4)':
integers = [-3, -2, -1, 0, 1, 2, 3]
elif interval_type == '(-∞, 3)':
integers = "All integers < 3"
else:
integers = []
return integers
print(f"Integers in (-2, 5]: {find_integral_solutions('ineq', '(-2, 5]')}")
print(f"Count: {len(find_integral_solutions('ineq', '(-2, 5]'))}")
print(f"Sum: {sum(find_integral_solutions('ineq', '(-2, 5]'))}")
# Example: Largest integer in (-∞, 7)
print(f"\nLargest integer in (-∞, 7): 6")
print(f"Smallest integer in (2, ∞): 3")
Example: Find the sum of all integral values of x satisfying: -3 ≤ x < 5
Solution: Integers: -3, -2, -1, 0, 1, 2, 3, 4 Sum = -3 + (-2) + (-1) + 0 + 1 + 2 + 3 + 4 = 4
| Concept | Key Formula / Rule |
|---|---|
| PEMDAS order | Parentheses → Exponents → Mult/Div → Add/Sub |
| Fraction → Decimal | Divide numerator by denominator |
| Percentage | (part / whole) × 100 |
| Direct Proportion | y = kx (k is constant) |
| Inverse Proportion | y = k/x (xy = constant) |
| HCF | Product of lowest common prime powers |
| LCM | Product of highest prime powers |
| HCF × LCM | = a × b |
| Triangle angle sum | 180° |
| Pythagoras | a² + b² = c² |
| Circle area | πr² |
| Rectangle area | length × width |
| Inequality reversal | Multiply/divide by negative reverses sign |
| Interval (a,b) | a < x < b (open interval) |
| Interval [a,b] | a ≤ x ≤ b (closed interval) |
| Interval (a,b] | a < x ≤ b (half-open, open on left) |
| Interval [a,b) | a ≤ x < b (half-open, closed on left) |
| |x| < a | -a < x < a |
| |x| > a | x < -a or x > a |
| Wavy Curve | Factor → Critical points → Sign chart → Select intervals |
Interactive:
Videos:
Counting is the foundational heartbeat of Discrete Mathematics and Computer Science. From determining the computational complexity of an algorithm and analyzing state spaces in artificial intelligence to ensuring cryptographic security through massive key spaces, mastering rigorous counting principles is indispensable.
This section covers foundational Discrete Mathematics (IIT Ropar — Prof. Sudarshan Iyengar), exploring fundamental counting laws, exponential growth, combinatorial explosion, Catalan numbers, and the Pigeonhole Principle.
Why do computer scientists care about counting? In continuous mathematics (calculus), we measure smooth quantities like time, velocity, and area. In computer science, everything is digital, discrete, and finite.
Computers operate on discrete states:
Core Insight: If you can count the number of states in a problem, you can immediately determine whether an exact solution can be computed in milliseconds, years, or millennia.
Consider a standard sheet of paper of thickness 0.1 mm (10⁻⁴ m). Every time you fold the paper in half, the thickness doubles.
| Number of Folds (n) | Number of Layers (2ⁿ) | Total Thickness | Real-World Comparison |
|---|---|---|---|
| 0 | 2⁰ = 1 | 0.1 mm | Single sheet of paper |
| 1 | 2¹ = 2 | 0.2 mm | Cardstock |
| 7 | 2⁷ = 128 | 1.28 cm | Small notebook |
| 14 | 2¹⁴ = 16,384 | 1.64 meters | Height of an adult |
| 20 | 2²⁰ = 1,048,576 | 104.85 meters | Height of Big Ben / 30-story building |
| 30 | 2³⁰ ≈ 1.07 × 10⁹ | 107.37 km | Crosses the Kármán Line into outer space |
| 42 | 2⁴² ≈ 4.40 × 10¹² | 439,804 km | Reaches the Moon (Moon distance: ≈ 384,400 km) |
| 51 | 2⁵¹ ≈ 2.25 × 10¹⁵ | 225,179,981 km | Reaches the Sun (Sun distance: ≈ 149,600,000 km) |
def paper_fold_thickness(num_folds: int, base_thickness_mm: float = 0.1) -> float:
# Calculates thickness in meters after n folds
thickness_meters = (base_thickness_mm / 1000.0) * (2 ** num_folds)
return thickness_meters
for folds in [10, 20, 30, 42, 51]:
m = paper_fold_thickness(folds)
km = m / 1000.0
print(f"Folds: {folds:2d} | Layers: 2^{folds:<2d} | Thickness: {km:,.2f} km")
Takeaway: Exponential functions (2ⁿ) grow faster than any polynomial function (nᵏ). What begins deceptively small quickly eclipses astronomical scales.
A standard 3 × 3 × 3 Rubik's cube has 6 colored faces, 8 corner pieces, and 12 edge pieces. How many valid configurations can be reached by turning the faces?
Total Valid Configurations = (8! × 3⁷ × 12! × 2¹¹) / 2 = 43,252,003,274,489,856,000 ≈ 4.33 × 10¹⁹
43 Quintillion, 252 Quadrillion States
God's Number: In 2010, mathematicians and computer scientists proved using supercomputers that every single one of these 43 quintillion states can be solved in 20 moves or fewer.
When arranging n distinct objects in a line, the number of permutations is n! = n × (n-1) × (n-2) × ... × 1.
| n | n! | Approximate Value | Computational Context |
|---|---|---|---|
| 5 | 120 | 1.2 × 10² | Instantaneous |
| 10 | 3,628,800 | 3.63 × 10⁶ | 3.6 million operations (< 1 ms) |
| 15 | 1,307,674,368,000 | 1.31 × 10¹² | 1.3 trillion (few seconds on modern CPU) |
| 20 | 2,432,902,008,176,640,000 | 2.43 × 10¹⁸ | ≈ 77 years on a 1 GHz processor |
| 25 | 15,511,210,043,330,985,984,000,000 | 1.55 × 10²⁵ | Longer than the age of the Universe |
| 52 | 52! (Deck of cards) | 8.06 × 10⁶⁷ | More than atoms in our Galaxy |
Standard 52-card deck:
52! ≈ 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000
Every time you thoroughly shuffle a deck of cards, it is virtually 100% certain
that exact sequence of 52 cards has NEVER existed in human history.
Given n cities, finding the shortest round-trip route by brute-force checking all (n-1)! / 2 routes becomes physically impossible for n ≥ 30, motivating the need for dynamic programming and approximation heuristics.
If a first task can be performed in m distinct ways, and a second task can be performed in n distinct ways, and the two tasks cannot be done simultaneously (they are mutually exclusive / disjoint), then performing either the first task or the second task can be done in:
Total Ways = m + n
In set-theoretic terms: |A ∪ B| = |A| + |B| (when A ∩ B = ∅)
If the tasks or sets have common elements (A ∩ B ≠ ∅): |A ∪ B| = |A| + |B| − |A ∩ B|
A university student can choose a computer science project from one of 3 lists: List A has 15 AI projects, List B has 12 Cybersecurity projects, and List C has 8 Web projects. No project appears in more than one list. How many choices does the student have?
Total Choices = 15 + 12 + 8 = 35 choices
If a procedure can be broken down into a sequence of two independent stages, where Stage 1 has m possible outcomes and Stage 2 has n possible outcomes regardless of the choice in Stage 1, then the total number of ways to complete the procedure is:
Total Ways = m × n
In set-theoretic terms: |A × B| = |A| × |B|
Extended to k sequential stages: Total Ways = n₁ × n₂ × n₃ × ... × nₖ
Bitstrings of Length n:
Each bit has 2 choices (0 or 1).
2 × 2 × ... × 2 (n times) = 2ⁿ
A 32-bit integer can represent 2³² = 4,294,967,296 unique values.
Password Search Space: A password of length 8 containing lowercase letters, uppercase letters, and digits (26 + 26 + 10 = 62 characters): Possible Passwords = 62⁸ = 218,340,105,584,896 ≈ 2.18 × 10¹⁴
def calculate_search_space(charset_size: int, length: int) -> int:
return charset_size ** length
lower_only = calculate_search_space(26, 8) # 26^8
alphanumeric = calculate_search_space(62, 8) # 62^8
full_ascii = calculate_search_space(94, 8) # 94^8
print(f"Lowercase (26^8): {lower_only:,}")
print(f"Alphanumeric (62^8): {alphanumeric:,}")
print(f"Full ASCII (94^8): {full_ascii:,}")
| Feature | Permutation P(n, r) | Combination C(n, r) = Cₙʳ |
|---|---|---|
| Core Question | In how many ways can we arrange r items from n? | In how many ways can we select r items from n? |
| Order Matters? | YES (e.g. Password, Race Finishers: 1st, 2nd, 3rd) | NO (e.g. Committee, Hand of cards, Team roster) |
| Formula | P(n, r) = n! / (n−r)! | C(n, r) = n! / (r!(n−r)!) = P(n, r) / r! |
| Relationship | P(n, r) = r! × C(n, r) | C(n, r) = C(n, n−r) |
If you have n objects where n₁ are of type 1, n₂ of type 2, ..., and nₖ of type k: Permutations = n! / (n₁! × n₂! × ... × nₖ!)
Example: Arrangements of letters in "SUCCESS" (Total 7 letters: 3 S, 2 C, 1 U, 1 E): Arrangements = 7! / (3! × 2! × 1! × 1!) = 5040 / (6 × 2) = 420
The Catalan Numbers form one of the most celebrated integer sequences in combinatorial mathematics, arising naturally across dozens of computer science structures.
The sequence begins: C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, C₆ = 132, C₇ = 429, ...
Cₙ = 1/(n+1) × C(2n, n) = (2n)! / ((n+1)! × n!)
Balanced Parentheses Strings (Dyck Words): Number of valid strings with n pairs of opening and closing parentheses:
() → C₁ = 1()(), (()) → C₂ = 2((())), (()()), (())(), ()(()), ()()() → C₃ = 5Full Binary Trees with n+1 Leaves: Number of structurally distinct binary trees with n internal nodes is exactly Cₙ.
Monotonic Lattice Grid Paths (Dyck Paths): Number of grid paths from (0, 0) to (n, n) moving only Right or Up that never cross above the diagonal line y = x.
Polygon Triangulations: Number of ways a convex polygon with n+2 sides can be cut into triangles by non-intersecting diagonals.
import math
def catalan_number(n: int) -> int:
# Computes the n-th Catalan number C_n = (2n)! / ((n+1)! * n!)
return math.comb(2 * n, n) // (n + 1)
print("First 10 Catalan Numbers:")
for i in range(10):
print(f"C_{i} = {catalan_number(i)}")
Basic Statement: If n+1 or more pigeons are placed into n pigeonholes, then at least one pigeonhole must contain two or more pigeons.
Generalized Statement: If N objects are placed into k boxes, then at least one box must contain at least: ⌈N / k⌉ = ceil(N / k) objects
import math
from itertools import permutations, combinations
# 1. Rule of Sum & Product Demo
departments = {"Engineering": 120, "Science": 85, "Arts": 60}
print("Total single reps (Rule of Sum):", sum(departments.values()))
print("Total committee pairs (Eng x Sci):", 120 * 85)
# 2. Permutations vs Combinations
items = ['A', 'B', 'C', 'D']
r = 2
perms = list(permutations(items, r))
combs = list(combinations(items, r))
print(f"
P({len(items)}, {r}) = {len(perms)} arrangements:")
print(perms)
print(f"
C({len(items)}, {r}) = {len(combs)} selections:")
print(combs)
# 3. Pigeonhole Principle Function
def min_pigeons_per_hole(total_items: int, total_holes: int) -> int:
# Returns the guaranteed minimum items in the fullest container.
return math.ceil(total_items / total_holes)
print(f"
100 students distributed into 12 grades guarantees at least: {min_pigeons_per_hole(100, 12)} students in one grade.")