What is discrete mathematics?

It is also known as Mathematics for computer science. Sometimes finite mathematics, or concrete mathematics.

Discrete mathematics is the study of numerable sets, it is 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.

Nice to have

• 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.

Classical Propositional Logical

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

• Don't use "preposition" as synonymous with "proposition". 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.

• Some people use statements and propositions interchangeably.

• The following statements are propositions

  • $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.

  • $\dfrac{d}{dx}e^x=e^x$

  • She loves him.

  • Whenever Juney barks, Ralph gets mad.

  💡

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

• Moreover, the definition excludes 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. A paradox is not a statement.

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

The Connectives of Propositional Logic. In short, Logical formulas

Definition.

Let $p$ and $q$ be propositions.

Worked examples

• Write the negation of the proposition.
  • Ten heads were obtained when you flip 10 times a coin.

    $P(\text{flipped coin} )=\text{flipped coin is a head}$

    $\lnot P(\text{flipped coin} )=\text{flipped coin is a tail}$

    By Morgan Law

    $\lnot(\forall \text{flipped coin } P(\text{flipped coin} ))= \exists \text{flipped coin } \lnot P(\text{flipped coin})$

    In plain English, the following propositions are equivalent

    Ten heads were not obtained.

    Some flipped coins were not head.

    Some flipped coins were tail.

    At least one flipped coin was tail.

  • Some heads were obtained when you flip 10 times a coin.

    $P(\text{flipped coin} )=\text{flipped coin is a head}$

    $\lnot P(\text{flipped coin} )=\text{flipped coin is a tail}$

    By Morgan Law

    $\lnot (\exists \text{flipped coin } P(\text{flipped coin}))= \forall\text{flipped coin } \lnot P(\text{flipped coin})$

    In plain English, the following propositions are equivalent

    At least one head was not obtained.

    Some heads were not obtained.

    All the flipped coins were not heads.

    No flipped coin was head.

    All the flipped coins were tail.

  • Some heads $H$ and some tails $T$ were obtained.

    The above proposition is equivalent to

    $U=\{x|x\in H \text{ or } x\in T\}$

    $H\cup T=U$ Because the flipped coins are either head or tail.

    $H\cap T=\empty$ Because the coin is either head or tail, but not both.

    So by complement law

    $H\cup T=T^\complement\cup T=U$

    The negation of the proposition is

    $U^\complement=\empty$ Since 0/1 laws.

  • At least one was obtained.

    No head was obtained.

    All the flipped coins were tails.

  • For some positive integer $n$, $19340=n\cdot 17$

    No positive integer $n$, $19340=n\cdot 17$

    All positive integers $n$, $19340\neq n\cdot 17$

  • Every even integer greater than 4 is the sum of two primes.

    Every even integer greater than 4 is not the sum of two primes.

    At least one integer greater than 4 is not the sum of two primes.

• Determine whether each is true or false.
  • $5<9$ and $9<7$

    $true\land false$

    $false$

  • $5<9$ and $9<7$ are not the case.

    $\lnot false=true$

  • $5<9$ or $5<7$ and $9<7$ are not the case.

    $true\lor whatever=true$

• Formulate the symbol expression in words using $p:\text{Lee takes computer science.}$ $q:\text{Lee takes mathematics.}$
  • $\lnot p$

    Lee doesn’t take computer science.

  • $p\lor\lnot q$

    Lee takes computer science or no mathematics.

  • $p\land q$

    Lee takes computer science and mathematics.

  • $p\land \lnot q$

    Lee takes computer science, but no mathematics.

  • $\lnot p\land \lnot q$

    Lee takes neither computer science nor mathematics.

• Formulate the symbolic expression in words using $p:\text{Today is Monday}$. $q:\text{It is raining.}$ $r:\text{It is hot.}$
  • $p\lor q$

    Today is Monday or raining.

  • $\lnot(p\lor q)\land r$

    Today is neither Monday nor raining, but it is hot.

  • $(p\land(q\lor r))\land(r\lor(q\lor p))$

    Today is Monday and it’s raining or hot, but it’s hot, raining, or Monday.

• At one time, the following ordinance was in effect in Naperville, Illinois: “It shall be unlawful for any person to keep more than three [3] dogs and three [3] cats upon his property within the city.” Was Charles Marko, who owned five dogs and no cats, in violation of the ordinance? Explain. https://www.chicagotribune.com/news/ct-xpm-1990-10-12-9003250777-story.html

  Yes.

  Informally, if you have five dogs, then you’re keeping more than three dogs.

  Formally $dogs,cats\in N$

  $is\_lawful(dogs,cats)=dogs\le3 \land cats\le3$

  $is\_lawful(5,0)=dogs\le3 \land cats\le3 =false\land true=false$

  Maybe Charles Marko thought government counts in total such that

  $is\_lawful(dogs,cats)=dogs+cats\le6$

  but his ordinance interpretation fails; the government doesn’t say it explicitly, and we don’t assume anything from the text.

  Although attorney argues that is possible to change $and$ to $or$, if you follow connectives of propositional strictly; it is a mistake.

  $is\_lawful(dogs,cats)=dogs\le3 \land cats\le3 \neq dogs\le3 \lor cats\le3$

6. Lógica computacional, Enrique Paniagua Arís et al., Ed. Thomson, 2003.

7. Elementos de lógica formal, Calixto Badesa et al., Ed. Ariel, 2003.

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

Argument

Rules of Inference

Worked examples

Formulate the following arguments symbolically and determine whether each is valid.

Let

p: I study hard.

q: I get A’s.

r: I get rich.

• If I study hard, then I get A’s. I study hard. Therefore, I get A’s.

  $p\implies q$

  $p$

  $\therefore q$

  It’s a valid argument because the argument uses the modus ponens.

• If I study hard, then I get A’s. If I don’t get rich, then I don’t get A’s. Therefore, I get rich.

  $p\implies q$

  $\lnot r\implies \lnot q$

  $\therefore r$

  From $\lnot r\implies \lnot q$ contrapositive, we may use Hypothetical syllogism to conclude $r$. Thus the conclusion $r$ follows from the hypotheses and the argument is valid.

  $p\implies q$

  $q \implies r$

  $\therefore r$

• I study hard if and only if I get rich. I get rich. Therefore, I study hard.

  Argument (I)

  $p\iff r$

  $r$

  $\therefore p$

  By Disjunctive syllogism

  $(p\implies r) \land (r\implies p)$

  $\lnot(p\implies r)$

  $\therefore r \implies p$

  By Modus ponens, (1) is valid

  $r \implies p$

  $r$

  $\therefore p$

• If I study hard or I get rich, then I get A’s. I Get A’s. Therefore, If I don’t study hard, then I get rich.

  The argument becomes

  $p\lor r \implies q$

  $q$

  $\therefore \lnot p \implies r$

  It’s invalid because $(p\lor r \implies q)\land q$ is equivalent $q$, and it’s not the conclusion.

• If I study hard, then I get A’s or I get rich. I don’t get A’s and I don’t get rich. Therefore, I don’t study hard.

  $p\implies q \lor r$

  $\lnot q \land \lnot r$

  $\therefore \lnot p$

  It’s a valid argument since modus tollens application

  $p\implies q \lor r$

  $\lnot (q \lor r) \implies \lnot p$

Notes

https://en.wikipedia.org/wiki/List_of_rules_of_inference

https://calcworkshop.com/logic/rules-inference/

http://logic.stanford.edu/intrologic/glossary/rule_of_inference.html

http://intrologic.stanford.edu/chapters/chapter_04.html

https://www.cs.sfu.ca/~ggbaker/zju/math/inference.html

Quantifiers

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

Nested Quantifiers

Proofs

Mathematical systems and the Axiomatic method

What is suitable proof?

Direct proofs

Proof by contradiction

Proofs of equivalence

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 follow a few logical steps from the theorem.

https://mathoverflow.net/questions/18352/theorem-versus-proposition

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.

Notes

Mathematical Writing by Knuth, Larrabee, and Roberts, https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf

Guide to Proofs, Stanford https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/handouts/070 Guide to Proofs.pdf

Proofwriting Checklist, Stanford https://web.stanford.edu/class/cs103/proofwriting_checklist

Some Remarks on Writing Mathematical Proofs by John M. Lee

https://www.youtube.com/watch?v=B0acu5nhG0w&ab_channel=StanfordOnline

https://math.stackexchange.com/questions/424854/1-0-by-integration-by-parts-of-tanx/424855#424855

Most ambiguous and inconsistent phrases and notations in maths

What are some examples of notations and words in maths which have been overused or abused to the point of them being almost completely ambiguous when presented in new contexts? For instance, a fun...

https://math.stackexchange.com/questions/1024280/most-ambiguous-and-inconsistent-phrases-and-notations-in-maths

Methods

Direct proof

Worked examples

• Prove that for all integers m and n, if m and n are even, then m + n is even.

  Let $m,n \in \mathbb{Z}$ such that $m$ is even and $n$ is even, by even definition we know

  $2k_1=m$ and $2k_2=n$ where $k_1,k_2\in \mathbb{Z}$.

  So, $m+n=2k_1+2k_2=2(k_1+k_2)$ is even since $k_1+k_2\in Z$.

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.

Strong induction

https://www.youtube.com/watch?v=9w20J4j5-0Y&ab_channel=AtticPhilosophy

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

https://www.youtube.com/watch?v=z7QCT8cgsR4&ab_channel=FrankStajanoExplains

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$