Integer Partitions and distinguishable permutations

Question

I'm not a mathematician but I'm faced with a problem where I can't find an answer, also because I do not know what I shall ask for:

I have to deal with partitions of an integer k, only small values, up to 30 at most. If we write this partitions down, lets say for k=4, we have p(k) = 5, namely:

1,1,1,1
2,1,1
2,2
3,1
4

So far, so good.

Now we have to build distinguishable permutations with these partitions, where the length of the permutation l is always greater or equal than k, let's say l = 6 for this explanation. (so they are filled up with 0s)

My task now is to find the sum s(k,l) of distinguishable permutations to be build out of the given partitions, for the given length

1,1,1,1,0,0
2,1,1,0,0,0
2,2,0,0,0,0
3,1,0,0,0,0
4,0,0,0,0,0

I have learned in my school-days (it's long ago), that this could be achieved with the multinomial coefficient, that I have to apply for every single partition. Finally I have to sum it up, and my problem would be solved.

I can do this - with the help of a computer program.

But, and this is my question, is there a more mathematical solution? Does anyone know whether there is a term or a definition or a function name what I would like to calculate?

Thank you very much for your assistance.

Answer 1

This is the same as the number of sequences of nonnegative integers $x_1,\ldots,x_l$ whose sum is $k$, or equivalently the number of sequences of positive integers of this length whose sum is $k+l$. This is the number of ways to choose $l-1$ partitions between $k+l$ elements to divide them into $l$ nonempty groups. The answer is $$\binom{k+l-1}{l-1}$$