🎡

# Discrete (aka finite aka concrete) mathematics

Tags Math @January 6, 2021 1:39 PM @December 2, 2022 10:42 AM

# 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

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

#### Foundations

NameWhy?TopicsAuthorsLast edition
Discrete mathematicsMost topics. Several examples. Coding.Richard Johnsonbaugh
Mathematics for Computer Science - TextbookThe clearestAlbert R MeyerEric LehmanF Thomson Leighton
Discrete Mathematics and Its ApplicationsapplicationsKenneth H. Rosen
Discrete and combinatorial mathematicasRalph P. Grimaldi
Mathematics for Computer Science (6.042J) - CourseAdam ChlipalaAlbert Meyer
Concrete Mathematics (Second edition)Discrete calculusDiscrete probabilityNumber TheoryDonald E. KnuthOren PatashnikRonald L. Graham
CS103: Mathematical Foundations of Computing
1. Nilsson, N.J.: "Artificial Intelligence, a new synthesis", Ed. Morgan Kaufmann Publishers, 1998
Untitled

# Requisites

• Minimum formal math.

# Nice to have

• Calculus
• Coding skills

# Foundations topics

• Set theory
• Sets
• Mathematical logic
• Combinatorics
• Combinations
• Permutations
• Partitions
• Graph theory

Graphs

Networks

• Number theory
• Integers
• Transcendental numbers
• Diophantine approximation
• 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} \}$﻿

## 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$﻿.

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

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

 Name Denotation Meaning Conjunction @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$p \land q$﻿ p && q p and q Disjunction @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$p \lor q$﻿ p || q p or q. Inclusive-or Negation !p not p

### 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

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.

All the flipped coins were not heads.

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.

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 ﬁve 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

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

## Conditional propositions and logical equivalence

If $p$﻿ and $q$﻿ are propositions, the proposition

is called a conditional proposition and is denoted $p\implies q$﻿.

 p q @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$p\implies q$﻿ Comments T T T You must prove this by assuming the antecedent. T F F You don’t prove this since the conclusion is false. F T T True by default or vacuously true, so you don’t prove this. F F T True by default or vacuously true, so you don’t prove this.
• Sufficient condition. If A then B. B whenever the occurrence of A is all that is needed for the occurrence of B. A guarantees B, but B might be achieved in other ways.

If X is a cat, then X is an animal.

• Necessary condition. A cannot occur without the occurrence of B, but B doesn’t guarantee A.

If not B then not A.

If X is not an animal, then X is not a cat.

If X is a cat, then X is an animal.

Si P, entonces Q. P: X es Y. Q: Z es W.

Si X es Y, entonces Z es W.

P es una condicion suficiente para que ocurra Q. Q ocurre porque P. P no es una condicion necesaria para que ocurra Q. Q puede ocurrir sin necesidad de que ocurra P. P garantiza Q, pero Q puede lograrse de otras maneras. Siempre que ocurra P, pasara Q. La implicacion no es un argumento, sino su sintesis. Es el fundamento para las inferencias.

Analisis de la tabla de verdad: True => True True True => False False Si sabemos que (P=>Q es falso) entonces P es verdaero y Q es Falso. True =>

Si no Q, no P. Si no ocurre Q es una condicion suficiente para que no haya pasado P.

no P o Q.

A common mistake is no P ⇒ no Q, it is a mistake because Q can occur if P doesn’t happen.

## Worked examples

Restate each proposition in the form of a conditional proposition.

• Joey will pass the discrete mathematics exam if he studies hard.

p: Joey will pass the discrete mathematics exam

q: He studies hard.

$q\implies p$﻿

• Rosa may graduate if she has 160 quarter-hours of credit.

q: she has 160 quarter-hours of credit.

$q\implies p$﻿

• A necessary condition for Fernando to buy a computer is that he obtain $2000. p: Fernando to buy a computer. q: He obtains$2000.

A necessary condition for $p$﻿ is $q$﻿.

not q then not p

$p \implies q$﻿

• A sufficient condition for Katrina to take the algorithms course is that she pass discrete mathematics.

p: Katrina to take the algorithms course.

q: She passes discrete mathematics.

A sufficient condition for $p$﻿ is $q$﻿.

$q \implies p$﻿

• Getting that job requires knowing someone who knows the boss.

p: Getting that job.

q: Knowing someone who knows the boss.

A necessary condition for getting a job is knowing someone who knows the boss.

A necessary condition for p is q.

$p \implies q$﻿

• You can go to the Super Bowl unless you can’t afford the ticket.

p: You can go to the Super Bowl.

q: You can afford the ticket.

p unless not q

p except on the condition that not q

A necessary condition for $p$﻿ is not (not $q$﻿).

A necessary condition for $p$﻿ is q.

$p\implies q$﻿

• You may inspect the aircraft only if you have the proper security clearance.

p: You may inspect the aircraft.

q: You have the proper security clearance.

A necessary condition for p is q.

if not q, not p.

if p, then q.

• The audience will go to sleep if the chairperson gives the lecture.

p: The audience will go to sleep.

q: The chairperson gives the lecture.

$q\implies p$﻿

• The program is readable only if it is well structured.

q: It is well structured.

$p\implies q$﻿

• A necessary condition for the switch to not be turned properly is that the light is not on.

p: The switch is turned properly.

q: The light is on.

A necessary condition for not p is that not q.

if q then p.

$q\implies p$﻿

Represent the given proposition symbolically

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

# 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

• 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://math.stackexchange.com/questions/424854/1-0-by-integration-by-parts-of-tanx/424855#424855

## Methods

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

## Worked example.

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

Therefore

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

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

Our theorem is false since

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}$﻿

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}$﻿

As

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

# Counting

## 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

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

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?

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.

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

## TIP. Bash. Brace expansion.

echo {1..3}{1..2}{5..10} | wc -w # 36
echo {1..3}{1..2} # 11 12 21 22 31 32

https://wiki.bash-hackers.org/syntax/expansion/brace

# Diophantine equations

https://www.hackmath.net/en/calculator/integer-diophantine-equations-solver

# Finite calculus

## Discrete logarithm problems

• Define a sequence iteratively by $s_1=\sqrt {3}$