How to find explicit form of recurrence relation with four variables for combinatorical value 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? 
 A: 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.
