What is discrete mathematics?

It also known as Mathematics for computer science.

Discrete mathematics is the study of numerable sets, it distinct from others. – such as integers, graphs, and statements in logic.

• Numerable. From Latin numerābilis.
  • (mathematics) In one to one correspondence with the set of natural integers.

Collins Dictionary

Wiki

https://www.merriam-webster.com/dictionary/numerable

https://www.dictionary.com/browse/numerable?s=t

https://wikidiff.com/countable/numerable#:~:text=As adjectives the difference between,able to be counted%3B countable.

Discrete. "separate, distinct from others," late 14c., from Old French discret, discre, and directly from Latin discretus "separated;" see discreet. Related: Discretely; discreteness. https://www.etymonline.com/word/discrete

Resources

Requisites

• Minimum formal math.

• Logic.

Unrequisites

• Calculus

• Coding skills

Foundations topics

• Philosophical logic and Philosophy of logic

• Set theory

  • Sets

• Mathematical logic

• Combinatorics

  • Combinations

  • Permutations

  • Partitions

• Graph theory

  Graphs

  Networks

• Number theory

  • Integers

  • Transcendental numbers

  • Diophantine approximation

  • p-adic analytics

  • Function fields

• Algebraic structures

  • Boolean algebra

  • Relational algebra

  • Algebraic coding theory

  • Formal languages

• Discretization

  • Numerical analysis

Applications

• Discrete calculus

  • Sequences

  • Recurrence relation

• Discrete probability

• Discrete geometry

  • Discrete collections

• Operations research

  • Linear programming

  • Optimization

  • Queuing theory

  • Scheduling theory

  • Network theory

  • Continous-time Markov process

• Game theory

  • Decision theory

  • Utility theory

  • Social choice theory

  • Game theory

• Topology

  • Combinatorial topology

  • Topological graph theory

• Information theory

  • Coding theory

  • Analog coding

  • Analog signals

  • Analog encryption

• Theoretical computer science

  • Automata theory

  • Formal languages

  • Computational geometry

Sets

Definitions

Level 1.

Collection. A group of objects of one type that have been collected by one person or in one place. Oxford dictionary.

Object. The objects are sometimes referred to as elements or members. Elements are unique.

Level 2.

Group. A number of people or things that are located close together or are considered or classed together. Oxford dictionary.

Level 3.

Number - The content of a statement of number is an assertion about a concept. [source: The Foundations of Arithmetic, §55, Engl.transl. page 67].

How to use sets?

$\text{TAG is the set of all elements such that element checks properties}$.

Finite sets. E.g. $A=\{\text{1,2,3,4}\}$

Either infinite or large finite sets. E.g. $A=\{x|x\text{ is positive, even integer} \}$

Number sets

Worked examples

• Show that $A=\{1\}\times \{1,2\}\subseteq B=\{1\}\times\{1,2,3\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  By inspection

  $A=\{(1,1),(1,2)\}$, $B=\{(1,1),(1,2),(1,3)\}$

  $A\subseteq B$ since every element of $A$ is an element of $B$.

• Show that $A=\{2n|n\in Z^+\}\subseteq B=\{n|n\in Z\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  Let $x\in A$, $x\in Z^+$ because $Z^+$ is closed under the operation of multiplication. $x\in Z$ since $Z^+\subseteq Z$ .

• Show that $A=\{1,2,3\}\nsubseteq B=\{\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  but $\{\}$ iff $\forall x.x \notin \{\}$, so the consequent always is $False$, hence $A\nsubseteq B$.

• Show that $A=\{1,2,3,4\}\nsubseteq B=\{n|n\in A \land n+m=8 \text{ for some } m\in C\}$, $C=\{5,6,7,8\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  $1\in A \implies 1\notin B$, so $A\nsubseteq B$.

• In a group of students, each student is taking a mathematics course or a computer science course or both. One-fifth of those taking a mathematics course are also taking a computer science course, and one-eighth of those taking a computer science course are also taking a mathematics course. Are more than one-third of the students taking a mathematics course?

  $C:\text{computer science students}$, $M:\text{mathematics course students}$

  We know $\dfrac{|C\cap M|}{|C|}=\dfrac{1}{5}$, $\dfrac{|C\cap M|}{|M|}=\dfrac{1}{8}$ (1), but

  $|U|=|C\cup M|=|C|+|M|-|C\cap M|$

  $1=\dfrac{|C|}{|U|}+\dfrac{|M|}{|U|}-\dfrac{|C\cap M|}{|U|}$ (2)

  By 1

  $\dfrac{1}{5}|C|=\dfrac{1}{8}|M|$

  $|C|=\dfrac{5}{8}|M|$

  We’ll substitute in (2)

  $1=\dfrac{5|M|/8}{|U|}+\dfrac{|M|}{|U|}-\dfrac{|M|/8}{|U|}$

  $1=\dfrac{12|M|/8}{|U|}$

  $\dfrac{|M|}{|U|}=\dfrac{8}{12}=\dfrac{2}{3}\ge\dfrac{1}{3}$

• Let C be a circle and let D be the set of all diameters of C. What is ∩ D? (Here, by “diameter” we mean a line segment through the center of the circle with its endpoints on the circumference of the circle.)

  If

  $D=\{\{p_{11},p_{12},p_{13},...,Center,...\},\{p_{21},p_{22},p_{23},...,Center,...\},\{p_{31},p_{32},p_{33},...,Center,...\},...\}$

  then

  $\cap D=\{Center\}$

• Let P denote the set of integers greater than 1 ($P=\{x|x\in Z\land x>1\}$). For i ≥ 2, define $X_i=\{ik|k\in P\}$. Describe $P-\bigcup_{i=2}^\infty X_i$.

  $$P-\bigcup_{i=2}^\infty X_i=\{2,3,4,...\}-\{2k|k\in P\}\cup\{3k|k\in P\}...\\ =\{2,3,4,...\}-\{4,6,8,10,12,...\}\cup\{6,9,12,15,...\}\cup\{8,12,16,20,...\}...$$

  $\bigcup_{i=2}^\infty X_i$ describes composite numbers since $X_i$ describes $i$ multiples, so

  $=P-\text{composite numbers}=\{x|(x\in Z \land x>1)\land x\notin\text{composite numbers} \}\\ =\text{prime numbers}$

Mathematical logic

Key ideas

Logic is the basis of all reasoning.

A statement or proposition is a declarative sentence that is either true or false, but not both. Remember structure no content.

• Don't use "preposition" as synonymous with "statement". A preposition is a word such as 'by', 'for', 'into', or 'with' which usually has a noun group as its object. Collins.

• Other views of propositions. A proposition is the meaning expressed by statements.

A predicate can be understood as a proposition whose truth depends on the value of one or more variables.

Truth tables

• Created by Charles Sanders Peirce. Popularized by Ludwig Wittgenstein in his Tractatus Logico-Philosophicus.

See "truth"

Truth table generator

When you wish to provide a conclusion (or proof in mathematics), you must use chain statements throughout logical consequences (or connectives, methods, and pieces of evidence) from a base set of previous results – such as axioms, theorems, and definitions.

value judgment

• The following statements are primitive prepositions

  • Cogito.

  • Sum.

  • $2+3=5$

  • $1+1=3$

  • P=NP This is either true or false (but not both), but you don't know.

  • for all $x\in R$, $x>0$ then $x^2>0$

  • Sun leaves tomorrow.

  • She loves him.

  💡

  Actually, whether sentence is a preposition while the sentence matches the definition.

• Moreover, the definition does exclude statements such as

  • Read 'Cogito ergo sum' in Discourse on the Method. (command)

  • Let's go to the beach tomorrow. (proposal)

  • God'll help you! (exclamation)

  • $2+3=5?$ (question)

  • $P(x):=x+4=6$ (indeterminate declarative sentence). It's a predicate.

  • if $x>0$, then $x^2>0$

  • $f(x)=x^2$ (indeterminate declarative sentence)

  • This sentence is false. Contradictions are not statements. (indeterminate statement).

You gonna use variables to represent prepositions, thus as you use letters in algebra. e.g.

Logical formulas

Worked examples

1=-1?

Pythagorean theorem

• Every polynomial ax^2+bx+c has two roots over C.

  $root:ax^2+bx+c=0$

Problem Set

Proofs

What is the proof?

Proof. A finite sequence of statements (called well-formed formulas in the case of a formal language), each of which is a previous result -axiom, an assumption, experiments, or theorems- in the sequence by a rule of inference.

Axiom. Simple postulate or assumption based on a priori knowledge and free contradictions.

Theorems. Important true statements.

Lemma. Preliminary statements.

Corollary. Statements that follows few logical steps from theorem.

Developing mathematical methods to verify programs and systems remains an active research area.

Good proofs

• State your game plan.

• Keep a linear flow.

• A proof is an essay, not a calculation.

• Avoid excessive symbolism.

• Revise and simplify.

• Introduce notation thoughtfully.

• Structure long proofs.

• Be wary of the “obvious.”

• Finish.

Methods

Proof by perfect induction o Proof by exhaustion

Proof of a Boolean theorem through perfect induction.

Simple induction

We know by Modus Ponens:

The principle of induction says

$\forall n P(n+1)$ use $\forall n P(n)$ when $\forall n P(n)\implies \forall n P(n+1)$ but the same to simple $P(n+1)$if always is true then $P(n)$ is always true.

Worked example.

• $\forall n \text{ }n\in N \text{, } P(n):\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}$

  $$\text{Base case:}P(0):0 =0\\ \text{Inductive Hypothesis: Assume that }P(n):\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2} \text{ is true}\\ \text{Inductive step: We need to prove }P(n+1):\sum_{i=0}^{n+1}i=\dfrac{(n+1)(n+2)}{2}$$

  $$\forall n [\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}]\implies \\\forall n [\sum_{i=0}^{n+1}i=\\ \sum_{i=0}^{n}i+(n+1)=\\\dfrac{n(n+1)}{2}+(n+1) =\\ \dfrac{(n+1)(n+2)}{2} ]\\$$

  Therefore

  $$\forall n [\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}]\implies \forall n [\sum_{i=0}^{n+1}i=\dfrac{(n+1)(n+2)}{2} ]\\ \text{ iff } \sum_{i=0}^{n+1}i=\dfrac{(n+1)(n+2)}{2}$$

• $\forall n \text{ }n\in N \text{ }n>0 \text{, } P(n):n^3\le n^2$

  $$\text{Base case: }P(1):1\le1 \\ \text{Inductive Hypothesis: Assume that }P(n):n^3\le n^2 \text{ is true }\\ \text{Inductive step: We need to prove }P(n+1):(n+1)^3\le (n+1)^2$$

  Because $n^3\ge 0,1\ge1,3n^2\ge2n^2$, $3n\ge2 n$

  $$\forall n [n^3\le n^2]\implies \forall n [n^3+3n^2+3n+1\ge n^2+2n+1]\\ \implies \forall n [(n+1)^3\ge (n+1)^2]\\$$

  Our theorem is false since

  $$\forall n [n^3\le n^2] \implies \forall n [(n+1)^3\ge (n+1)^2]\\ \text{iff } (n+1)^3\le (n+1)^2$$

  our argument is always false.

• $\forall n \text{ }n\in N \text{ } \text{, } P(n):\dfrac{d^n}{dx^n}x^k=n!x^{k-n}$

  $$P(0):\dfrac{d^0}{dx^0}x^k=x^k\\ P(n):\dfrac{d^n}{dx^n}x^k=n!x^{k-n}\\ P(n+1):\dfrac{d^{n+1}}{dx^{n+1}}x^k=(n+1)!x^{k-(n+1)}\\ \dfrac{d^n}{dx^n}x^k=n!x^{k-n}\implies \\\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{d}{dx}\dfrac{d^{n}}{dx^{n}}x^k=\dfrac{d}{dx}(n!x^{k-n})=n!(k-n)x^{k-n-1}$$

  $$\forall n [\dfrac{d^n}{dx^n}x^k=n!x^{k-n}] \implies \forall n [\dfrac{d^{n+1}}{dx^{n+1}}x^k=n!(k-n)x^{k-n-1} ]\\ \text{iff } \dfrac{d^{n+1}}{dx^{n+1}}x^k=(n+1)!x^{k-(n+1)}$$

  Our argument is valid, but it is always false.

• $\forall n,k, \text{ }n\in N \text{ } \text{, } P(n):\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}$

  $$P(0):\dfrac{d^0}{dx^0}x^k=\dfrac{k!}{(k-0)!}x^k=x^k\\ P(n):\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}\\ P(n+1):\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}\\ \dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}\implies \\\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{d}{dx}\dfrac{d^{n}}{dx^{n}}x^k=\dfrac{d}{dx}\dfrac{k!}{(k-n)!}x^{k-n}=\dfrac{k!}{(k-n)!}(k-n)x^{k-(n+1)}=\\\dfrac{k!}{(k-n)(k-n-1)!}(k-n)x^{k-(n+1)}=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}$$

  As

  $$\forall n [\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}] \implies \forall n [\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}]\\ \text{iff } \dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}$$

  Our argument is valid and it happen be always true.

https://web.stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf

https://math.stackexchange.com/questions/2926239/when-we-can-use-mathematical-induction-and-when-we-cant

https://www.purplemath.com/modules/inductn2.htm

Boolean Algebra

California State University

Proof of a Boolean theorem through perfect induction

Zermelo-Fraenkel Axioms

Our Axioms

Mathematical data types

Counting

Sums and Asymptotics

Cardinality Rules

The Bijection Rule

Bijection := one-to-one correspondence

Each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

What does it mean to write |A| = n?

It means that there is a bijection f : A → {1, . . . , n}

MIT OpenCourseWare. 2016. 3.3.3 Counting with Bijections: Video. YouTube. Retrieved May 25, 2021 from https://www.youtube.com/watch?v=n0lce1dMAh8‌

The Bijection Rule or Equinumerosity

Let S and T be two finite sets. If there exists one-to-one correspondence (or bijection) between them, from S to T, if and only if $|S|=|T|$ i.e. S and T have the same number of elements. This is taken as the definition.

https://www.cs.colostate.edu/~cs220/summer19/slides/16_bijection_rule.pdf

Counting Sequences

Multiplication Principle or Product Rule

$P_1\times P_2\times ... \times P_n=\{(p_1,p_2,...p_n)|p_1\in P_1,p_2 \in P_2,...,p_n\in P_n\}=\text{all sequences}$ called Cartesian product.

Thus, if $P_1,P_2,\cdots ,P_n$ are finite sets, then

For example, if $A=\{x,y,z\}$ and $B=\{1,2,3\}$

$A\times B=\{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)\}$

$|A\times B|=|A|\cdot|B|=3 \cdot 3=9$

Key ideas

• When we're counting since cardinality $|A|$ is more important than the set $A=\{a_0,a_1,...,a_n\}$. We will ignore writing it.

• No decision might be part b of the set. When your problem says about optional something. $A=\{a_0,a_1,...,a_n,noA\}$

• If repetitions are allowed, $|A|^{repetitions}$

• If repetitions are not allowed, You'd remove the last used element such that $|A|\cdot(|A|-1)\cdot(|A|-2)...$

• $|U|=|A|+|A^c|$

Product Rule Worked examples

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of one appetizer and one beverage?

  $|Appetizers|=2$, $|Beverages|=4$

  $|Dinners|=2\cdot4=8$

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of an optional appetizer, one main course, and an optional beverage?

  $|Main\text{ } courses|=3$

  $|optional \text{ } appetizers|=|appetizers|+|no\text{ }appetizer|=2+1=3$

  $|optional \text{ }bevarages|=|bevarages|+|no \text{ }bevarage|=4+1=5$

  $|Dinners|=|main\text{ } courses| \cdot |optional \text{ } appetizers| \cdot |optional \text{ }bevarages|=3\cdot3\cdot5=45$

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of one appetizer, one main course, and an optional beverage?

  $|Main\text{ } courses|=3,$$|Appetizers|=2,$ $|Beverages|=5$

  $|Dinners|=3\cdot2\cdot5=30$

• A man has eight shirts, four pairs of pants, and five pairs of shoes. How many different outfits are possible?

  $Outfit=\{(shirt,pair\text{ } of\text{ }pants,pair\text{ } of\text{ }shoes)|shirt\in Shirts,pair\text{ } of\text{ }pants \in Pairs\text{ } of\text{ }pants,pair\text{ } of\text{ }shoes \in Pair\text{ } of\text{ }shoes\}$

  $|Shirts|=8$, $|Pairs\text{ } of\text{ }pants|=4$ and, $|Pairs\text{ } of\text{ }shoes|=8$

  $|Outfit|=|Shirts|\cdot|Pairs\text{ } of\text{ }pants|\cdot |Pairs\text{ } of\text{ }shoes|=8\cdot 4\cdot5=160$

• Two dice are rolled, one blue and one red. How many outcomes are possible?

  $Outcomes=\{(color,position)|color\in Colors,position\in Positions\}$

  $|Colors|=2$, $|Positions|=6$

  $|Outcomes|=2\cdot6=12$

• The Braille system of representing characters was developed early in the nineteenth century by Louis Braille. The characters, used by the blind, consist of raised dots. The positions for the dots are selected from two vertical columns of three dots each. At least one raised dot must be present. How many distinct Braille characters are possible?

  $|Dot|=|Raised \text{ } dot|+|No \text{ } raised \text{ } dot|=2$

  $|Dot|^{n\text{ }dots={columns\times rows}}=2^{6}=64$ are Braille characters possibles.

• The options available on a particular model of a car are five interior colors, six exterior colors, two types of seats, three types of engines, and three types of radios. How many different possibilities are available to the consumer?

  $|Possibilities|=|Interior\text{ } colors|\cdot |Exterior\text{ } colors|\cdot|Seats|\cdot|Engines|\cdot|Radios|=5 \cdot 6 \cdot 2 \cdot 3 \cdot 3=540$

• How many different car license plates can be constructed if the licenses contain three letters followed by two digits if repetitions are allowed? if repetitions are not allowed?

  $\text{Car license plates}=\{(letter,letter,letter,digit,digit)|letter \in \text{English alphabet},digit \in \text{Decimal numeral system}\}$

  $|\text{English alphabet}|=26$

  $|\text{Decimal numeral system}|=10$

  If repetitions are allowed, then

  $\text{Car license plates}=26\cdot26\cdot26\cdot10\cdot10=1757600$

  If repetitions are not allowed, then

  $\text{Car license plates}=26\cdot25\cdot24\cdot10\cdot9=1404000$

• How many 7-digit phone numbers are possible, assuming that the first digit can’t be a 0 or a 1?

  $\text{phone numers}=\{(digit_1,digit_2,digit_3,digit_4,digit_5,digit_6,digit_7)|digit_1\in[2,9],digit_2\in[0,9],...\}$

  $|\text{phone numbers}|=8\times10^7=8000000$

• Re-solve the previous problem, except now assume also that the phone number is not allowed to start with 911

  $\text{911 phone numers}=\{(digit_1,digit_2,digit_3,digit_4,digit_5,digit_6,digit_7)|digit_1\in[9],digit_2\in[1],digit_3\in[1],digit_4\in[0,9],...\}$

  $|\text{no 911 phone numbers}|=|\text{phone numbers}|-|\text{911 phone numbers}|=(8\times10^7)-10^4=7990000$

• Why the number of ways to choose 5 people out of 10 is greater than the number of ways to choose 6 people out of 10?

• Why the number of ways to break 10 people into 2 teams of 5 is less than the number of ways to break 10 people into a team of 6 and a team of 4?

• How many different 3x3 pattern locks are possible?

  

Exercises 10–12 ask about strings of length 5 formed using the letters ABCDEFG without repetitions.

• 10. How many strings begin with the letter F and end with the letter A?

  $String=\{(F,letter,letter,letter,A)|letter_\in \{B,C,D,E,G\} \}$

  $|\{F\}|=1,|\{A\}|=1,|\{B,C,D,E,G\}|=5$

  $|String|=1\cdot5\cdot4\cdot3\cdot1=60$

• 11. How many strings begin with the letter F and do not end with EB in that order?

  $U=\{(F,letter,letter,letter,letter)|letter\in \{A,B,C,D,E,G\}\}$

  $|U|=1\cdot6\cdot5\cdot4\cdot3=360$

  $Strings_{EB}=\{(F,letter,letter,E,B)|letter\in \{A,C,D,G\}\}$

  $|Strings_{EB}|=1\cdot4\cdot3\cdot1\cdot1=12$

  $|Strings_{noEB}|=|U|-|Strings_{EB}|=348$

• 12. How many strings contain CEG together in that order?

  $Strings_0=\{(C,E,G,letter,letter)|letter\in \{A,B,D,F\}\}$

  $|Strings_0|=1\cdot1\cdot1\cdot4\cdot3=12$

  $Strings_1=\{(letter,C,E,G,letter)|letter\in \{A,B,D,F\}\}$

  $|Strings_1|=12$

  $Strings_2=\{(letter,letter,C,E,G)|letter\in \{A,B,D,F\}\}$

  $|Strings_2|=12$

  $|Strings|=|Strings_0|+|Strings_1|+|Strings_2|=36$

  But, a sequence n and sub-sequence r together can simplify as $n-r+1$.

  $CEG$ sub-sequence, $|\{C,E,G\}|=3$

  $(letter,letter,letter,letter,letter),|sequence|=5$, where CEG can be 3 distinct positions.

  But, We'll convert to $5-3+1=3$ size sequence, such that

  $CEG$ sub-sequence, $|\{CEG\}|=1$

  $(letter,letter,letter),|sequence|=3$, where CEG can be 3 distinct positions.

  Thus, $|Strings|=((n-r)+1)|String_{CEG}|=36$

Two chess players, A and B, are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0 points.

• How many possible outcomes for the individual games are there, such that overall player A ends up with 3 wins, 2 draws, and 2 losses?

  $A=\{(win_1,win_2,win_3,draw_1,draw_2,loss_1,loss_2),...\}$

  $|A|={7\choose 3}{4\choose 2}{2\choose 2}=210$

• How many possible outcomes for the individual games are there, such that A ends up with 4 points and B ends up with 3 points?

  $A_1=\{(win_1,win_2,win_3,win_4,loss_1,loss_2,loss_3),...\}$

  $A_2=\{(win_1,win_2,win_3,draw_1,draw_2,loss_1,loss_2),...\}$

  $A_3=\{(win_1,win_2,draw_1,draw_2,draw_3,draw_4,loss_1),...\}$

  $A_4=\{(win_1,draw_1,draw_2,draw_3,draw_4,draw_5,draw_6),...\}$

  $|\text{All outcomes where A wins by a score of 4}|=|A_1|+|A_2|+|A_3|+|A_4|={7\choose4}+{7\choose3}{4\choose2}+{7\choose2}{5\choose4}+{7\choose1}=357$

• Now assume that they are playing a best-of-7 match, where the match will end when either player has 4 points or when 7 games have been played, whichever is first. For example, if after 6 games the score is 4 to 2 in favor of A, then A wins the match and they don't play a 7th game. How many possible outcomes for the individual games are there, such that the match lasts for 7 games and A wins by a score of 4 to 3?

  267

Addition Principle or Sum Rule

If $A_1,A_2,...,A_n$ are disjoint sets, then:

$|A_1\cup A_1\cup ...\cup A_n|=|A_1|+|A_2|+...+|A_n|$

Inclusion–exclusion principle

If $X$ and $Y$ are finite sets, then

The k-to-1 rule or division rule

If B is a finite set and f : A → B maps precisely k items of A to every item of B, then A has k times as many items as B.

https://dspace.mit.edu/bitstream/handle/1721.1/70477/6-042j-fall-2002/contents/readings/ln9.pdf

The division rule is a common way to ignore “unimportant” differences when you are counting things. You can count distinct objects, and then use the division rule to “merge” the ones that are not significantly different.

Permutations

A permutation of n things taken r at a time, written P(n,r), is an arrangement in a row of r things, taken from a set of n distinct things. Order matters.

In your problem, $(a_0,a_1,a_2)\ne(a_1,a_2,a_0)?$

Example: How many permutations of the letters ABCDEF contain the letters DEF together in anyorder?

Counting Subsets or combinations

A combination of n things taken r at a time, written C(n,r) or n r (“n choose r”) is any subset of r things from n things. Order makes no difference.

In your problem, $(a_0,a_1,a_2)=(a_1,a_2,a_0)?$

The key points to remember in this section are that a permutation takes order into account and a combination does not take order into account. Thus, a key to solving counting problems is to determine whether we are counting ordered or unordered items.

Combinatorial Proofs

$n{n-1 \choose k-1}=k{n \choose k}$

Vandermonde's identity

${m+n \choose k} = \sum^k_{j=0} {m \choose j}{n\choose k-j}$

The Binomial Theorem

Pascal’s Triangle Identity

Worked examples

• How many ways are there to split a dozen people into 3 teams, where one team has 2 people, and the other two teams have 5 people each?

  $$teams=\{((x_1,x_2),(y_1,y_2,y_3,y_4,y_5),(z_1,z_2,z_3,z_4,z_5))|x_1\in[1,12],x_2\in[1,11],y_1\in[1,10],...,z_1\in[1,5],...z_5\in[1],\\ \text{but order doesn't matter, such that sequence two sequences with same elements are equals} \}$$

  For example, $(x_1,x_2)=(x_2,x_1)$ or $(y_1,y_2,y_3,y_4,y_5)=(z_1,z_2,z_3,z_4,z_5)$. First one references to itself, the second one references to teams by that group by 2.

  $$|teams|=\frac{team_1\times team_2\times team_3}{\text{Group by repetitions}}=\dfrac{{12\choose2}{10\choose5}{5\choose5}}{\text{Group by repetitions}}=\dfrac{{12\choose2}{10\choose5}}{\text{2!}}=8316$$

• How many ways are there to split a dozen people into 3 teams, where each team has 4 people?

  $teams=\{((x_1,x_2,x_3,x_4),(y_1,y_2,y_3,y_4),(z_1,z_2,z_3,z_4))|x_1\in[1,12],x_2\in[1,11],...,y_1\in[1,8],...,z_1\in[1,4],...,z_4\in[1],\text{but order doesn't matter}\}$

  For example$(y_1,y_2,y_3,y_4)=(z_1,z_2,z_3,z_4)$. First one eferences to teams by that group by 3.

  $$|teams|=\frac{team_1\times team_2\times team_3}{\text{Group by repetitions}}=\dfrac{{12\choose4}{8\choose4}{4\choose4}}{\text{Group by repetitions}}=\dfrac{{12\choose4}{8\choose4}}{\text{3!}}=8316$$