Doh!
I have a sorted list of n integers, that may contain duplicates, in the range 0..(m-1). How many possible such lists are there given n and m?
Changing to a more standard notation, that's r out of n with repetitions allowed. Following Tom Rokicki's nudge, I did use my brain and got it mostly right before using the web. A page written at my fifth-grade level http://www.mathsisfun.com/combinatorics/combinations-permutations.html uses a mnemonic that I like: walking & picking from a row of bins. Anyway, this is leading up to more of a puzzle: I have a sorted list of r numbers from the integers { 0 .. n-1 }. I can encode the set using differences. For instance 3, 5, 5, 1024, 1025, 6000 --> 3, 2, 0, 1019, 1, 4975 These numbers say how many bins I skip over before taking each thing. The total of the differences will be < n. Invent a binary prefix code (means a distinct string of whole bits for each codeword) to further encode these differences, knowing r (how many there will be) and n (the limit on their total). The goal is to minimize the maximum size of the string of r codewords. Not to try for a smaller total than that, nor to worry about the size of individual codewords per se. Yet, the job is to design, given r and n, a single code to apply to all the differences individually. Then compare to the information-theoretical size: ( r + n - 1 )! log ( -------------- ) 2 r! ( n - 1 )! --Steve