OOPS RE: [math-fun] nondecreasing sequence count?
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 more 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).
<< 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
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.
participants (3)
-
dasimov＠earthlink.net -
Michael Kleber -
Scott Huddleston