# 5 - SUCCESS and Counting Inequalities

## Addendum: Additional binomial identity
$\binom{2n}{n} = \sum_{k=0}^n\binom{n}{k}^2$

**Proof**: Use Vandermande's with $m=n$ ($m+n=2n$) and $r=n$
$=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k} = \sum_{k=0}^n\binom{n}{k}^2$

## Applications of counting rules
**Example**: How many rearrangements of the string "ROCKY" are there?
By the product rule: $5!$

## Counting rearrangements of the word SUCCESS
How many rearrangements of the string "SUCCESS" are there?
It might be tempting at first to say $7!$

If we map each letter in "SUCCESS" to the numbers 1-7, we can arrange the letters in two different ways such that the string is the same

Ex:
1 2 3 4 5 6 7
1 2 4 3 5 6 7

We analyze the string more carefully and observe how many of each letter we have
- 3 x S
- 1 x U
- 2 x C
- 1 x E

Lets define a procedure
1. Choose 3 places to arrange the S's $\binom{7}{3}$
2. Write down 1 U $\binom{4}{1}$
3. Write down 2 C's $\binom{3}{2}$
4. Write down 1 E $\binom{1}{1}$

$\binom{7}{3} \times \binom{4}{1} \times \binom{3}{2} \times \binom{1}{1}$

Side note: another way to come to this answer is something along the lines of $\frac{7!}{3! \times 2! \times 1! \times 1!}$

## Counting solutions
How many solutions to the equation $x_1 + x_2 + x_3 = 11$ are there where $x_1, x_2, x_3 \geq 0$ and $x_1, x_2, x_3$ are integers?

Some solutions:
$x_1 = 5$
$x_2 = 6$
$x_3 = 0$

$(1,1,9)$
$(1,2,8)$
$(8,2,1)$
...

Imagine buckets?

There is a bijection between the choices of the bins and the answer to the question

There is a bijection between bitstrings of length 13 with exactly 2 1's and the set of solutions

The answer is $\binom{13}{2}$

**Theorem**: The number of solutions to $x_1 + x_2 + ... + x_k = n$ with $x_i \geq 0$ and each $x_i$ being an integer is $\binom{n+k-1}{k-1}$

<hr/>

How many solutions to the equation $x_1 + x_2 + x_3 \leq 11$ are there where $x_1, x_2, x_3 \geq 0$ and $x_1, x_2, x_3$ are integers?

There are two ways to solve this
1. Use the sum rule

- For each $n \in \{0,1,...,11\}$, let $S_n$ be the solutions to $x_1 + x_2 + x_3 = n$
- By the sum rule, the total number of solutions to $x_1 + x_2 + x_3 \leq 11$ is $|S_1| + |S_2| +|S_3| + ... + |S_n|$
- $\binom{2}{2} + \binom{3}{2} + ... + \binom{13}{2} =? \binom{14}{3}$

2. Use black magic

- We create a bitstring of length $n + k$
- We choose $k$ positions as 1's
- The first 3 sections like the example above will either add up to or be less than 11, the last part we just refer to as y
- 

###### tags: `COMP2804`, `Combinatorics`