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

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_{1} C (n_{1} - 1, n_{2}, n_{3}, l - 1) + n_{2} C (n_{1} + 1, n_{2} - 1, n_{3}, l - 1) + n_{3} C (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

S_{= q} (P_{1 \leq \cdot \leq 3} (Z))

different possible configurations with generating function

{(z + \frac{z^{2}}{2} + \frac{z^{3}}{6})}^{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} (\binom{d}{q}) {(z + \frac{z^{2}}{2} + \frac{z^{3}}{6})}^{q} = - 1 + {(1 + z + \frac{z^{2}}{2} + \frac{z^{3}}{6})}^{d} .

The answer is then given by

l! [z^{l}] {(1 + z + \frac{z^{2}}{2} + \frac{z^{3}}{6})}^{d} .

Remark. We could have started from the labeled species

S_{= d} (P_{0 \leq \cdot \leq 3} (Z))

to get the same result.
Observe that for the maximum possible value

l = 3 d

we get

(3 d)! [z^{3 d}] {(1 + z + \frac{z^{2}}{2} + \frac{z^{3}}{6})}^{d} = \frac{(3 d)!}{(3!)^{d}} = (\binom{3 d}{3, 3, 3, \dots, 3})

which is the correct value.

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

Answers (1)

Not exactly what you’re looking for?

Relevant Questions