0
$\begingroup$

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?

  • 0
    @Gerry: I made a similar suggestion under [another one](http://math.stackexchange.com/questions/118834/how-to-count-using-polynomials-when-we-have-subsets-that-partially-overlap) 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.2012-03-19

1 Answers 1

1

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$.

[Edit:]

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.

  • 0
    never mind, hope chinese in these site know what i say and translate2012-03-20