OK, I see what I did wrong on my "brute force solution" of the Q-generalization of Propp's problem. My error was, the (k-1)^(N-Q) term, counting ways to filling in N-Q slots with any of k-1 letters, allowed the resulting configurations to include some Q or more letters that all were the same. That should have been forbidden. Duh. So, this (i) makes it clear the brute force answers I derived were all valid as upper bounds. (ii) We can now repair. Let A(k,N,Q) be the number of N-letter words over k-letter alphabet such that there is no letter occurring Q or more times. We have the recurrence A(k,N,Q) = SUM(for m=0..Q-1) A(k-1,N-m,Q)*Binomial(N,m)*k and the base case A(1,N,Q) = 1 if 0<=N<Q, else 0. We can also let B(k,N,Q) be the number of N-letter words over k-letter alphabet such that there is no letter occurring Q or more times, except that the last letter occurs exactly Q times. We have B(k,N,Q) = A(k-1,N-Q,Q)*Binomial(N-1,Q-1)*k. These recurrences should let you compute any Propp-like expectation: Expected value of F(N) is SUM(for N=Q,...,k*(Q-1)+1)of k^(-N) * B(k,N,Q) * F(N). I have made no attempt to check these results, so beware of my usual erroneousness. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)