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
    Incomprehensible. Please discuss your question with someone who speaks your language, English, and Mathematics, and let her rewrite your question for you.2012-03-19
  • 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
    hope a generating function version2012-03-18
  • 0
    would you mind calculating the generating function?2012-03-18
  • 0
    @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?2012-03-18
  • 0
    want 3 kind of generating function number of digits, or the length of the strings, or both , if possible2012-03-19
  • 0
    @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.2012-03-19
  • 0
    actually is not only two identical substring, it is that there is no any two identical substring2012-03-19
  • 0
    After read your answer, i understand if length of string is 5 and fixed length not repeat is 3, 5*x+5^2*x^2+5^3*x^3+5^4*x^4+5^5*x^5-(3*x^2+3^2*x^(2*2)+3^3*x^(2*3)+3^4*x^(2*4)+3^5*x^(2*5)) if i am wrong, please fix.2012-03-19
  • 0
    though minus two identical substring, do it need to minus three identical substring or more in order to eliminate cases, if length of whole string is long?2012-03-19
  • 0
    @Marco: I'm truly sorry, I'd love to help you, and I'm sure this must be rather frustrating to you, but unfortunately your English is close to incomprehensible. It's not just individual mistakes, the lack of grammatical structural and unusual choice of words makes it very difficult to guess what you're trying to say. I tried to find someone who might be able to translate from Chinese in your other question, but without success. I'm afraid you're just going to have to improve your English or look for help from native Chinese speakers. I wish I spoke Chinese so I could help but I don't...2012-03-19
  • 0
    never mind, hope chinese in these site know what i say and translate2012-03-20