# I want to know how many ways there are to choose l elements in order from a set with d eleme

I want to know how many ways there are to choose $l$ elements in order from a set with $d$ elements, allowing repetition, such that no element appears more than 3 times. I've thought of the following recursive function to describe this:
$C\left({n}_{1},{n}_{2},{n}_{3},0\right)=1$
$C\left({n}_{1},{n}_{2},{n}_{3},l\right)={n}_{1}C\left({n}_{1}-1,{n}_{2},{n}_{3},l-1\right)+{n}_{2}C\left({n}_{1}+1,{n}_{2}-1,{n}_{3},l-1\right)+{n}_{3}C\left({n}_{1},{n}_{2}+1,{n}_{3}-1,l-1\right)$
The number of ways to choose the elements is then $C\left(0,0,d,l\right)$. Clearly there can be at most ${3}^{l}$ instances of the base case $C\left({n}_{1},{n}_{2},{n}_{3},0\right)=1$. Additionally, if ${n}_{i}=0$, that term will not appear in the expansion since zero times anything is zero.
It isn't too hard to evaluate this function by hand for very small l or by computer for small l, but I would like to find an explicit form. However, while I know how to turn recurrence relations with only one variable into explicit form by expressing them as a system of linear equations (on homogeneous coordinates if a constant term is involved) in matrix form, I don't know how a four variable equation such as this can be represented explicitly. There's probably a simple combinatorical formulation I'm overlooking. How can this function be expressed explicitly?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

relientaaho2
Suppose $q$ different values from the $d$ values appear in the selection. These create
${\mathfrak{S}}_{=q}\left({\mathfrak{P}}_{1\le \cdot \le 3}\left(\mathcal{Z}\right)\right)$
different possible configurations with generating function
${\left(z+\frac{{z}^{2}}{2}+\frac{{z}^{3}}{6}\right)}^{q}.$
Here the first set from the sequence describes where the smallest value from the $q$ values appears, the next set where the second smallest value appears and so on.
Sum these to obtain
$\sum _{q=1}^{d}\left(\genfrac{}{}{0}{}{d}{q}\right){\left(z+\frac{{z}^{2}}{2}+\frac{{z}^{3}}{6}\right)}^{q}=-1+{\left(1+z+\frac{{z}^{2}}{2}+\frac{{z}^{3}}{6}\right)}^{d}.$
The answer is then given by
$l!\left[{z}^{l}\right]{\left(1+z+\frac{{z}^{2}}{2}+\frac{{z}^{3}}{6}\right)}^{d}.$
Remark. We could have started from the labeled species
${\mathfrak{S}}_{=d}\left({\mathfrak{P}}_{0\le \cdot \le 3}\left(\mathcal{Z}\right)\right)$
to get the same result.
Observe that for the maximum possible value $l=3d$ we get
$\left(3d\right)!\left[{z}^{3d}\right]{\left(1+z+\frac{{z}^{2}}{2}+\frac{{z}^{3}}{6}\right)}^{d}=\frac{\left(3d\right)!}{\left(3!{\right)}^{d}}=\left(\genfrac{}{}{0}{}{3d}{3,3,3,\dots ,3}\right)$
which is the correct value.