CSCE 222 Lecture 19

« previous | Wednesday, March 9, 2011 | next »

Counting

Lecture Notes

Product Rule

Suppose a procedure can be broken into two tasks:

• there are $m$ ways to do the first task, and
• for each of these ways, there are $n$ ways to do the second task.

Therefore, the total number of possible tasks is $m\times n$

Number of Possible Functions

Suppose that $f:A\rightarrow B$ is a function from a set $A$ with $|A|=m$ elements to $B$ with $|B|=n$ elements. How many possible functions exist?

$\underbrace {n\times n\times \ldots \times n} _{m}=n^{m}$

Sum Rule

$S$ is union of 2 non-overlapping finite sets $A$ and $B$: $|S|=|A|+|B|$

Example

Each user has a password 6-8 characters long, where each character is an uppercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there?

Let $P$ be number of passwords, $P_{k}$ is the number of passwords with length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , hence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P=P_6+P_7+P_8} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_k = 36^k-26^k} : number of strings of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} with digits or uppercase letters − number of strings that contain only letters.

Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = 36^6-26^6+36^7-26^7+36^8-26^8}

Inclusion/Exclusion

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A \cup B| = |A| + |B| - |A \cap B|}

How many bit strings of length 8 either start with 1 or end with 00?

Let $A$ be the set of bit strings of length 8 that start with 1. Then $|A|=2^{7}$

Let $B$ be the set of strings of length 8 that end with 00. Then $|B|=2^{6}$

$|A\cap B|=2^{5}$, the number of strings that start with 1 and end in 00.

Therefore, $|A\cup B|=2^{7}+2^{6}-2^{5}$

Pigeonhole Principle

If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more objects.

Example: Among 367 people, there must be at least two people who share the same birthday. Max of 366 days in a (leap) year.

Example: For every positive integer $n$, there is a multiple of $n$ that contains only the numbers 0 and 1.

Proof: Consider the $n+1$ integers $\underbrace {1,11,\ldots ,11\ldots 1} _{n+1}$. Dividing each by $n$ yields at most $n$ possible remainders. Since we have $n+1$ numbers, two must share the same remainder... What does this mean?

Sequences

A set of numbers.

subsequence

a sequence formed by removing some elements of a larger sequence while maintaining a certain order.

strictly increasing

for all numbers in a sequence, the next number is larger than all before it.

strictly decreasing

for all numbers in a sequence, the next number is smaller than all before it.

Example

Proof. Seeking a contradiction, we assume that there exists a sequence $S=(a_{1},\ldots ,a_{n^{2}+1})$ that does not contain any strictly increasing (or decreasing) subsequence of length n+1 or longer.

Let $i_{k}$ be the length of the longest increasing subsequence starting at $a_{k}$. Let $d_{k}$ be the length of the longest decreasing subsequence starting at $a_{k}$.

Notice that 1 ≤ $i_{k},d_{k}$ ≤ $n$, so there are $n^{2}$ distinct ordered pairs

Since all elements of the sequence are distinct real numbers, we either have $a_{s}<a_{t}$ or $a_{s}>a_{t}$, where $a_{s}$ and $a_{t}$ are two elements in our sequence.

Permutations

A permutation of a set of distinct elements is an ordered arrangement of these objects:

$S=\{1,2,3\}\rightarrow \{3,1,2\}\quad {\mbox{a permutation}}$

If we decide to rearrange Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} elements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} , then it is called an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} -permutation.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n,r)} denote the number of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} -permutations of a set containing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} elements.

Simple Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} P(\{1,2,3\}, 2) &= |\{\{1,2\}, \{1,3\}, \{2,1\}, \{2,3\}, \{3,1\}, \{3,2\}|\\ &= 3\ \mbox{ways to choose first element} \times 2\ \mbox{ways to choose the second element} \\ &= 6\ \mbox{by product rule} \end{align}}

In General

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} P(n,r) &= n(n-1)(n-2) \ldots (n-r+1) \\ &= \frac{n!}{(n-r)!} \end{align}}

Complicated example

How many permutations of the letters A-H are there containing the string "ABC"?

Think of the phrase ABC as a single token. The other five positions can be filled with D-H. Therefore, 6!

Note: Look up lex