Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume 5 distinguished balls drawn randomly to 4 distinguished boxes, one ball one box mark the ball number on the box after drawn and put back the ball back to the pool and then draw again

imagine boxes arranged like a string of characters, part of it, for example the string will be 3124 after ball drawn, any part of it do not allow to repeat, in this case 31, 24 do not repeat, if the string is 3131, then it is not allowed and should be drawn again as 31 is repeated

as the fix length not allow to be repeated is 2, How to polynomial count?

share|improve this question
Incomprehensible. Please discuss your question with someone who speaks your language, English, and Mathematics, and let her rewrite your question for you. –  Gerry Myerson Mar 19 '12 at 10:51
@Gerry: I made a similar suggestion under another one of the MP's questions; apparently that option is not available. I then suggested to post the question in Chinese in the hope that someone might translate it, but unfortunately no-one has. I found this one marginally more comprehensible than the other one and gave it a shot. –  joriki Mar 19 '12 at 12:13
add comment

1 Answer

up vote 1 down vote accepted

I'll rephrase the question as I understand it; please let me know if I've misunderstood.

You form a string of four digits; each digit is $1$, $2$, $3$, $4$ or $5$. You want to count the number of such strings that don't consist of two identical substrings of length $2$. (The question appears to contradict itself in that it first excludes any repetitions but then only excludes repetitions of period $2$; I'll only exclude repetitions of period $2$. Also I'm not sure whether by "polynomial count" you mean a polynomial in the number of balls that directly gives the count or a generating function; I'll assume the former.)

There are $5^4$ different strings of length $4$, $5^2$ different strings of length $2$ and thus $5^2$ different strings of length $4$ consisting of two identical substrings of length $2$. Thus the number of different strings of length $4$ without repetition of period $2$ is $5^4-5^2=5^2(5^2-1)=25\cdot24=600$.


I'm not sure this is what you're looking for; it seems quite an overkill to do this with generating functions; but you could do this: For a fixed number $k$ of digits, the number $a_n$ of strings of length $n$ is $k^n$. The corresponding generating function is $A(x)=\sum_nk^nx^n=1/(1-kx)$. Then the generating function for the number of strings of length $n$ consisting of two identical substrings is $A(x^2)=1/(1-kx^2)$. Substracting the two yields a generating function for the number of strings not consisting of two identical substrings, $B(x)=A(x)-A(x^2)=1/(1-kx)-1/(1-kx^2)$.

I doubt using the number of digits as a parameter for a generating function makes much sense, since it's strings being combined into longer strings, not digits being combined into more digits.

share|improve this answer
hope a generating function version –  M-Askman Mar 18 '12 at 8:15
would you mind calculating the generating function? –  M-Askman Mar 18 '12 at 8:59
@Marco: For a generating function, you need at least one parameter -- which parameter(s) do you want? The number of digits, or the length of the strings, or both? –  joriki Mar 18 '12 at 13:49
want 3 kind of generating function number of digits, or the length of the strings, or both , if possible –  M-Askman Mar 19 '12 at 3:31
@Marco: I added one using the length of the strings as a parameter -- I wonder whether this is what you had in mind; if not, I'm afraid you'll have to explain a bit more about what you're after. –  joriki Mar 19 '12 at 10:13
show 5 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.