This question is a part of a TopCoder problem. I am learning algorithms, and just got stuck at this (not homework).
Suppose we have a set $A$ of integer elements, such that $n(A) = a$ (number of elements in $A$ is $a$). Now we have some $n$ blanks, each of which can be filled using the $a$ elements in A, repetition allowed. I want to find out the total number of such sequences of length $n$ which are in non decreasing order, and can be formed using the elements in $A$.
My thoughts reduce this problem to a dynamic programming approach, but I just wanted to find out if a straightforward formula is possible or not. Thanks.
Without loss of generality, we can let the elements of $A$ be $1, 2, ..., a$. We may form a nondecreasing sequence of length $n$ using 'stars and bars'. Arrange $n$ stars and $a-1$ bars (dividers) in a line. The number of stars in the $i$th grouping say how many times $i$ was used. For instance if $a=5$ and $n=7$, we would have $**||*|***|*$ corresponding to the sequence $1, 1, 3, 4, 4, 4, 5$.
There are $n+a-1 \choose n$ arrangements of the stars and bars, and hence the same number of sequences.