## Basics

- Counting

## Counting

### Trees

- How many 3-bit strings?
- How would you make one sequence?
- How many different sequences of 3 bits from {0, 1}?

```
0 1
/ \ / \
00 01 10 11
/ \ / \ / \ / \
000 001 010 011 100 101 110 111
```

### First Rule of Counting: Product Rule

Objects made by chosing from , then , …, then . Then number of objects if

#### First Rule Example

- How many outcomes possible for coin tosses? –>
- How many 10 digit numbers? –>
- How many digit base numbers? –> , actually

### Functions, Polynomials

How many functions mapping to ?

ways to choose for , ways to choose for …

So, such functions

How many polynomials of degree modulo ?

- ways to choose coefficients, so

## Permutations

How many 10 digits numbers **without repeating a digit**?
Answer:

The number of possible choices for the second number is dependent on the first.

How many different samples of size from numbers **without displacement**?

Permutation of objects =

### One-to-one Functions

How many one-to-one functions from to ?

## Counting Without Order

How many poker hands? ?? Not really, because A, K, Q, 10, J of spades are the “same” as 10, J, Q, K, A of spades.

### Second Rule of Counting

**Second Rule of Counting**: If order doesn’t matter, count ordered objects and then divide by number of orderings.

Number of ordering for a poker hand =

So, correct answer is

To choose out of :

Notation:

### Examples

How many orderings of “ANAGRAM”?

- Ordered set: , except for “A”
- A’s are the same. There’re 3 “A”s, so number of such repeated ones =
- Answer =

How many orderings of “MISSISSIPPI”?

- Ordered set:
- 4 S’s, 4 I’s, 2 P’s, so ordered objects per unordered object

## Sampling

Sample items out of .

**Without replacement**:

- If order matters,
- If order doesn’t matter,

**With replacement**:

- If order matters,
- If order doesn’t matter: not so easy … depends on how many of each item we choose.
- Different number of unordered elts map to each unordered elt.

### Example: Splitting up some money …

How many ways can Bob and Alice split 5 dollars?

**Attempt #1**:

For each of the 5 dollars pick Bob or Alice, so and divide out order. Does this work??

- Nope, doesn’t work. Second rule of counting isn’t the best here.

Let’s make the question harder… How many ways can Bob, Alice, and Eve split 5 dollars?

**Attempt #2**:

`* * * * *`

–––– 5 stars are the 5 dollars

```
| | * * * * *
| * | * * * *
| * * | * * *
...
```

How many different 5 star and 2 bar diagrams? 7 positions in which to place the 2 bars. Answer:

### Stars and Bars

Ways to add up numbers to sum to , or “ from with replacement where order doesn’t matter”.

In general, if we have stars and bars, there are positions from which to choose bar positions. i.e.

## Summary

**First rule**:
sampls with replacement from items:
Samples without replacement:

**Second rule: when order doesn’t matter**

### Balls in bins

” balls in bins” “ samples from possibilities”. “indistinguishable balls” “order doesn’t matter” “only one ball in each bin” “without replacement”

### Sum Rule

Sum rule: **Can sum over disjoint sets**

**Example 1**: Two indistinguishable jokers in 54-card deck. How many 5 card poker hands?
No jokers:
One joker:
Two jokers:
So, answer: + +

**Example 2**: Two distingiushable jokers in 54-card deck.
No jokers: .
One black/white joker:
Both jokers:
Answer is actually same as

### Combinatorial Proofs

#### Theorem 1

**Theorem**:

**Proof**: Choosing what we choose is the same as choosing what we leave out.

#### Theorem 2 – Pascal’s Triangle

**Pascal’s rule**:

**Proof**:
How many size subsets of ?
Disjoint sets:

- Contains first element: then
- Doesn’t contain first element: then

```
0
1 1
1 2 1
1 3 3 1
1 4 6 4 1
```

Row : coefficients of

Foil (4 terms) on steroids: terms: choose or from each factor of

Simplify: collect all terms corresponding to . Coefficient of is : choose factors where is in product.

#### Theorem 3

**Theorem**:

**Proof**:
Consider size subset where is the first element chosen:

- Must choose elements from the remaining elements. => such subsets.
- Add the up to get the total number of subsets

#### Theorem 4 – Binomial Theorem: x = 1

**Theorem**:

**Proof**:
How many subsets of {1, …, }? Construct a subset with sequence of choices.

First rule of counting: subsets.

Sum over to get

### Simple Inclusion/Exclusion

**Sum Rule**: For disjoint sets and ,

**Inclusion/Exclusion Rule**: For *any* and ,

**Example**: How many 10-digit phone numbers have 7 as their first or second digit?

= phone numbers with 7 as first digit.

= phone numbers with 7 as first digit.

### Key Points

- Uncertainty doesn’t mean “nothing is known”

## Conditional Probability

**Definition**:

For events , in the same probability space, such that , the conditional probability of given is:

.

### Bayes Rule

### Total Probability Rule

For **disjoint** sets ,

Hey! Thanks for reading :P I just want to let you know that if you enjoyed this, you might also like this post on Sorting.