1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm not quite familiar with the notation you use in the equations with the "mathfrak" font. Does P 1<=.<=3(Z) denote the power set with values limited between 1 and 3? Also, can this approach be modified if one of the elements can appear at most 2 times and the others at most 3? $\endgroup$
    – hacatu
    Feb 29, 2016 at 0:45
  • 1
    $\begingroup$ The notation is documented at Wikipedia. I trust you can do the case of a special element appearing at most two times on studying this entry. $\endgroup$ Feb 29, 2016 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.