Expert: David Hemmer - 10/2/2008

Question
If I have a pool of N numbers, and P positions, where P<N, how many ways can I fill the positions P1, P2, ... with numbers N1, N2, ... such that N1<=N2, N2<=N3, etc.  For example if N=20 and P=6, then 1,2,2,2,5,20 is acceptable, but 1,2,2,20,4,5 is not.  I have a good knowledge of combinations and permutations, but this extra restriction of only ascending numbers has me stumped.

Can you help, please?

Answer
Well I hope I understand the question. So for you want P numbers in a row, nondecreasing and all in the set 1, 2, 3, ..., N.

So this isn't really a question about permutations, you want the number of subsets of N of the right size, with repeats allowed. Your requirement that  N1<=N2 etc.. tells us the order.

The number of P element subsets of an N element set with repeats allowed is the binomial coefficient (N+P-1)choose (N-1). Notice P<N isn't relevant here.

I would suggest you look in Bogart's combinatorics book for this kind of problem.