# Discrete Math_PermutationCombination
### Permutations/Combinations of size $r$ from $n$ distinct objects
| Order Relevant | Repetition | Number of Distributions | Interpretation|
|:-:|:-:|:-:|-|
|yes | no | $P(n, r)$ | # Arrangements with repetition of size $r$ from $n$ distinct objects|
| no | no | $\dbinom{n}{r},\ C(n, r)$ | # Selections/Combinations of size $r$ from $n$ distinct objects |
| yes | yes | $n^r$ | # Arrangements with repetition of size $r$ from $n$ distinct objects |
|no | yes | $\dbinom{r+n-1}{r}$ | # Selections with repetition of size $r$ from $n$ distinct objects |

### Distribute $m$ objects into $n$ containers

| Distinct Objects (m) | Distinct Containers (n) | Some Empty Containers | Number of Distributions | Interpretation|
| :----: | :----: | :----: |-|-|
| yes | yes | yes | $n^m$ | Each of the $m$ distinct object may be distributed into any of the $n$ distinct containers |
| yes | yes | no | $n!S(m,n)$ | Each of the $m$ distinct object may be distributed into any of the $n$ distinct containers with no containers empty|
| yes | no | yes | $S(m,1)+S(m,2)+...+S(m,n)$ | $m$ distinct objects onto 1, 2, ... , $n$ identical containers, leaving no container empty $S(m, 1) + S(m, 2) + ... + S(m, n)$ |
| yes | no | no | $S(m,n)$ | $m$ distinct objects onto $n$ identical containers, leaving no container empty |
| no | yes | yes | $m+n-1 \choose m$ | $(\frac 1{1-x})^n\ (= (1-x)^{-n})$ $=\sum\limits_{k = 0}^\infty {k+n-1 \choose k} {x^k}$ | Ordering food from the view of kitchen (m kids (identical), n foods (distinct)); m identical pennies into n distinct container; nonnegative integer solutions for an equation |
| no | yes | no | ${m-1 \choose {m-n}}={m-1 \choose n-1}\\={{(m-n)+n-1} \choose {m-n}}$ | Deliver one object to each of the $n$ distinct containers first, then distribute $m-n$ objects to the $n$ containers distinct container; nonnegative integer solutions for an equation |
| no | no | yes | $\begin{cases} p(m), \text { for } m=n; \\ p(m, 1)+p(m,2)+...+p(m,n), \text { for } n<m\end{cases}$ | Partition integer $m$ into at most $n$ summands (with some 0 summands, corresponding to empty containers when tossing $m$ identical objects into $n$ identical containers) |
| no | no | no | $p(m,n)$ | Partition integer $m$ into exactly $n$ summands (with no container empty), corresponding to empty containers when tossing $m$ identical objects into $n$ identical containers)** (See more on: **https://math.berkeley.edu/~mhaiman/math172-spring10/partitions.pdf |

$P=\sum\limits_{m = 0}^\infty S(m,n)$

$log_2n$ $\log_2n$

| yes | yes | $n^r$ | $(1+\frac {x}{1!}+\frac {x^2}{2!}+\frac {x^3}{3!}+ ...)^n\\ = e^{nx}=\sum\limits_{r = 0}^n\frac{(nx)^r}{r!}=\sum\limits_{r = 0}^nn^r\dfrac{x^r}{r!}$ |# Arrangements with repetition of size $r$ from $n$ distinct objects |

$(1+x+{x^2}+{x^3}+...)^n\\ =(\frac {1}{1-x})^n = (1-x)^{-n}$

$(e^{x}-1)^n \\ =\sum\limits_{k = 0}^\infty k!S(m,k){\frac {x^k}{k!}} \\ =\sum\limits_{k = 0}^\infty (-1)^k{n\choose k} (n-k)^k$

[*]
$\qquad\qquad f(x)=(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)^n$
$\qquad\qquad\qquad = (e^x-1)^n \qquad\text{(applying binomial theorem)}$
$\qquad\qquad\qquad =\displaystyle\sum_{k=0}^n\binom{n}{k}(e^x)^{k}(-1)^{n-k}$
$\qquad\qquad\qquad =\displaystyle\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}e^{kx}$
$\qquad\qquad\qquad =\displaystyle\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}(1+kx+\frac{(kx)^2}{2!}+\frac{(kx)^3}{3!}+\cdots)$
$\qquad\qquad\qquad =\displaystyle\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\sum_{r=0}^\infty k^r\frac{x^r}{r!}$
$\qquad\qquad\qquad =\displaystyle\sum_{r=0}^\infty (\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^r)\frac{x^r}{r!}$

$(\prod \limits_{i = 1}^{n-1} (1+x^i+x^{2i}+...))\cdot (x^n+x^{2n}+...) \\= (\prod \limits_{i = 1}^{n-1}\frac1{1-x^i})\cdot\frac{x^n}{1-x^n}= x^n\prod \limits_{i=1}^n\frac1{1-x^i} =\sum\limits_{i=0}^n p(i,n){x^i}$ or $P(x,y)=\sum\limits_{i,j} p(i,j)y^j{x^i}= \prod \limits_{i=1}^\infty \frac{1}{1-yx^i}$

$\prod \limits_{i = 1}^\infty (1+x^i+x^{2i}+...) \ \text {for }n=m \\= \prod \limits_{i = 1}^\infty \frac 1{1-x^i} =\sum\limits_{i = 0}^\infty p(i){x^i}\ (\text{where } p(0)=1)$ $\prod \limits_{i = 1}^n (1+x^i+x^{2i}+...) \ \text {for }n<m \\= \prod \limits_{i = 1}^n \frac 1{1-x^i} =\sum\limits_{ i = 0}^n p_{\le n}(i){x^i}$