Lollies

Let $f(n,k)$ denote the number of ways there are to arrange $n$ lollies bought from a shop that sells $k$ types of lollies in a straight line, given that there is at least one of each of the $k$ types among them. There are a few ways to see that

$f(n,k)=\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n.$

One of which involves considering the number of ways there are to arrange $n$ lollies of $k$ types in a line with no restrictions, and then accounting for over/undercounting (i.e., the Inclusion-Exclusion Principle). Substituting $n=14$ and $k=7$ yields an answer of $\boxed{248619571200}$ .

We are interested in the number of surjective functions from a set $X$ of size $m$ to a set $Y = \{1,2,3,...,n\}$ of size $n$ . For any $1 \le j \le n$ , let $A_j$ be the set of functions from $X$ to $Y$ for which $j$ is not in the range. Then $|A_{u_1} \cap A_{u_2} \cap \cdots \cap A_{u_r}|\; = \; (n-r)^m \hspace{2cm} 1 \le u_1 < u_2 < \cdots < u_r \le n$ for any $1 \le r \le n$ and so, by the Inclusion-Exclusion Principle, $|A_1 \cup A_2 \cup \cdots \cup A_n| \; = \; \sum_{r=1}^n (-1)^{r-1}\binom{n}{r} (n-r)^m$ and so the number of surjective functions is $|(A_1 \cup A_2 \cup \cdots \cup A_n)'| \; = \; n^m - |A_1 \cup A_2 \cup \cdots \cup A_n| \; = \; \sum_{r=0}^n (-1)^{r}\binom{n}{r} (n-r)^m$ Putting $m=14$ and $n=7$ gives the desired answer of $\boxed{248619571200}$ .

Let each type of lollies are numbered as 1,2,3,4,5,6,7. Now let we select $x_i$ lollies from $ith$ type. So that

$x_1+x_2+x_3+x_4+x_5+x_6+x_7=14$ (*)

We see that each integral solution of this corresponds to a way of selection of lollies.

ie if $x_1=12, x_2=2$

this means we select 12 lollies of type 1 and 2 lollies of type 2. For this particular selection the number of ways of arranging the lollies in a line is $\frac{14!}{12!2!}$ .

So what we wish to count is the sum of

$\frac{14!}{x_1!x_2!x_3!x_4!x_5!x_6!x_7!}$

for all solutions of (*).

So we can see that an exponential generating function can help us do that.

the generating function for this is

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

and our answer is then $14!*($ coefficient of $x^{14})$ which is $\boxed{248619571200}$

If we say each candy is a part of cycle within the greater set of 14 candies, then the problem stipulates that the we are counting the number of ways to partition a set of 14 elements into 7 cycles, which is S(14,7) However this count would ignore that each color is unique, so we must multiply S(14,7) by the number of ways to assign each of the seven colors to each of the cycles: 7!. S(14,7) * 7! = 248619571200

The way I solved this is by using dynamic programming.

Let the $dp(n,k)$ denote the number of ways to arrange the $k$ lollies with first $n$ colors such that at least one of each color is used. It's clear the recurrence relation is

${ dp }(i,j)=\sum _{ k=i-1 }^{ j-1 }{ { dp }(i-1,k)\left( \begin{matrix} j \\ j-k \end{matrix} \right) }$

Once we have this recurrence relation we can simply calculate bottom-up until we reach $dp(7,14) = \boxed{248619571200}$ .