Scott Huddleston asks:
<<
Is there a nice general formula or a good approximation for the number
of nondecreasing sequences in N^k, for integers N and k ?
>>
Let me give this a shot.
I suspect N here is shorthand for {1,2,. . .,N} ?
Assuming this, let X1 <= 2 <= . . . <=Xk with 1 <= Xj <= N for all j, 1 <= j <= k.
Given the two integers X1 and Xk with 1 <= X1 <= Xk <= N, the above sequence
is determined by the placement of the I = Xk - X1 increments among the
k-1 locations the increments can occur: going from X1 to X2, or X2 to X3, etc.
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).
The totality of nondecreasing sequences includes N ways that I = 0,
N-1 ways that I = 1, . . . , 2 ways that I = N-2,
and finally 1 way that I = N-1. This means the # of nondecr. seqs. is
-------------------------------------------------------------------------------------------------------------------------
nondec(N,k) = N*1 + (N-1)*(2^(k-2)) + . . . + 2*(N-1)^(k-2) + 1*N^(k-2).
-------------------------------------------------------------------------------------------------------------------------
If we divide nondec(N,k) by N^k, we get nondec(N,k))/N^k =
(1/N)*[(N/N)*(1/N)^(k-2)+((N-1)/N)*(2/N)^(k-2)+ . . . +(2/N)*((N-1)/N)^(k-2)+(1/N)*(N/N)^(k-2)]
which, for N >> 0, is approx. the integral from x=0 to x=1 of (1-x)*x^(k-2),
i.e., nondec(N,k)/N^k ~= 1/(k-1) - 1/k = 1/(k^2 - k).
So asymptotically, nondec(N,k) ~ N^k / (k^2 - k).
(Since it's 1:47 am, I think I'll let someone else check my work.)
--Dan
