How to find explicit form of recurrence relation with four variables for combinatorical value

Question

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(n_1,n_2,n_3,0)=1$$ $$C(n_1,n_2,n_3,l)=n_1C(n_1-1,n_2,n_3,l-1)+n_2C(n_1+1,n_2-1,n_3,l-1)+n_3C(n_1,n_2+1,n_3-1,l-1)$$ The number of ways to choose the elements is then $C(0,0,d,l)$. Clearly there can be at most $3^l$ instances of the base case $C(n_1,n_2,n_3,0)=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?

Answer 1

Suppose $q$ different values from the $d$ values appear in the selection. These create

$$\mathfrak{S}_{=q}(\mathfrak{P}_{1\le\cdot\le 3}(\mathcal{Z}))$$

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 {d\choose q} \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! [z^l] \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}(\mathfrak{P}_{0\le\cdot\le 3}(\mathcal{Z}))$$

to get the same result.

Observe that for the maximum possible value $l=3d$ we get

$$(3d)! [z^{3d}] \left(1+z+\frac{z^2}{2}+\frac{z^3}{6}\right)^d = \frac{(3d)!}{(3!)^d} = {3d\choose 3,3,3,\ldots, 3}$$

which is the correct value.