<< Original question: Is there a nice general formula or a good approximation for the number of nondecreasing sequences in N^k, for integers N and k ?
Thanks Dan. Sometime after posting my question I also realized the connection to ordered partitions. The number of length k nondecreasing sequences over N = {0, 1, ..., N-1} is the number of ordered partitions of k into N parts of size 0 or more, and this is the standard number of ordered partitions of N+k into N parts (of size 1 or more). I'm not intimate with ordered partitions, but googling tells me this is (N+k-1 choose N-1), which checks for small N. I hadn't expected a formula nearly that nice :-) - Scott
The second paragraph below (using the separators to count the ways that I increments can be binned into k-1 bins) is flawed -- it overcounts the ways by I'm not sure what factor at this hour.
Oh, well.
--Dan
<< Think of the I increments as dots in a row. The number of ways they can be distributed into k-1 bins is the same as the way we can separate the I dots using k-2 vertical lines each before, between, or after the I dots. (Two or mor e separators are allowed to have 0 dots between them.)
The number of ways to arrange the separators, and equally to interpolate a nondecreasing sequence between X1 and Xk, is thus (I+1)^(k-2).
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun