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\to B$ is a function from a set $A$ with $|A|=m$ elements to $B$ with $|B|=n$ elements. How many possible functions exist?

$\underset{m}{\underbrace{n\times n\times \dots \times n}}=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 $k$, hence $P=P_6+P_7+P_8$.

$P_k=36^k-26^k$: number of strings of length $k$ with digits or uppercase letters − number of strings that contain only letters.

Therefore, $P=36^6-26^6+36^7-26^7+36^8-26^8$

Inclusion/Exclusion

$|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 $\underset{n+1}{\underbrace{1,11,\dots ,11\dots 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,\dots ,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\}\to \{3,1,2\}\text{a permutation}$

If we decide to rearrange $r$ elements in $S$, then it is called an $r$-permutation.

Let $P(n,r)$ denote the number of $r$-permutations of a set containing $n$ elements.

Simple Example

$\begin{array}{rl}P(\{1,2,3\},2)& =|\{\{1,2\},\{1,3\},\{2,1\},\{2,3\},\{3,1\},\{3,2\}|\\ & =3\text{ways to choose first element}\times 2\text{ways to choose the second element}\\ & =6\text{by product rule}\end{array}$

In General

$\begin{array}{rl}P(n,r)& =n(n-1)(n-2)\dots (n-r+1)\\ & =\frac{n!}{(n-r)!}\end{array}$

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