This course is an advanced (honors) version of "COMP 2711: Discrete Mathematical Tools for Computer Science" which provides a much more in-depth treatment of a wide variety of important mathematical concepts that form the theoretical basis of modern computer science.

Discrete mathematics needed for the study of computer science: sets, functions, propositional logic, predicate logic, rules of inference, proof techniques, pigeonhole principle, basic and generalized permutations and combinations, binomial coefficients, inclusion-exclusion principle, probability theory, Bayes theorem, expectation, variance, random variables, hashing, cryptography and modular arithmetic, Euclid’s division theorem, multiplicative inverse, divisibility, RSA cryptosystem, Chinese remainder theorem, mathematical induction, strong induction and well-ordering property, recursion, recurrence relations, graph representation, isomorphism, connectivity, Eulerian paths, Hamiltonian paths, planarity, graph coloring. Gentle introduction to many discrete mathematical concepts that will appear later in more advanced computer science courses.

• Proofs and Reasoning: Propositional Logic, First-order (Predicate) Logic, Quantifiers, Proof by contradiction, Mathematical Induction, the Pigeonhole Principle, the Invariant Principle, the Extremal Principle, ...
• Set Theory: ZMC, Peano's Axioms, Dedekind Cuts, Relations, Functions, Ordinals and Cardinals, Russel's Paradox, ...
• Enumerative Combinatorics: Rules of Sum and Product, Permutations and Combinations, Inclusion-Exclusion, Catalan and Stirling Numbers, Generating Functions, Recurrence Relations, Double Counting, ...
• Probability Theory: Discrete and Countable Probability Spaces, Axiomatic Probability Theory, Measure Functions, Lebesgue Integrals, Conditional Probability, Independence, Random Variables, Bayesian Reasoning, Expectation, Stochastic Processes, Markov Chains, Markov Decision Processes, ...
• Number Theory: Divisibility, GCD, LCM, Primes, Congruence, Chinese Remainder Theorem, Theorems of Fermat, Euler and Wilson, Quadratic Reciprocity Law, the RSA and El-Gamal Cryptosystems, ...
• Graph Theory: Adjacency, Walks, Paths, Cycles, (Strong) Connectivity, Distance, Trees, Spanning Trees, Bipartite Graphs, Matchings, Shortest Paths, ...
• Game Theory: Combinatorial Games, Sprague-Grundy Theorem, Normal Form (Nash) Games, Nash Equilibria, Correlated Equilibria, Infinite Games on Graphs, ...

• Is there any practical difference between logic / boolean algebra?
• Is Boolean algebra "algebra" because we have XYZ?

• COMP 2711H

  • 👨‍🏫Honors, so we will put infinite pressure on you HAHA
    • 0 coding, 100% theoretical
    • this session: easy (unlike others)
  • ~50%: have A's
    • but thou shalt suffer before getting it!
  • talking about basics: proof, proposition, set of natural numbers

• Propositional logic

  • proposition $:=$ any statement that can be true / false (not both)
    • 👨‍🏫or 1 or 0, as we are CS PPL
    • if you can't assign Boolean value: not a statement
      • e.g. "close the door" not boolean
    • usually using $p,q,r$ for var. names
    • atomic proposition prop. that can't be further broken down
    • for combination: use operators like $\neg$ ("neg")
      • and we often draw truth table to represent the value

• Logical operators

  • negation: $\neg p$ or $\bar{p}$

    • "it is not the case that $p$"

      • read as "not $p$"

    • (!p) ? 1 : 0

    • always opposite of $p$

      $p$	$\neg p$
      1	0
      0	1

    • examples

      • $p=$ "Prof. Amir uses Kali Linux for his desktop"
      • $\neg p=$ "Prof. Amir doesn't use Kali Linux for his desktop"

  • disjunction: $p\vee q$

    • "$p$ or $q$"

    • (p || q) ? 1 : 0

    • 0 only if both $p$ and $q$ are 0

      $p$	$q$	$p\vee q$
      1	1	1
      1	0	1
      0	1	1
      0	0	0

  • conjunction: $p\wedge q$

    • "$p$ and $q$"

    • (p && q) ? 1 : 0

    • 1 only if both $p$ and $q$ are T

    • 👨‍🏫 logical operator: kind of "promise" on condition

      $p$	$q$	$p\wedge q$
      1	1	1
      1	0	0
      0	1	0
      0	0	0

  • exclusive or (xor): $p\oplus q$

    • 1 when exactly one of $p$ and $q$ is T

      • 0 otherwise

    • ((p && !q) || (!p && q)) ? 1 : 0

      • or: (p ^ q) ? 1 : 0 (bit-wise though)

      $p$	$q$	$p\oplus q$
      1	1	0
      1	0	1
      0	1	1
      0	0	0

  • implication

    • cond. state.: $p\to q$

      • = prop. "if $p$ then $q$"

    • $p$: hypothesis / premise

    • $q$: conclusion / consequence / implication

    • (!p || (p && q)) ? 1 : 0

    • 👨‍🏫: any connection in $p,q$: not needed

      • simply depending on its values

    • 👨‍🏫: also, kind of promise

      • "if you are in classroom 2456, then you are Y1 student"

    • can be combined, like: $((p\wedge \neg q)\to r)\to t$

      $p$	$q$	$p\to q$
      1	1	1
      1	0	0
      0	1	1
      0	0	1

    • examples

      • if the moon is made of green cheese, then I have more money than Bill Gates
        • 👨‍🎓 as the hypothesis is false, the true value of conclusion doesn't matter
        • 👨‍🎓 you broke the promise (more like, premise) first!!!

  • 👨‍🏫 dual

    • let $s$ be a statement
    • $s^d$ is the statement obtained by following replacement $$\begin{gathered} \vee \to \wedge \\ \wedge \to \vee \\ T\to F \\ F\to T \\ \text{👨‍🎓 and }\neg \text{ reversed..?} \end{gathered}$$
    • example
      • $s=((x\vee y)\wedge \neg z)\wedge T$
      • $s^d=((x\wedge y)\vee \neg z)\vee F$
      • $s\equiv s^{\prime }⟺s^d\equiv s^{\prime d}$

• Conditional statement

  • necessary / sufficient conditions

    • if $(p\to q)==T$, then
      • $p$: sufficient condition of $q$
      • $q$: necessary condition of $p$
    • examples
      • if I am elected, then taxes will be lowered
      • if elected: sufficient to know "tax will be lowered"
      • if not "tax will be lowered" it must be that I am not elected
    • other ways for $p\to q$
      • if $p$, then $q$
      • $q$ if $p$
      • $q$ when $p$
      • $p$ implies $q$
      • $q$ follows from $p$
      • $p$ is a sufficient condition for $q$
      • $q$ is a necessary condition for $p$
      • $p$ only if $q$ (falsity of $q$: implies falsity of $p$)
        • $\neg q\to \neg p$

  • converse, contrapositive

    • (below: of $p\to q$)

    • converse: $q\to p$

    • contrapositive: $\neg q\to \neg p$

    • inverse: $\neg p\to \neg q$

    • $p\to q$: equivalent to its contrapositive

      $p$	$q$	$p\to q$	$\neg q\to \neg p$
      T	T	T	T
      T	F	F	F
      F	T	T	T
      F	F	T	T

  • bi-conditional statement

    • bicon. state.: $p\leftrightarrow q$

      • = prop. "$p$ if and only if $q$"
      • or: iff

    • T when $p$ and $q$ have the same truth value

      • or $(p\to q)\wedge (q\to p)$

    • equivalent

      • $p$ if and only if $q$
      • $p$ iff $q$
      • $p$ is "necessary and sufficient" for $q$
      • if $p$ then $q$, and conversely

      $p$	$q$	$p\leftrightarrow q$
      T	T	T
      T	F	F
      F	T	F
      F	F	T

• Tautology and contradiction

  • tautology: compound proposition, that is always true
    • no matter values of the prop. vars in it
      • 👨‍🏫: to proof: to show that certain statement is a tautology
  • contradiction: compound proposition, that is always false
  • contingency: compound proposition that is neither a tautology nor a contradiction
  • example
    • $p\vee \neg p$ is a tautology
      • as well as $(p\wedge \neg p)\to p$
      • as premise: always 0
    • $p\wedge \neg p$ is a contradiction
    • $p\to \neg p$ is a contingency

• Boolean algebra

  • conjunction, disjunction, or negation: can be implemented in hardware easily
    • 👨‍🏫 but, how can gates output true when all conjunctions are false?
      • for simplicity, just imagine there is an extra power line

graph TD;
      OR(( ∨ )) --> c_1[ ];
      a_1[ ] --> OR;
      b_1[ ] --> OR;
      AND(( ∧ )) --> c_2[ ];
      a_2[ ] --> AND;
      b_2[ ] --> AND;
      NOT(( ¬ )) --> c_3[ ];
      a_3[ ] --> NOT;

• let's build a simple adder!

  • bit 0 adder: $z_0=x_0\oplus y_0$
    • $\oplus$: defined as $(p\vee q)\wedge \neg (p\wedge q)$
    • read as, "XOR"
  • carry: $x_0\wedge x_0$
  • bit 1: $z_1=x_1\oplus y_1\oplus (x_0\wedge x_0)$
  • 👨‍🎓use 2611 knowledge
  • 👨‍🏫: one thing you can't ask: "where will this course be useful?"

• Logical equivalence

  • compound prop. always having the same truth values: logically equivalent
    • i.e. $p\leftrightarrow q$ is a tautology
    • notation: $p\equiv q$ (or $p\iff q$)
    • $\equiv$: not a logical operator
    • $p\equiv q$: not a compound prop., but a statement!
      • that $p\leftrightarrow q$ is a tautology
    • example: $p\to q\equiv \neg p\vee q$
      • 👨‍🎓 you can use truth table to compare! (manual)
  • use of $\equiv ,\leftrightarrow ,=$
    • $\equiv$: denotes logical equivalence, regardless of var. values
    • $\leftrightarrow$: binary logical operator
    • $=$: not used on propositions
      • only on two mathematical quantities

• Propositional equivalences

  • 👨‍🏫 many algebraic rules also work here!
    • consider $\vee$ as addition, and $\wedge$ as multiplication
  major equivalences

  Name	Equivalence
  Identity laws	$p\wedge T\equiv p$
  	$p\vee F\equiv p$
  Domination laws	$p\vee T\equiv T$
  	$p\wedge F\equiv F$
  Idempotent laws	$p\vee p\equiv p$
  	$p\wedge p\equiv p$
  Double negation laws	$\neg (\neg p)\equiv p$
  Commutative laws	$p\vee q\equiv p\wedge q$
  	$p\wedge q\equiv p\vee q$
  Associative laws	$(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$
  	$(p\vee q)\vee r\equiv p\vee (q\vee r)$
  Distributive laws	$p\vee (q\wedge r)\equiv (p\vee q)\wedge (q\vee r)$
  	$p\wedge (q\vee r)\equiv (p\wedge q)\vee (q\wedge r)$
  De Morgan's laws	$\neg (p\wedge q)\equiv \neg p\vee \neg q$
  	$\neg (p\vee q)\equiv \neg p\wedge \neg q$
  Absorption laws	$p\vee (p\wedge q)\equiv p$
  	$p\wedge (p\vee q)\equiv p$
  Negation laws	$p\vee \neg p\equiv T$
  	$p\wedge \neg p\equiv F$
  Involving cond. states	$p\to q\equiv \neg p\vee q$
  	$p\to q\equiv \neg q\to \neg p$
  	$(p\to q)\wedge (p\to r)\equiv p\to (q\wedge r)$
  	$(p\to q)\vee (p\to r)\equiv p\to (q\vee r)$
  	$(p\to r)\wedge (q\to r)\equiv (p\vee q)\to r$
  	$(p\to r)\vee (q\to r)\equiv (p\wedge q)\to r$
  Involving bicond. states.	$p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$
  	$p\leftrightarrow q\equiv \neg p\leftrightarrow \neg q$
  	$p\leftrightarrow q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)$

• Examples

  • Use De Morgan's laws to express the negations of "Alice will send a secret message or Bob will send a secret message" and "today is Saturday and today is a holiday".
    • Alice & Bob
      • $p$ := Alice will send a secret message
      • $q$ := Bob will send a secret message
      • expr := $p\vee q$
      • $\neg$expr=$\neg (p\vee q)$=$\neg p\wedge \neg q$
      • = "Alice will NOT send a secret message and Bob will NOT send a secret message"
    • Today is...
      • $p$ := today is Saturday
      • $q$ := today is a holiday
      • expr := $p\wedge q$
      • $\neg$expr=$\neg (p\vee q)$=$\neg p\wedge \neg q$
  • Show that $\neg (p\to q)$ and $p\wedge \neg q$ are logically equivalent by developing a series of logical equivalences.
  1. $\neg (p\to q)$
  2. $p\wedge \neg q$
  • Show that $\neg (p\vee (\neg p\wedge q))$ and $\neg p\wedge \neg q$ are logically equivalent by developing a series of logical equivalences.
    1. $\neg (p\vee (\neg p\wedge q))$
    2. =$\neg p\wedge \neg q$
  • Show that $(p\vee q)\to (p\wedge q)$ is a tautology by developing a series of logical equivalences.
    1. $(p\vee q)\to (p\wedge q)$

• Rules of inference

  • theorem: statement that is always true (or: is a tautology)

  • we can write theorem as $h_1\wedge h_2\wedge \cdots \wedge h_n\to c$

  • better, we can define proof

    • you can either fill in $O(2^n)$ size table...
    • or: you use "inference" from existing tautology

  • proof for $h_1\wedge h_2\wedge \cdots \wedge h_n\to c$ is $\alpha$

    • a sequence of statements $$\begin{gathered} p_0:\dots \\ {p}_1:\dots \\ {p}_2:\dots \\ \dots \\ {p}_k=c \end{gathered}$$

  • s.t. for each $p_i$, either is true

    1. $p_i=h_j$ for some $j$
       • i.e. the premise
    2. $p_0\wedge p_1\wedge p2\wedge \cdots \wedge p_{i-1}\to p_i$ is a tautology
       • i.e. can be implied from prev. statements

  • 👨‍🏫 "one rule is actually enough"

    • but we introduce multiple for now

• Rules

  • modus ponens $$\begin{gathered} p \\ p\to q \\ --- \\ q \end{gathered}$$
    • thereafter, you can use $q$ as a tautology
    • or: "$(p\wedge (p\to q))\to q$ is a tautology"
    • 👨‍🏫 just another way of writing a tautology!
    • 👨‍🏫 the actual, only real rule here
  • syllogism $$\begin{gathered} p\to q \\ q\to r \\ --- \\ r \end{gathered}$$
    • or: "$((p\to q)\wedge (q\to r))\to r$" is a tautology
  • modus tollens $$\begin{gathered} p\to q \\ \neg q \\ --- \\ \neg p \end{gathered}$$

• Does predicate / logic have much thing to do with (3-)SAT?
  • 👨‍🏫 No, that's more of an algorithm...

• Other unnamed rules

  • proof by contradiction $$\begin{gathered} \neg p\to F \\ --- \\ p \end{gathered}$$
  • informal "Rule of Equivalence" $$\begin{gathered} p\equiv q \\ p \\ --- \\ q \end{gathered}$$
  "Trivial" ones

1. conjunction $$\begin{gathered} p \\ q \\ --- \\ p\wedge q \end{gathered}$$
2. disjunctive syllogism $$\begin{gathered} p\vee q \\ \neg p \\ --- \\ q \end{gathered}$$
3. modus tollens application $$\begin{gathered} \neg p\to F \\ --- \\ p \end{gathered}$$
4. simplification $$\begin{gathered} p\wedge q \\ --- \\ p \end{gathered}$$
5. addition $$\begin{gathered} p \\ --- \\ p\vee q \end{gathered}$$
6. syllogism - 2 $$\begin{gathered} p\wedge q \\ p\to (q\to r) \\ --- \\ r \end{gathered}$$
7. syllogism of OR $$\begin{gathered} p\to q \\ r\to s \\ p\vee r \\ --- \\ q\vee s \end{gathered}$$
8. reverse syllogism of OR $$\begin{gathered} p\to q \\ r\to s \\ \neg q\vee \neg s \\ --- \\ \neg p\vee \neg r \end{gathered}$$
9. reverse syllogism of OR $$\begin{gathered} p\to r \\ q\to r \\ --- \\ (p\vee q)\to r \end{gathered}$$

• Proof

  • theorem: assuming following conditions $$\begin{gathered} p\to r \\ \neg p\to q \\ q\to s \end{gathered}$$
    • wants to prove: $\neg r\to s$
  • process
    1. $p\to r$ // premise
    2. $\neg r\to \neg p$ // rule of equivalence
    3. $\neg p\to q$ // premise
    4. $\neg r\to q$ // rule of syllogism 2,3
    5. $q\to s$ // premise
    6. $\neg r\to s$ // rule of syllogism 4,5
  • above proof: can be checked by machine!
    • if it understands all symbols, etc.
    • 👨‍🏫 above: a "formal, mathematical" proof
  • and, we can now add a new rule $$\begin{gathered} p\to r \\ \neg p\to q \\ q\to s \\ --- \\ \neg r\to s \end{gathered}$$

• Predicates

  • Boolean statement w/ variable
    • $p(x)$: a predicate if it becomes a prop. when $x$ is replaced by a value
      • 👨‍🏫in our UNIVERSE
  • examples
    • $p(x):=x^2=2$
    • $p(5):=5^2=2$ // false
    • $p(\sqrt{2}):={\sqrt{2}}^2=2$ // true
      • however, if if out "universe" is that of integer
      • no solution for the above exists
  • we can have multiple variables, too
    • $p(x,y):=x>\sqrt{y}$

• Quantifiers

  • universal quantifier $\forall$
    • "forall (in universe) s.t. $p(x)$"
    • $\forall xp(x)$
  • existential quantifier $\exists$
    • "exists (at least one in the universe...) s.t. $p(x)$"
    • $\exists xp(x)$
  • example: $\forall x{x}^2\ge 0$
    • if universe is within the $\mathbb{R}$: true
    • alternatively: $\forall x\in \mathbb{R},x^2\ge 0$

• Rules on $\forall -\exists$

  • $\forall -\exists$ relation
    • $\neg \forall xp(n)\equiv \exists x\neg p(n)$
    • $\exists x\neg p(n)\equiv \neg \forall xp(n)$
  • ⭐distributive law
    • $\forall xp(x)\wedge q(x)\equiv \forall xp(x)\wedge \forall xq(x)$
    • $\exists xp(x)\vee q(x)\equiv \exists xp(x)\vee \exists xq(x)$
    • 👨‍🏫 but not the following!!
      • $\exists xp(x)\wedge q(x)\equiv \exists xp(x)\wedge \exists xq(x)$
      • there can be a $x$ that satisfies "either" one, but not both
      • e.g. $\exists xp(x)\wedge \neg p(x)\not\equiv \exists xp(x)\wedge \exists x\neg p(x)$
        • one on the left: w/ stricter requirement
    • also: following is wrong, for the same reason
      • $\forall xp(x)\vee q(x)\equiv \forall xp(x)\vee \forall xq(x)$
      • there can be a $x$ that only satisfies one predicate
      • e.g. $\forall xp(x)\vee \ne p(x)\not\equiv \forall xp(x)\vee \forall \neg pq(x)$
      • one on the left: w/ looser requirement here

• Natural numbers

  • highschool definition: $\mathbb{N}=\{0,1,2,3,\dots \}$
    • 👨‍🏫 not good! vague, what does the $\dots$ mean?
  • solved by Peano, in 19th century
  • Peano axioms
    1. 0 is a natural number
       • rules below: exists as equality wasn't defined by then...
       1. for every natural number $x$, $x=x$
       2. $\forall x,y\in \mathbb{N}x=y\to y=x$
       3. $\forall x,y,z\in \mathbb{N}x=y\wedge y=z\to x=z$
       4. ...
    2. every natural number $n$ has a successor $s(n)$
    3. $\forall n,m\in \mathbb{N},s(n)=s(m)\to n=m$
       • i.e. $s(n)$ is a one-to-one
    4. $\forall n\in \mathbb{N},s(n)\ne 0$
    5. if $K$ is a set s.t. $0\in K$
       • $\forall n\in \mathbb{N},n\in K\to s(n)\in K$
       • ⭐then $K\supseteq \mathbb{N}$
       • 👨‍🏫 basis of all mathematical induction
  • example: I want to prove $\forall n\in \mathbb{N}p(n)$
    • $\forall n\in \mathbb{N}n\ge 0$
    • let $K$ be the set of all natural no. $n$ s.t. $p(n)$
    • showing two things are sufficient:
      • $p(0)$ holds
      • $\forall n\in \mathbb{N}p(n)\to p(n+1)$

• Definition of +

  • definition will be recursive
  • define some terms
    • $1:=s(0)$
    • $2:=s(s(0))$
    • ...
  • rules
    1. $\forall n,n+0=n$
       • addition of 0 (identity)
    2. $\forall n,m,n+s(m)=s(n+m)$
       • addition of a number, that is successor of something else

• Prove 1+1=2

  • $s(0)+s(0)=s(s(0)+0)=s(s(0))$
  • $2:=s(s(0))$

• Prove 2+2=4

  • 2+2=4 means
    • $ss(0)+ss(0)=ssss(0)$
  • furthermore: $$\begin{array}{rl}ss(0)+ss(0)& =s(ss(0)+s(0))\\ & =s(s(ss(0)+0))\\ & =s(s(ss(0)))\\ & =ssss(0)\end{array}$$

• Definition of $\times$

  • rules
    1. $\forall n,n\times 0=0$
    2. $\forall n,m,n\times s(m)=s\times m+n$
  • 👨‍🏫 can you define division?

• Mathematical induction

  • to show $\phi (n)$ holds $\forall n\in \mathbb{N}$
  • it is sufficient to show
    • $\phi (0)$ holds
      • aka: induction base
    • $\forall n\in \mathbb{N},\phi (n)\to \phi (n+1)$
      • inductive step

• Definition of $\le$

  • $\forall n,m,n\le m⟺\exists x\in \mathbb{N},n+x=m$
  • 👨‍🏫 other, better definitions exist!

• Problems

  • prove that ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$
  • inductive base
    • $\phi (0)={\sum }_{i=1}^{0}i=\frac{0(1)}{2}=0$
  • inductive step $$\begin{array}{rl}\phi (n)& \\ \sum _{i=1}^{n}i& =\frac{n(n+1)}{2}\\ \sum _{i=1}^{n}i+n+1& =\frac{n(n+1)}{2}+n+1\\ \sum _{i=1}^{n+1}i& =\frac{n(n+1)}{2}+n+1\\ \sum _{i=1}^{n+1}i& =\frac{n(n+1)}{2}+2\times \frac{n+1}{2}\\ \sum _{i=1}^{n+1}i& =\frac{(n+2)(n+1)}{2}=\frac{(n+1)(n+2)}{2}\\ \phi (n+1)& \end{array}$$

• Well-ordering principle

  • every non-empty subset A $\subseteq \mathbb{N}$ contains a least / smallest element
  • alternatively: set of $\mathbb{N}$ is "well-ordered" by its natural / magnitude order
    • i.e. $x<y$ in order $⟺\exists n\in \mathbb{N},y=x+n$
      • $n$: can be 0
  • principle: mostly driven from mathematical induction
    • taken as granted from Peano axioms
  • $\mathbb{N}$: the smallest inductive set
    • one can show: set of all natural no. $n$ s.t. "$\{0,\dots ,n\}$ is well-ordered" is inductive
    • and therefore must contain all natural no.
  • 👨‍🎓 ~= reverse direction of mathematical induction?

• Proof by infinite descent

  • aka Fermat's method of descent
  • you can't have an infinite sequence of $n\in \mathbb{N}$ s.t. $\forall i\in \mathbb{N},n_i>n_{i+1}$
  • particular kind of "proof by contradiction"
    • showing: if the statement was to hold a number
    • => it can hold a smaller number
    • => $\mathbb{N}$ has lower bound (0); thus it's wrong
  • relies on the well-ordering principle
    • often used to show that no solution exists

• Problem 2: proof on irrationality of $\sqrt{2}$

  • theorem: $\exists a,b\in \mathbb{N},b\ne 0,\sqrt{2}=\frac{a}{b}$
  • $x,y\in \mathbb{N}\wedge c_a,c_b\in \mathbb{Z}$ let $a=2^x{c}_a$ and $b=2^y{c}_b$
  • $(x=0\vee y=0)\wedge (c_a\perp c_b)\wedge (2\perp c_a)\wedge (2\perp c_b)$ $$\begin{array}{rl}\sqrt{2}& =\frac{a}{b}\\ 2& =\frac{a^2}{b^2}\\ 2b^2& =a^2\end{array}$$
  • i.e. $a^2$ is even => $a$ is also even
    • $a\%2=1\to a^2\%2=1$
    • thus $a^2\%2=0\to a\%2=0$
  • $\exists c,a=2c$
  • $2b^2=4c^2$
  • $b^2=2c$
  • $\exists d,b=2d$
  • $\sqrt{2}=\frac{a}{b}=\frac{2c}{2d}=\frac{c}{d}=\dots$
  • a ever-smaller fraction can be found, infinitely!
    • which is impossible, or is a "contradiction"
  • i.e. no such integer $a,b$ exists!
  • 👨‍🏫 also, keep in mind:

• Proof in well-ordering principle

  • let $A=\{a|\exists b,\sqrt{2}=a/b\}$
  • proof by contradiction
  • step
    • if $A$ is not empty, there must be smallest set from $A$
      • let $a$ be smallest number from $A$
    • however: we can obtain a even smaller member based on $a$
    • thus: it must be the case that $A$ is empty

• Proving: "There are infinitely many prime numbers"

  • let $p_1,p_2,\dots ,p_n$ be all the primes
  • $k=\_1\times p_2\times \cdots \times p_n+1={\prod }_{i=1}^n{p}_i+1$
  • if $k$ is prime: premise is wrong as $k$ is not in the list
  • if $k=a\cdot b$
    • it must be the case that $a$ is a prime that's not on the list
      • (contradiction)
    • or: $a$ can be factorized to $a_1\cdot b_1$
  • and so on, $a_2=a_2\cdot b_2$
  • and $a>a_1>a_2>\dots$
  • however: the sequence must be finite (infinite descent)
    • and the last element of the sequence, must be a prime
    • that is not on the list!
    • q.e.d.

• Problem 4 (Pigeonhole principle)

  • if we have $n$ holes and $n+1$ pigeons are put in them
    • $\exists$ a hole w/ at least two pigeons
    • (for $n\ge 1$)
  • proof by induction
    • base case: starts from $n=1$
      • there is only 1 hole, with 2 pigeons
      • so there is a hole w/ 2 pigeons
    • induction step:
      • for $n+1$-th hole, you can either put
        • 2 pigeons: problem solved
        • 1 pigeon: $\phi (n)$, which is premise
        • 0 pigeon: $\phi (n)$ is sufficient as there are more than $n+1$ pigeons already

• False proof: all cars are the same color

  • base case: when $n=0,1$, $n$ cars have the same color!
  • induction step $$\underset{n\text{ cars}}{\underbrace{\square \square \square }}\square$$ $$\square \stackrel{n\text{ cars}}{\overbrace{\square \square \square }}$$
    • first $n$ cars have the same color
    • and last $n$ cars have the same color too
    • 👨‍🏫 yeah, all crs have the same color!
  • it's wrong when $n=1$!
    • and you can't prove that

• False proof: all man are bald

  • base case: if you have 0 threads of hair, you are bald!
  • inductive case: if a man with $n$ threads of hair is bald, having $n+1$ threads doesn't really make you not bald either!
  • thus, all man (unless they have negative or fractional hair) are bald!

• Problem 5: $n$ players take part in a tournament

  • every player plays against every other player
    • and every game has one winner
  • prove that there exists a permutation $p_1,p_2,\dots ,p_n$
  • s.t. $\forall i\le i\le n-1$ $p_i$ has lost to $p_{i+1}$
  • proof
    • when $n=1$, the case holds
    • if we can sort for $n$ players
      • for $p_{n+1}$, has it won over $p_i{|}_{i=n}^1$?
        • if so, we can place it after $p_i$
      • if there was no place to put $p_{n+1}$, it shows that it has won against no one
        • in which, we can put $p_{n+1}$ in the first place

• Proving induction is valid

  • roadmap
    • show infinite descent $\to$ well ordering (1)
    • show induction holds from well-ordering
  1. let $A\subseteq \mathbb{N}$ be a non-empty set w/o a smallest element
     • pick any $a_0\in A$
     • $A_0=\{a^{\prime }\in A|a^{\prime }<a_0\}$
     • and $A_0$: must be another non-empty set w/o a smallest element
       • and smaller than $A$
       • else: proof ends
     • pick any $a_1\in A_0$
     • $A_1=\{a^{\prime }\in A_0|a^{\prime }<a_1\}$
     • and $A_1$: must be another non-empty set w/o a smallest element
       • and smaller than $A_0$ // infinite descent!
     • thus: based on infinite descent principle, well ordering holds
  2. let $k$ be a set of all of natural number s.t. $0\in K$
     • i.e. trying to prove the fifth Peano axiom
     • $0\in K$
     • $\forall n,n\in K\to n+1\in K$
     • proving: $K=N$; suppose $K\ne N$ (contradiction)
     • $A=\mathbb{N}-K$ // A: non-empty (by definition)
     • let $m$ be the smallest element of $A$
     • $m$ is not in $K$
       • thus, $m-1$ is also not in $K$
       • however, $m-1$ is smaller than $m$, and it also shouldn't be in $K$ either!

• Relationship between three

  • infinite descent: implies well-ordering
  • well-ordering: implies induction
  • 👨‍🏫 can we assume the reverse?

• Well-ordering: implies infinite descent

  • let $A$ be an infinite seq. of numbers
  • then $B=\{x\in \mathbb{N}|\exists i{a}_i=x\}$
  • $B$ has a minimum $b$
    • as $B$ is non-empty
  • and $\exists i,a_i=b$
  • then $a_{i+1}$ cannot be smaller than $a_i=b$
    • as $b$ is the minimum
  • thus, there can't be an infinite sequence of $\mathbb{N}$ that is always decreasing

• Induction: implies well-ordering

  • let $A\subseteq \mathbb{N}\wedge A\ne \varnothing$
  • and does not have minimum (proof by contradiction)
  • $B:=A^c$
  • $p(n):=\forall i\le n,i\in B$
  • to be proven by induction
    • $p(0)$: for $i=0$, $i\in B$
      • unless: $0$ is the minimum element in $\mathbb{N}$
      • and it cannot be in $A$
        • unless: 0 becomes the min. element of $A$
    • assuming $p(n)$,
      • suppose $\forall i\le n+1,i\notin B$
      • which means: $i\in A$
      • however, all elements $\le n$ is not in $A$
      • $n+1$ becomes the minimum element in $A$!
        • thus: the inductive assumption is wrong: and $n+1\in B$
    • finally, $\forall n\in \mathbb{N},\forall i\le n,i\in B$
      • $B=\mathbb{N}$
    • i.e. $A=\varnothing$
      • contradicts our initial assumption: $A$ being non-empty
      • thus, every non-empty subset of $\mathbb{N}$ has a minimum element

• Fibonacci numbers

  $$F_n=\{\begin{array}{l}n=0:0\\ n=1:1\\ n\ge 2:F_{n-1}+F_{n-2}\end{array}$$
  • e.g. $0,1,1,2,3,5,8,13\dots$

• Problem 1

  • $\forall F_1+F_2+\cdots +F_n=F_{n+2}-1$
  • base cases $$\{\begin{array}{l}n=0:0=1-1=0\\ n=1:1=2-1=1\\ n=2:2=3-1=2\end{array}$$
  • prove ${\sum }_{i=1}^{n+1}{F}_i=F_{n+3}-1$ $$\begin{array}{rl}\sum _{i=1}^n{F}_i& =F_{n+2}-1\\ \sum _{i=1}^{n+1}{F}_i+F_{n+1}& =F_{n+2}-1+F_{n+1}\\ \sum _{i=1}^{n+1}{F}_i& =F_{n+2}-1+F_{n+1}\\ \sum _{i=1}^{n+1}{F}_i& =F_{n+3}-1\end{array}$$

• Problem 2

  • $\forall n{F}_1+F_3+F_5+\dots F_{2n-1}=F_{2n}$
  • base case: $F_1=F_2$
  • then: ${\sum }_{i=1}^n{F}_{2i-1}=F_{2n}$
    • ${\sum }_{i=1}^n{F}_{2i-1}=F_{2n}$
    • ${\sum }_{i=1}^n{F}_{2i-1}+F_{2_n+1}=F_{2n}+F_{2_n+1}$
    • ${\sum }_{i=1}^{n+1}{F}_{2i-1}=F_{2n+2}$

• Problem 3

  • $\forall n{F}_2+F_4+F_6+\dots F_{2n}=F_{2n+1}-1$
  • 👨‍🏫 simply subtract the result of (2) from result of (1)

• Problem 4

  • $\forall n\in \mathbb{N},F_n\perp F_{n+1}$
    • i.e. $\gcd (F_n,F_{n+1})=1$
    • or: they are relatively prime
  • with well-ordering & infinite descent
  • $A=\{n\in \mathbb{N}|\gcd (F_n,F_{n+1})\ne 1\}$
    • to be proven: $A=\varnothing$
  • proof by contradiction: assume $A\ne \varnothing$
    • let $m$ be the smallest element of $A$
    • $d:=\gcd (F_m,F_{m+1})\ne 1$
    • $d|F_m\wedge d|F_{m+1}$
      • i.e. $d$ divides both
      • and $d>1$
    • if $F_{m+1}=F_m+F_{m-1}$
      • then also $d|F_{m-1}$
      • $⟹m-1\in A$
      • however: $m$ is supposed to be the "smallest element" in $A$
      • thus: contradiction, and $A$ is empty
  • or: using infinite descent
    • (continued from above) $m-1\in A⟹m-2\in A⟹m-3\in A$...
    • infinite sequence & decreasing -> impossible!
  • also: using induction
    • base case holds: $\gcd (F_0,F_1)=\gcd (F_1,F_2)=1$
    • induction: $\gcd (F_n,F_{n+1})=1⟹\gcd (F_{n+1},F_{n+2}=1)$
      • proof by contradiction
      • $d:=\gcd (F_{n+1},F_{n+2})$ (hopefully $\ne 1$)
      • $d|F_{n+1}\wedge d|F_{n+2}$
      • i.e. $d$ divides both
      • then for $F_{n+2}-F_{n+1}=F_n$, also $d|F_n$
      • but, as $\gcd (F_n,F_n+1)=1,d=1$
  • 👨‍🏫 any of three will work, but just that one will be more human-intuitive!

• Problem 5:

  • $\forall n\ge 1,{\sum }_{i=1}^n{i}^3=({\sum }_{i=1}^n{)}^2$
  • by induction, so base case: $1^3=1^2$
  • assume ${\sum }_{i=1}^n{i}^3=({\sum }_{i=1}^n{)}^2$, then: $$\begin{array}{rl}\sum _{i=1}^{n+1}{i}^3& =\sum _{i=1}^n{i}^3+(n+1{)}^3\\ & =(\sum _{i=1}^{n}i{)}^2+(n+1{)}^3\\ & =(\frac{n(n+1)}{2}{)}^2+(n+1{)}^3\\ & =\frac{n^2(n+1{)}^2}{4}+(n+1{)}^3\\ & =\frac{(n^2+4n+4)(n+1{)}^2}{4}\\ (\sum _{i=1}^{n+1}i{)}^2& =(\frac{(n+1)(n+2)}{2}{)}^2\\ & =\frac{(n+1{)}^2(n+2{)}^2}{4}\\ & =\frac{(n^2+4n+4)(n+1{)}^2}{4}\end{array}$$

• Problem 6

  • let $|A|=n$, then $A$ has $2^n$ subsets
  • base case: $n=0$, then has only 1 subset: $\varnothing$
    • $1=2^0$, so it holds
  • proof by induction
    • let $A$ be a set of size $n+1$
    • $A=\{a_1,a_2,\dots ,a_{n+1}\}$
    • any $B\subseteq A$ s.t. $B\not\ni a_{n+1}$ is of size $n$ too
      • then, $A$ has two groups of subsets, one including $a_{n+1}$ and those that are not
      • each of size $2^n$
      • together: of size $2^{n+1}$

• Problem 7

  • let $A$ be a non-empty finite set
  • let $E=\{B\subseteq A||B|\text{ is even}\}$
  • let $O=\{B\subseteq A||B|\text{ is odd}\}$
  • prove that $|E|=|O|$
  • base case: $n=1$
    • $A=\{a_1\}$
    • $\varnothing \in E$
    • $A\in O$
  • let $A_{n+1}$ be a set of size $n+1$
    • let $A_n\subseteq A_{n+1}$ with $|A_n|=n$
    • $|E_n|=|O_n|$
    • let $x\in A_{n+1}\wedge x\notin A_n$
    • subsets without $x$:
      • odd: $|O_n|$
      • even: $|E_n|$
    • subsets with $x$:
      • odd: $|E_n|$
      • even: $|O_n|$
    • and $|O_n|+|E_n|+|E_n|+|O_n|$

• Problem 8

  • suppose: we have a class $C$ of $n$ students
  • let $A^{+}\subseteq A\subseteq C$
  • in how many ways can we choose $A^{+}$ and $A$?
  • 👨‍🏫
  • if $n=0$
    • $A^{+}=A=C=\varnothing$
  • if $n=1$
    • $C=\{1\}$
    • 3 choices
      • $A^{+}=A=\varnothing$
      • $A^{+}=A=\{1\}$
      • $A^{+}=\varnothing \wedge A=\{1\}$
  • if $n=2$
    • $C=\{1,2\}$
    • 9 choices (as grade of a student is independent of another)
  • assume: for $n$, there are $3^n$ ways
  • induction
    • $C=\{1,2,3,\dots ,n,n+1\}$
    • there are $3^n$ ways to allocate first $n$ students
    • and 3 ways to allocate the last student
    • as they are independent (in this course), there are $3^n\times 3=3^{n+1}$ ways

• Problem 9

  • reducing game / game of Nim with two heaps
  • given $a,b\in \mathbb{N}$
  • players, in turn, choose either $a,b$ and decreases it
    • if one can't make move: then the player loses
  • assuming ideal play
    • if $a=b$ then player 2 wins
    • if $a\ne b$ then player 1 wins
  • and assume $a<b$ as the order doesn't matter
  • base case: $a=b=0$
    • player 2 wins
  • using induction on $n$
    • with $a=b=n+1$
    • if player 1 reduces $a$ to $n$
      • player 2 can also make $b$ to $n$
  • strong induction
    • proving $\forall n\in \mathbb{N}p(n)$
    • consists of:
      • $p(0)$ holds
      • $\forall n,(\forall i\le n,p(i))⟹p(n+1)$
        • i.e. more stuff & requirements
  • prove that player 2 wins $n+1,n+1$
    • $\forall i\le n+1$, player 2 wins $i,i$
    • player 2: can copy player 1's move
      • i.e. player 2 makes $a,b$ equal
  • can also be proven with infinite descent
    • game: ends at some point (i.e. when $0,0$)
    • and player 2 wins it

• Problem 1

  • prison guard
  • prisoner $n,m$ gets to assigned a number ($n,m$)
    • they know what number they were assigned
    • and $|n-m|=1$
  • can say: 1 sentence, only once
    • "I know out number and it's (n,m)"
  • show that: they will be able to come to an answer
  • $i:=\min (n,m)$:
  • base case: $i=0$
    • one with 0 can immediately shout out $(n,m)=(0,1)$
    • solved on day 1
  • base case: $i=1$
    • if either number was 0, the prisoner would have said $(n,m)=(0,1)$
    • however, if no one shouted it on day 1, prisoner w/ no. 1 can know that his/her number is the min. and the other no. is $i+1=2$
    • solved on day 2
  • $p(i)$: if $i=\min (n,m)$, then it will be announced on day $n+1$
  • $\forall i\in \mathbb{N},p(i)⟹p(i+1)$
    • as, if it was $p(i)$, then it would have been announced on day $i+1$
    • it wasn't the case, so the prisoner with $i+1$ can announce $(n,m)=(i+1,i+2)$ on day $i+2$

• Problem 1'

  • a prisoner: supposed to be executed
  • someday next week, but not known
    • 👨‍🏫 and you will be surprised
  • prisoner: cannot be executed on Sunday
    • as he won't be surprised on that day
  • prisoner: cannot be executed on Saturday
    • as he won't be surprised to be so by the end of Friday
  • and so on...
  • prisoner: I ought not to be executed!
  • answer: he was executed on Wednesday, and he was surprised

• Problem 2

  • 2d lattice: all points of form $(x,y)$ where $x,y\in \mathbb{Z}$
  • for each point: has natural number written on it
  • number written on point: will be mean of its neighbors
    • neighbor: i.e. on m
  • prover all the number are equal
  • proof by well ordering
    • $X=$ all numbers assigned to points
      • $X\subseteq \mathbb{N}\wedge X\ne \varnothing$
      • $X$ has a minimum value
    • and the minimum value's neighbors: must all be $m$
      • unless: there must be a neighbor that is bigger than $m$
      • then there also must be a neighbor with natural number smaller than $m$, too

• Problem 3

  • there is a circle w/ circumference 1
  • and there are $n$ cars on its circumference
    • and each can go distance $x_i$, and fuel can be shared
  • if ${\sum }_{i=1}^n{x}_i\ge {\sum }_{i=1}^n{d}_i=1$, there exists a car that can catch & steal others' fuel, and make a full round
  • base case: $n=1$
    • with only 1 car, w/ $x_i>1$, then the car can make a whole round
    • or: ${\sum }_{i=1}^1{x}_i\ge {\sum }_{i=1}^1{d}_i$
  • induction case: $p(n)\to p(n+1)$
    • $d_i$: denotes distance till the next car
    • there exists at least 1, "good" car that can catch another car ($d_i\le x_i$)
      • however, it doesn't mean that the car can make a whole round after the catch
    • 👨‍🏫 idea: removing the "good" car, and making it with $n$ cars only
      • remove the good car $x_i$, and eliminate $d_i$
      • and change fuel of car $i+1$ to $x_{i+1}+x_i-d_i$
      • intuition: if a car could reach car $i$, then it can reach car $i+1$ with this wormhole & fuel change
        • 👨‍🎓 it is, kind of equivalent, considering car $i$ is a "good" car
      • and, still, this subproblem w/ $n$ cars: satisfy ${\sum }_{i=1}^n{x}_i\ge {\sum }_{i=1}^n{d}_i$
  • ⭐👨‍🏫 we don't get to choose the instance of $n+1$ cars, as we must show it holds for all combinations
    • however, we can do so for $n$ cars, as it is the assumption we are having

• Problem 4

  • there are no four positive integers $x,y,z,u$ s.t.
    • $x^2+y^2=3(z^2+u^2)$
  • proof by contradiction
    • assume: assignment s.t. making $(x^2+y^2)$ minimum exists
      • $(x,y,z,u)=(a,b,c,d)$
    • $a^2+b^2=3(c^2+d^2)$
      • RHS: multiple of 3
      • LHS: must also be multiple of 3
        • $a{\equiv }_{3}0⟹a^2{\equiv }_{3}0$
        • $a{\equiv }_{3}1⟹a^2{\equiv }_{3}1$
        • $a{\equiv }_{3}2⟹a^2{\equiv }_{3}1$
      • and sum of two such numbers: must be within $\{0,1,2\}$
        • and $3|a^2+b^2$ only occurs when both numbers are multiple of 3
      • if $3|a^2⟹3|a$
        • $a=3a^{\prime }$
      • if $3|b^2⟹3|b$
        • $b=3b^{\prime }$ $$\begin{array}{rl}{a}^2+b^2& =3(c^2+d^2)\\ 9a^{\prime 2}+9b^{\prime 2}& =3(c^2+d^2)\\ 3a^{\prime 2}+3b^{\prime 2}& =c^2+d^2\\ 3(a^{\prime 2}+b^{\prime 2})& =c^2+d^2\\ c^2+d^2& =3(a^{\prime 2}+b^{\prime 2})\end{array}$$
      • and $c^2+d^2$: smaller then $a^2+b^2$, clearly
      • contradiction: thus no such solution exists

• Problem 5

  • graph problem: a country w/ $n$ cities
  • and exactly 1 road between any two cities
    • and all are 1-way
  • a city $C$: a central city
    • if every other city $C^{\prime }$ can reach $C$ directly / or with 1 stop
  • show that there exists at least 1 central city
  • proof by induction
    • $n=1,2$: it works
    • for $n$ city: all other cities will have road to
      • $c$
      • or other city that has road to $c$
    • by adding a new city $c_{n+1}$
      • if $c_{n+1}$ has road to $c$: $c$ remains the central
      • if $c$ has road to $c_{n+1}$:
        • if $c_{n+1}$ has any road to $c$'s first neighbor: $c$ remains the central
        • else:
          • $c$ and first neighbors of $c$: has direct road to $c_{n+1}$
          • second neighbors of $c$: can access $c_{n+1}$ through first neighbors
          • $c_{n+1}$ is the new central
  • extremal proof
    • count: how many roads are coming in
      • such count: $\in [0,n-1]$
      • i.e. indegree
    • if $c$: a city w/ maximal indegree
      • then $c$ is the capital
    • proof
      • there are first neighbor cities of $c$
      • and other cities
        • if it has road to first neighbors: can access $c$ in two steps
          • doesn't make $c$ not-a-capital
      • $c$ is not capital only when:
        • $c$ and all first neighbors are towards a different city
          • 👨‍🎓 as: if that city had road towards any of first neighbors / $c$, it can reach $c$ easily
            • must be the other direction
          • i.e. if $c$ had $k$ indegree, new city has at least $k+1$ indegree
        • however, it's a contradiction in choice of $c$
          • as $c$ is supposed to be a city w/ maximal indegree

• Counting

  • how many ways is there to do something?

• PA: principle of addition

  • there are 2 points, $a,b$
    • there exists 2 roads, 2 ferry routes, and 1 flight route
    • how many ways? $2+2+1=5$
  • i.e. dividing big set's size into sum of smaller sets' size

• PM: principle of multiplication

  • when noe event is independent of another
  • same city $a,b$
    • but intermediate $c,d$ also exists
    • a-c-d-b in linear order
    • a-c: 2; c-d: 3; d-b: 2 ways
    • total ways of a-b, without going back:
      • $2\cdot 3\cdot 2=12$ ways
  • as long as no. of later choices (not individual cases of later choices) are independent of previous choices, we can simply multiply
  • another way to divide a large set

• Counting permutations

  • prof's notation: $[n]=\mathrm{1..}=n$
  • permutations of $\{1,2,3\}$:
    • $\{1,2,3\},\{1,3,1\},\{2,1,3\},\{2,3,1\},\{3,2,1\},\{3,1,2\}$
    • 6 ways!
  • how many permutation for $n$ numbers?
    • e.g. how many different (linear) queues?
      • use notation $x_n$ to denote permutation ways of $[n]$
    • $x_1=1$
    • $x_n=x_{n-1}\cdot n$
      • i.e. inserting $n$-th person into queue of $n-1$ people
      • $n$ slots to insert!
    • $x_n={\prod }_{i=1}^{n}i=:n!$
    • definition: can be either multiplication / permutation of $[n]$
      • $0!=1$ as there is 1 way of aligning 10 people
  • or, different approach:
    • for $n$ objects
      • how many choices do I have for 1st place?: $n$
      • how many choices do I have for 2nd place?: $n-1$
      • ...
      • how many choices do I have for last place?: $1$
      • total: $n!$
    • 👨‍🏫 note that no. of later choices are independent of previous choices

• Permutations

  • how many queue of length $r$ can we form from $n$ people?
    • ${\prod }_{i=0}^{r-1}(n-i)=:P_r^n=P(n,r)$
    • or: $n!/(n-r)!$
    • 👨‍🏫: double counting: we consider $(a,b)$ and $(b,a)$ as different queue
      • order matters here!
  • or, think of other way
    • it's still $n$-length queue, but the last $n-r$ elements do not matter
      • thus: $n!/(n-r)!$

• Permutations of non-distinct items

  • how many permutations does each word have
    • not necessarily meaningful
    • $HKUST$: all letters are distinct
      • $5!$ ways to order
    • simple: $AABB$
      • there are $4!$ ways to simply display
        • if it was $$A_1{A}_2{B}_1{B}_2$$
      • but order of 2 As and 2 Bs doesn't matter
        • so $2!2!$ ways of double count
      • $\frac{4!}{2!2!}=6$ distinct ways
    • $ABRACADABRA$: some letters appear more than once!
      • 5 A, 2 B, 2 R, 1 C, 1 D
      • all permutations: $\frac{11!}{5!2!2!}$
  • general way
    • there are $t$ alphabets in a word
    • where each letter appears $k_t$ times
    • total no. of permutations: $\frac{({\sum }_{i=1}^t{k}_i)!}{{\prod }_{i_1}^t{k}_i!}$
  • one of the ways we show that a fraction is an integer
    • claim that it is answer to some counting problem
      • all counting problem: has integer solution
  • 👨‍🏫 I'll fail you if you say there are 9.5 ways of counting!!!

• Combinations

  • 👨‍🏫 what if we don't care about the order?
    • e.g. how many subsets of $[n]$ have size $r$
    • notation: $C_r^n,C(n,r),\left(\genfrac{}{}{0ex}{}{n}{r}\right)$
  • equivalent: how many binary seq. of length $n$ have $r$ ones?
    • $=\frac{n!}{(n-r)!r!}$
  • or, a different way
    • $P(n,r)$: no. of different permutation of length $r$ from $[n]$
      • then divide it by $r!$: no. of different ordering of length $r$
    • thus: $\frac{P(n,r)}{r!}=\frac{n!}{(n-r)!r!}$