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 $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 $\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 $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{aligned}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{aligned}}$

In General

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

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