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