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?

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&#039;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&#039;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&#039;t know how a four variable equation such as this can be represented explicitly. There&#039;s probably a simple combinatorical formulation I&#039;m overlooking. How can this function be expressed explicitly?

relientaaho2 · Accepted Answer

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.

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

Answered question

Answer & Explanation

New Questions in Algebra I