Thursday, March 27, 2014

Compositions

I missed this class, probably because I was crying over COMP 527.

1Compositions¶

If $c_k(n)$ is the number of ways of writing $n$ as a sum of $k$ positive integers, then

$$c_k(n) = \binom{n-1}{k-1}$$

Proof by bijection to $k-1$ subsets of an $n-1$ set.

Note that if we can have zeros in our sum, we have $\displaystyle \binom{n+k-1}{k-1}$ ways instead.

2Convolutions¶

Fruit salads and shit. See question 1, assignment 6.