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

Brooke Ayala 2022-05-23 Answered
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?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

relientaaho2
Answered 2022-05-24 Author has 13 answers
Suppose q different values from the d values appear in the selection. These create
S = q ( P 1 3 ( Z ) )
different possible configurations with generating function
( z + z 2 2 + 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
q = 1 d ( d q ) ( z + z 2 2 + z 3 6 ) q = 1 + ( 1 + z + z 2 2 + z 3 6 ) d .
The answer is then given by
l ! [ z l ] ( 1 + z + z 2 2 + z 3 6 ) d .
Remark. We could have started from the labeled species
S = d ( P 0 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 + z 2 2 + z 3 6 ) d = ( 3 d ) ! ( 3 ! ) d = ( 3 d 3 , 3 , 3 , , 3 )
which is the correct value.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more