Scott Huddleston asked and answered:
Is there a nice general formula or a good approximation for the number of nondecreasing sequences in N^k, for integers N and k ?
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 :-)
If you allowed 0 in your sequences, the answer would be N+k choose k. It's an easy stars-and-bars argument: arrange N stars and k bars in a line, and let the i'th element of your sequence be the number of stars to the left of the i'th bar. (For example, with N=k=4, |**||*|* corresponds to 0,2,2,3.) If you don't like zero, set one star aside and add it to the left of your string at the end -- so the number of strings is (N-1)+k choose k. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.