The Nine Billion Names of God
Martin Julian DeMello
subject only to the constraint that you cannot have a run of k identical
letters? (e.g., for k=3, ABCCCDD is invalid)
--
Martin DeMello
Remove the sep_field from my address to reply
riverman
spoiler
.
.
.
.
.
.
.
.
.
.
.
.
. m^n(1-m^(1-k))
Note: this solution includes runs of 4,5,6, etc.
BTW: If this is HW, now you gotta figure out how I got this.. :-)
--
riverman
.........................
I think, therefore I thwim.
Carpe ropum.
Eyes on your own papers, please.
TwoBirds
>Martin Julian DeMello wrote:
>>
>> With an alphabet of m letters, how many n letter words can you form,
identical
[* a run = exactly one run]
>> letters? (e.g., for k=3, ABCCCDD is invalid)
>>
>> --
>> Martin DeMello
>>
>> Remove the sep_field from my address to reply
>
>spoiler
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>. m^n(1-m^(1-k))
>
>Note: this solution includes runs of 4,5,6, etc.
>
I think what you mean is that this counts the
number of such sequences that do not have
*exactly one* run of length k; i.e., sequences
with two or more runs of length k are counted.
David A Karr
>riverman wrote in message <36B756...@sorry.com>...
>>Martin Julian DeMello wrote:
>>> With an alphabet of m letters, how many n letter words can you form,
>>> subject only to the constraint that you cannot have a[*] run of k
I supposed this meant "at least one run."
>>. m^n(1-m^(1-k))
>>
>>Note: this solution includes runs of 4,5,6, etc.
>
>I think what you mean is that this counts the
>number of such sequences that do not have
>*exactly one* run of length k; i.e., sequences
>with two or more runs of length k are counted.
Even under that assumption the formula is still wrong. Try m = 2,
n = 3, k = 2.
--
David A. Karr "Groups of guitars are on the way out, Mr. Epstein."
ka...@shore.net --Decca executive Dick Rowe, 1962
Martin Julian DeMello
: riverman wrote in message <36B756...@sorry.com>...
: >Martin Julian DeMello wrote:
: >>
: >> With an alphabet of m letters, how many n letter words can you form,
: >> subject only to the constraint that you cannot have a[*] run of k
: [* a run = exactly one run]
Sorry - I meant that nowhere in the word could there be a run of k
letters.
TwoBirds
>TwoBirds <XXr...@ix.netcom.com> wrote:
>>riverman wrote in message <36B756...@sorry.com>...
>>>Martin Julian DeMello wrote:
>>>> With an alphabet of m letters, how many n letter words can you form,
>>>> subject only to the constraint that you cannot have a[*] run of k
>
>I supposed this meant "at least one run."
>
>>>. m^n(1-m^(1-k))
I read the proposed solution as (m^n)*(1 - m^(1-k)),
i.e., m^n - m^(n-k+1)
>>>
>>>Note: this solution includes runs of 4,5,6, etc.
>>
>>I think what you mean is that this counts the
>>number of such sequences that do not have
>>*exactly one* run of length k; i.e., sequences
>>with two or more runs of length k are counted.
>
>Even under that assumption the formula is still wrong. Try m = 2,
>n = 3, k = 2.
This gives m^n - m^(n-k+1) = 8 - 4 = 4, which seems correct if,
as I said, one interprets the problem as excluding only those sequences
having exactly one run of length 2.
The 4 cases marked with * are not excluded.
aaa *
aab
aba *
baa
abb
bab *
bba
bbb *
(I notice that the original poster has clarified the problem as not
intending
this interpretation.)
David A Karr
>>>>> With an alphabet of m letters, how many n letter words can you form,
>>>>> subject only to the constraint that you cannot have a[*] run of k
>
>This gives m^n - m^(n-k+1) = 8 - 4 = 4, which seems correct if,
>as I said, one interprets the problem as excluding only those sequences
>having exactly one run of length 2.
>
Ah, I see the difference in this case: you mean
"exactly one run of length *exactly* k."
In that case, try m = 2, n = 4, k = 2.
riverman
>
> TwoBirds <XXr...@ix.netcom.com> wrote:
> >>>>> With an alphabet of m letters, how many n letter words can you form,
> >>>>> subject only to the constraint that you cannot have a[*] run of k
> >[...]
> >
> >This gives m^n - m^(n-k+1) = 8 - 4 = 4, which seems correct if,
> >as I said, one interprets the problem as excluding only those sequences
> >having exactly one run of length 2.
Not quite. If a run includes, say 'aaa', (and k=3), then 'aaaa' and
'aaaaa' are also rejected. Any word which includes a run of k as a
<subset> is rejected.
In fact, if a word contains 2 sets of k, then it is rejected as it
contains one run of k.
> >
> >aaa * [not excluded]
>
> Ah, I see the difference in this case: you mean
> "exactly one run of length *exactly* k."
>
> In that case, try m = 2, n = 4, k = 2.
>
OK: by the equation, we have 2^4 - 2^(2-2+1) = 16-14 = 2
By brute force, we have:
aaaa bbaa aabb bbbb these are all 16 options. For k=2,
baaa baba abbb all are rejected except abab, and baba.
abaa baab babb I think it works.
aaba abba bbab
aaab abab bbba
riverman
.........................
I think, therefore I thwim.
Carpe ropum.
anyone got a calculator?
TwoBirds
>>>>>> With an alphabet of m letters, how many n letter words can you form,
>>>>>> subject only to the constraint that you cannot have a[*] run of k
>>[...]
>>
>>This gives m^n - m^(n-k+1) = 8 - 4 = 4, which seems correct if,
>>as I said, one interprets the problem as excluding only those sequences
>>having exactly one run of length 2.
>>
>
>Ah, I see the difference in this case: you mean
>"exactly one run of length *exactly* k."
IMHO, "Exactly one run of length k"
seldom refers to a run whose length is not k ;o)
>
>In that case, try m = 2, n = 4, k = 2.
That counter-example does succeed --
looks like riverman's solution fails.
riverman
(some utter nonsense)
> > In that case, try m = 2, n = 4, k = 2.
> >
>
> OK: by the equation, we have 2^4 - 2^(2-2+1) = 16-14 = 2
^^^^^^^^^ ^^
DON'T READ THE PREVIOUS POST!! I had started cleaning up my equation,
and the computer decided to mail the queud messages, which were not
finished!! I think I know where I went wrong: and the equation is
definately NOT right: it has to do with how we count things like 'aab b
b' where the 'aab' is not rejected, and the 'b b' is not either, but the
'aabbb' should be.
I withdraw my last post completely! I didn't mean it!!
--
riverman
Kent Parks
: OK: by the equation, we have 2^4 - 2^(2-2+1) = 16-14 = 2
Huh? This says 16-2=14; perhaps the formula calculates REJECTIONS?
: By brute force, we have:
: aaaa bbaa aabb bbbb these are all 16 options. For k=2,
: baaa baba abbb all are rejected except abab, and baba.
: abaa baab babb I think it works.
: aaba abba bbab
: aaab abab bbba
Kent
Martin Julian DeMello
: BTW: If this is HW, now you gotta figure out how I got this.. :-)
LOL! No, see the subject - it was inspired by the Clarke story (where,
IIRC, n=7 and m=3)
riverman
>
> In rec.puzzles riverman <nos...@sorry.com> wrote:
>
> : OK: by the equation, we have 2^4 - 2^(2-2+1) = 16-14 = 2
>
> Huh? This says 16-2=14; perhaps the formula calculates REJECTIONS?
>
Nah, at best this formula shows what happens when you think too quickly
at 1 am.
Here's where my thoughts came from, and maybe several minds can fix my
(embarassing) error:
Of course, there are m^n possible words of length n composable from an
alphabet of m letters.
To calculate how words with repeats of K are *prohibited*, I figured to
take K blanks, and combine them into one. That makes a word of (n-k+1)
length. In that 'triple blank',(which is indistinguishable in position
from any other), I counted how many ways a 'triple letter' could be
placed. There are M triple letters (aaa,bbb,ccc,ddd,..). So the number
of prohibited words should be m^(n-k+1). Hence, m^n - m^(n-k+1) are
remaining.
Contrary to some of the discussion, this does include runs of <more
than> K letters, as the basic run of K is included in the triple blank.
But what gets overlooked is when the triple letter is not excluded, but
it's neighbor completes a triple.
For example, my equation identifies 'aaa b b', but overlooks 'aab b b'.
What next?
--
riverman
.........................
riverman
>
>
> That counter-example does succeed --
> looks like riverman's solution fails.
Oh Yes, and miserably at that. See my other post "the 200 names of
God".
--
riverman
.........................
I think, therefore I thwim.
Carpe ropum.
...and thanks for rubbing it in.
TwoBirds
>>With an alphabet of m letters, how many n letter words can you form,
>>letters? (e.g., for k=3, ABCCCDD is invalid)
riverman wrote ...
>
>What next?
>
Frankly, I had forgotten how easy it is to pose difficult "runs" problems.
It would be nice to see that there is some simple solution to such a
simply stated problem, but I won't hold my breath. The problem is
surely discussed in some classical text like Feller, Uspensky, or Hajek.
(I was a bit surprised not to find anything like it in the math faq.)
One approach would be to seek some appropriate recursion relations:
We could write the solution as N(n,k)
where, suppressing the dependence on m,
N(n,k)=number of n-words, formed from an m-alphabet, containing
no k-runs (and therefore no runs of length k or greater -- a k-run
meaning any k consecutive occurrences of the same letter, possibly
as part of a longer run)
Now
N(n,2)=m*(m-1)^(n-1)
because there are m choices in the 1st spot, m-1 choices in the next
so as to differ from the 1st, m-1 in the next to differ from the 2nd, etc.
I haven't succeeded in doing the following (the hard part), but I believe
that N(n,3) can be expressed in terms of N(2,2), N(3,2), ...,N(n,2)
and similarly N(n,4) in terms of N(3,3), N(4,3), etc.
One hopes this would reveal a recursion something like
N(n,k) = f ( N(k-1,k-1), N(k,k-1), ..., N(n,k-1) )
etc.
At least the stars haven't yet disappeared (re A.C.Clark). LOL
TwoBirds
>[...]
>here is where my
>own thoughts are going, in line with my 'compound letter' idea:
>
>To count the prohibited words, create a compound letter of k-1. That
>would be m^(n-k+2) possibile words with this compound letter. Then
>count the ways to make the letter on either side match the compound
>letter. That would be 2.
>
>So N(n,k) is m^n - m^(n-k+2) + 2, which works with m=2, n=4, k=2, and
>also with k=3.
>
>
>...but its 2 am and I'm fading. And last night at this time I was way
>off base.
>
Alas, for m=3 and n=k=2, there are N=6 acceptable cases, whereas your
formula gives 3^2 - 3^2 + 2 = 2.
riverman
>
> As part of the thread originated by Martin DeMello's posting:
> >>With an alphabet of m letters, how many n letter words can you form,
> >>subject only to the constraint that you cannot have a run of k identical
> >>letters? (e.g., for k=3, ABCCCDD is invalid)
>
> riverman wrote ...
> >
> >What next?
> >
>
> Frankly, I had forgotten how easy it is to pose difficult "runs" problems.
> It would be nice to see that there is some simple solution to such a
> simply stated problem, but I won't hold my breath. The problem is
> surely discussed in some classical text like Feller, Uspensky, or Hajek.
> (I was a bit surprised not to find anything like it in the math faq.)
Or in any of my Probability texts..I agree that we want be surprised to
find that its some sort of balls-in-bins solution, but I think it might
not be that simple, either.
>
> One approach would be to seek some appropriate recursion relations:
>
> We could write the solution as N(n,k)
> where, suppressing the dependence on m,
>
> N(n,k)=number of n-words, formed from an m-alphabet, containing
> no k-runs (and therefore no runs of length k or greater -- a k-run
> meaning any k consecutive occurrences of the same letter, possibly
> as part of a longer run)
>
> Now
> N(n,2)=m*(m-1)^(n-1)
> because there are m choices in the 1st spot, m-1 choices in the next
> so as to differ from the 1st, m-1 in the next to differ from the 2nd, etc.
>
> I haven't succeeded in doing the following (the hard part), but I believe
> that N(n,3) can be expressed in terms of N(2,2), N(3,2), ...,N(n,2)
> and similarly N(n,4) in terms of N(3,3), N(4,3), etc.
>
> One hopes this would reveal a recursion something like
> N(n,k) = f ( N(k-1,k-1), N(k,k-1), ..., N(n,k-1) )
> etc.
>
Interesting....I'm going to think on that angle. But here is where my
own thoughts are going, in line with my 'compound letter' idea:
To count the prohibited words, create a compound letter of k-1. That
would be m^(n-k+2) possibile words with this compound letter. Then
count the ways to make the letter on either side match the compound
letter. That would be 2.
So N(n,k) is m^n - m^(n-k+2) + 2, which works with m=2, n=4, k=2, and
also with k=3.
...but its 2 am and I'm fading. And last night at this time I was way
off base.
The stars are shining brightly tonight...
riverman
.........................
.
TwoBirds
>Martin DeMello asked ...
>>With an alphabet of m letters, how many n letter words can you form,
>>subject only to the constraint that you cannot have a run of k identical
>>letters? (e.g., for k=3, ABCCCDD is invalid)
>
>
>We could write the solution as N(n,k)
>where, suppressing the dependence on m,
>
>N(n,k)=number of n-words, formed from an m-alphabet, containing
>no k-runs (and therefore no runs of length k or greater -- a k-run
>meaning any k consecutive occurrences of the same letter, possibly
>as part of a longer run)
>
>Now
>N(n,2)=m*(m-1)^(n-1)
>because there are m choices in the 1st spot, m-1 choices in the next
>so as to differ from the 1st, m-1 in the next to differ from the 2nd, etc.
>
Further suppressing the dependence on k as well as m, and just writing
N(n) for N(n,k), let the number of prohibited words be P(n)=m^n - N(n).
Then
P(n+1) = m*P(n) + (m-1)*( m^(n-k+1) - P(n-k+1) )
for k < n-k+1, i.e., k<(n-1)/2.
My reasoning is that when n is increased by one, there will be m additional
prohibited words for each word already prohibited, and one further
prohibited
word for each word not already prohibited but ending in a (k-1)-run.
The latter condition is accounted for by N(n-k+1)=m^(n-k+1) - P(n-k+1)
of the n-words having no k-runs in the first n-k+1 letters, and ending in a
(k-1)-run in a letter that must differ from the (n-k+1)st letter.
I tested this recursion with the k=2 result that I obtained above, in which
P(n)=m^n - m*(m-1)^(n-1), and it checked -- that's a comfort at least.
Substituting P(n)=m^n - N(n), the recursion simplifies further to
N(n+1) = m*N(n) + (m-1)*N(n-k+1), k<(n+1)/2
I'm rusty on this, but I believe this means we need to look for a real root
of
x^(n+1) - m*x^n - (m-1)*x^(n-k+1) = 0.
riverman
>
> riverman wrote
> >[...]
> >here is where my
> >own thoughts are going, in line with my 'compound letter' idea:
> >
> >To count the prohibited words, create a compound letter of k-1. That
> >would be m^(n-k+2) possibile words with this compound letter. Then
> >count the ways to make the letter on either side match the compound
> >letter. That would be 2.
> >
> >So N(n,k) is m^n - m^(n-k+2) + 2, which works with m=2, n=4, k=2, and
> >also with k=3.
> >
> >
> >...but its 2 am and I'm fading. And last night at this time I was way
> >off base.
> >
>
> formula gives 3^2 - 3^2 + 2 = 2.
Ah, yes, alas. But I still think I'm on to something.
Similar to your notation of N(n,k) being the amount of n-length words
without <at least> k-length repetitions, let E(n,k) be the amount of
n-length words without <exactly> k-length repetitions, supressing m.
Then N(n,k) = m^n - E(n,k) - E(n,k+1) - E(n,k+2) - ... - E(n,n)
I don't have time to chase this now, but the next steps are to find the
formula for E(n,p) for any p, then to find the recursion.
They both seem do-able, but then again, Fermat said that, too.
--
riverman
.........................
I think, therefore I thwim.
Carpe ropum.
The answer is in the margin.
QSCGZ
you might want to check them , before you post
formulas or recurrences !
n = stringlength
m = size of alphabet
k = length of run
N(n,m,k) = number of n-m-strings without k-run
n = 1
m = 1 , N(1,1,1..2) = : 0,1
m = 2 , N(1,2,1..2) = : 0,2
m = 3 , N(1,3,1..2) = : 0,3
...
------------------------------
n = 2
m = 1 , N(2,1,1..3) = : 0,0,1
m = 2 , N(2,2,1..3) = : 0,2,4
m = 3 , N(2,3,1..3) = : 0,6,9
m = 4 , N(2,4,1..3) = : 0,12,16
...
------------------------------
n = 3
m = 1 , N(3,1,1..4) = : 0,0,0,1
m = 2 , N(3,2,1..4) = : 0,2,6,8
m = 3 , N(3,3,1..4) = : 0,12,24,27
m = 4 , N(3,4,1..4) = : 0,36,60,64
m = 5 , N(3,5,1..4) = : 0,80,120,125
...
------------------------------
n = 4
m = 1 , N(4,1,1..5) = : 0,0,0,0,1
m = 2 , N(4,2,1..5) = : 0,2,10,14,16
m = 3 , N(4,3,1..5) = : 0,24,66,78,81
m = 4 , N(4,4,1..5) = : 0,108,228,252,256
m = 5 , N(4,5,1..5) = : 0,320,580,620,625
m = 6 , N(4,6,1..5) = : 0,750,1230,1290,1296
...
------------------------------
n = 5
m = 1 , N(5,1,1..6) = : 0,0,0,0,0,1
m = 2 , N(5,2,1..6) = : 0,2,16,26,30,32
m = 3 , N(5,3,1..6) = : 0,48,180,228,240,243
m = 4 , N(5,4,1..6) = : 0,324,864,996,1020,1024
m = 5 , N(5,5,1..6) = : 0,1280,2800,3080,3120,3125
m = 6 , N(5,6,1..6) = : 0,3750,7200,7710,7770,7776
m = 7 , N(5,7,1..6) = : 0,9072,15876,16716,16800,16807
...
------------------------------
n = 6
m = 1 , N(6,1,1..7) = : 0,0,0,0,0,0,1
m = 2 , N(6,2,1..7) = : 0,2,26,48,58,62,64
m = 3 , N(6,3,1..7) = : 0,96,492,666,714,726,729
m = 4 , N(6,4,1..7) = : 0,972,3276,3936,4068,4092,4096
m = 5 , N(6,5,1..7) = : 0,5120,13520,15300,15580,15620,15625
m = 6 , N(6,6,1..7) = : 0,18750,42150,46080,46590,46650,46656
m = 7 , N(6,7,1..7) = : 0,54432,109116,116718,117558,117642,117649
m = 8 , N(6,8,1..7) = : 0,134456,247352,260736,262024,262136,262144
...
------------------------------
n = 7
m = 1 , N(7,1,1..8) = : 0,0,0,0,0,0,0,1
m = 2 , N(7,2,1..8) = : 0,2,42,88,112,122,126,128
m = 3 , N(7,3,1..8) = : 0,192,1344,1944,2124,2172,2184,2187
m = 4 , N(7,4,1..8) = : 0,2916,12420,15552,16224,16356,16380,16384
m = 5 , N(7,5,1..8) = : 0,20480,65280,76000,77800,78080,78120,78125
m = 6 , N(7,6,1..8) = : 0,93750,246750,275400,279360,279870,279930,279936
m = 7 , N(7,7,1..8) = : 0,326592,749952,814968,822612,823452,823536,823543
m = 8 , N(7,8,1..8) = :
0,941192,1950984,2082304,2095744,2097032,2097144,2097152
m = 9 , N(7,9,1..8) = :
0,2359296,4515840,4758912,4780944,4782816,4782960,4782969
...
------------------------------
...
Martin Julian DeMello
: Interesting....I'm going to think on that angle. But here is where my
: own thoughts are going, in line with my 'compound letter' idea:
: To count the prohibited words, create a compound letter of k-1. That
: would be m^(n-k+2) possibile words with this compound letter. Then
: count the ways to make the letter on either side match the compound
: letter. That would be 2.
I started working along those lines, but got stuck at the problem of multiple compound letters.
For example if k=3, AAA...BBB. would get counted twice (once for each block being the compound
letter), and then there are runs like AAAAA...BBBB..CCC which are either included or excluded
depending on some sort of parity argument - I'm beginning to fear that the solution won't be in
a closed form.
I'm currently trying something along the lines of N(m,n,k) = f(n-1, with a superletter anywhere)
+ g(n-1, with a run of k-1 at the beginning). I think that covers all the cases, but I could be
wrong.
TwoBirds
TwoBirds wrote in message <79bs2g$5...@dfw-ixnews12.ix.netcom.com>...
>TwoBirds wrote ...
>>Martin DeMello asked ...
>>>With an alphabet of m letters, how many n letter words can you form,
>>>subject only to the constraint that you cannot have a run of k identical
>>>letters? (e.g., for k=3, ABCCCDD is invalid)
>>
>>One approach would be to seek some appropriate recursion relations:
>>
>>We could write the solution as N(n,k)
>>where, suppressing the dependence on m,
>>
>>N(n,k)=number of n-words, formed from an m-alphabet, containing
>>no k-runs (and therefore no runs of length k or greater -- a k-run
>>meaning any k consecutive occurrences of the same letter, possibly
>>as part of a longer run)
>>
>>Now
>>N(n,2)=m*(m-1)^(n-1)
>>because there are m choices in the 1st spot, m-1 choices in the next
>>so as to differ from the 1st, m-1 in the next to differ from the 2nd, etc.
>>
>
>
>Further suppressing the dependence on k as well as m, and just writing
>N(n) for N(n,k), let the number of prohibited words be P(n)=m^n - N(n).
>Then
>
>P(n+1) = m*P(n) + (m-1)*( m^(n-k+1) - P(n-k+1) )
>for k < n-k+1, i.e., k<(n-1)/2.
this should be k<(n+1)/2
>
>My reasoning is that when n is increased by one, there will be m additional
>prohibited words for each word already prohibited, and one further
>prohibited
>word for each word not already prohibited but ending in a (k-1)-run.
>The latter condition is accounted for by N(n-k+1)=m^(n-k+1) - P(n-k+1)
>of the n-words having no k-runs in the first n-k+1 letters, and ending in a
>(k-1)-run in a letter that must differ from the (n-k+1)st letter.
>
>I tested this recursion with the k=2 result that I obtained above, in which
>P(n)=m^n - m*(m-1)^(n-1), and it checked -- that's a comfort at least.
>
>Substituting P(n)=m^n - N(n), the recursion simplifies further to
>
>N(n+1) = m*N(n) + (m-1)*N(n-k+1), k<(n+1)/2
There is a sign mistake here, and the recursion should be
N(n+1) = m*N(n) - (m-1)*N(n-k+1), k<(n+1)/2
I also checked this successfully for several cases of n,m,k in the table
posted by "QSCGZ" in another part of this thread.
>
>I'm rusty on this, but I believe this means we need to look for a real root
>of
>
>x^(n+1) - m*x^n - (m-1)*x^(n-k+1) = 0.
similarly,
x^(n+1) - m*x^n + (m-1)*x^(n-k+1) = 0.
TwoBirds
>here are some N() numbers found with brute search.
>you might want to check them , before you post
>formulas or recurrences !
>
>
> n = stringlength
> m = size of alphabet
> k = length of run
> N(n,m,k) = number of n-m-strings without k-run
Thanks for posting this!
For the several cases of n,m,k that I checked, these values agree with the
results I obtained in another part of this thread:
N(n+1) = m*N(n) - (m-1)*N(n-k+1), k<(n+1)/2
and the special case
N(n) = m*(m-1)^(n-1), for k=2.
It would be nice if someone with the books by Feller, or perhaps Knuth,
would
do a quick check to see if they discuss this problem -- it's got to be a
classic.
Martin Julian DeMello
: I'm currently trying something along the lines of
: N(m,n,k) = f(n-1, with a superletter anywhere) + g(n-1, with a run of
: k-1 at the beginning). I think that covers all the cases, but I could be
: wrong.
And following up: the recursion proved pretty easy to formulate, but I
can't solve it.
Let N(n) be the number of valid n letter words, and U(n) be the number of
unacceptable ones.
Then U(n) = m U(n-1) + m N(n-k)
Reasoning: If there is an invalid word of length n-1, adding any of the m
letters to the beginning will leave it invalid.
Also, if there is a valid n-1 letter word, beginning with a run of k-1
letters, adding the run letter to the beginning renders it invalid. But
this is equivalent to taking a valid (n-k) letter word ad adding k of any
letter to the start. Hence m N(n-k)
Now we have U(n) + N(n) = m^n
So U(n) = m U(n-1) + m m^(n-k) - m U(n-k)
= m U(n-1) - m U(n-k) + m^(n-k+1)
And the termination condition is U(n<k)=0, U(n=k)=m
However, attempts to solve it led rapidly to partition functions[1], and I
got thoroughly lost.
[1] consider the recurrence as a tree. then every node at depth r branches
into 3 nodes, U(r-1), U(r-k) and m^(r-k). Each will be multiplied by a
factor m^p, where p is the number of steps between n and r, step sizes
being either 1 or k. Furthermore every step of k adds a - sign. So we have
to sum over multiple functions of the sort that count how many ways a
string of 1s and ks can be arranged to give n, then sum over the number of
ways such functions can be permuted etc. etc.
Overhead, without any fuss, the dark matter is thinning :)
TwoBirds
on whether m or m-1 should be the multiplier in the second term of the
recursion (see below). It is customary to cite the work of others when
you use it.
Martin Julian DeMello wrote in message <79d3cu$joo$1...@joe.rice.edu>...
>Martin Julian DeMello (mdem...@rice.edu) wrote:
>
>: I'm currently trying something along the lines of
>: N(m,n,k) = f(n-1, with a superletter anywhere) + g(n-1, with a run of
>: k-1 at the beginning). I think that covers all the cases, but I could be
>: wrong.
>
>And following up: the recursion proved pretty easy to formulate, but I
>can't solve it.
>
>Let N(n) be the number of valid n letter words, and U(n) be the number of
>unacceptable ones.
>
>Then U(n) = m U(n-1) + m N(n-k)
>
>Reasoning: If there is an invalid word of length n-1, adding any of the m
>letters to the beginning will leave it invalid.
>
>Also, if there is a valid n-1 letter word, beginning with a run of k-1
>letters, adding the run letter to the beginning renders it invalid. But
>this is equivalent to taking a valid (n-k) letter word ad adding k of any
>letter to the start. Hence m N(n-k)
>
This is what I had already posted:
::Further suppressing the dependence on k as well as m, and just writing
::N(n) for N(n,k), let the number of prohibited words be P(n)=m^n - N(n).
::Then
::
::P(n+1) = m*P(n) + (m-1)*( m^(n-k+1) - P(n-k+1) )
[...]
::My reasoning is that when n is increased by one, there will be m
additional
::prohibited words for each word already prohibited, and one further
::prohibited
::word for each word not already prohibited but ending in a (k-1)-run.
::The latter condition is accounted for by N(n-k+1)=m^(n-k+1) - P(n-k+1)
::of the n-words having no k-runs in the first n-k+1 letters, and ending in
a
::(k-1)-run in a letter that must differ from the (n-k+1)st letter.
::
::I tested this recursion with the k=2 result that I obtained above, in
which
::P(n)=m^n - m*(m-1)^(n-1), and it checked -- that's a comfort at least.
::
[...]
:I also checked this successfully for several cases of n,m,k in the table
:posted by "QSCGZ" in another part of this thread.
Matt McLelland
> You are repeating what I had already posted, except only that we differ
> on whether m or m-1 should be the multiplier in the second term of the
> recursion (see below).
... and it should be noted that your recurrence was correct, his was not.
> It is customary to cite the work of others when you use it.
Maybe we can blame the net lag.
> >Then U(n) = m U(n-1) + m N(n-k)
The last m should be m-1.
> >Also, if there is a valid n-1 letter word, beginning with a run of k-1
> >letters, adding the run letter to the beginning renders it invalid. But
> >this is equivalent to taking a valid (n-k) letter word and adding k of any
> >letter to the start. Hence m N(n-k)
Not any letter. Any letter other than the first letter of the n-k letter word.
Martin Julian DeMello
: You are repeating what I had already posted, except only that we differ
: on whether m or m-1 should be the multiplier in the second term of the
: you use it.
If I'd used your work, I would have cheerfully cited it - in fact, your
post hit my server after I'd sent mine out. AAMOF, I prolly wouldn't even
have bothered posting, especially if (as it appears) your recurrence
rather than mine is right (I missed the point that after stripping away
the k-1 run, you would have one fewer letter to use, and the table of
values hasn't reached here yet).
Note too that I was merely casting into algebraic terms an idea proposed
in a previous post of mine. If you like I'll mail you the paper on which I
worked it out :) If you'd like credit for the recurrence, go ahead - mine
was wrong anyway.
ObPuzzle: Cast it into closed form :)
TwoBirds
Let's hope that at least *one* of our recursions is correct and leads to
further results!
Martin Julian DeMello wrote in message <79d9pa$mrd$1...@joe.rice.edu>...
>TwoBirds (XXr...@ix.netcom.com) wrote:
>: You are repeating what I had already posted, except only that we differ
>: on whether m or m-1 should be the multiplier in the second term of the
>: recursion (see below). It is customary to cite the work of others when
>: you use it.
>
>If I'd used your work, I would have cheerfully cited it - in fact, your
>post hit my server after I'd sent mine out. [...]
TwoBirds
earlier in this thread, confirming it for the values in the table posted by
"QSCGZ".
To summarize, letting
N(n)= # n-words from an m-alphabet, containing no k-runs
P(n)= # n-words from an m-alphabet, containing at least one k-run
so that P(n) = m^n - N(n),
we have for n=k+1,k+2,k+2... ; k=1,2,3,... ; m=1,2,3,... :
N(n) = m*N(n-1) - (m-1)*N(n-k)
with N(n<k)=m^k, N(n=k)=m^k - m
or equivalently,
P(n)=m*P(n-1) - (m-1)*P(n-k) + (m-1)*m^(n-k)
with P(n<k)=0, P(n=k)=m.
This recursion is consistent with the following cases already known:
k=1 => then P(n)=0
k=2 => then N(n)=m(m-1)^(n-1)
k=n => then P(n)=m
k<n => then P(n)=0.
Kurt Foster
. With an alphabet of m letters, how many n letter words can you form,
. subject only to the constraint that you cannot have a run of k identical
. letters? (e.g., for k=3, ABCCCDD is invalid)
The following approach seems plausible: For a given positive integer n,
select a positive integer r, and consider the sums (if any) of positive
integers s_1 < k, s_2 < k, ... s_r < k, such that
s_1 + s_2 + ... + s_r = n.
For each such sum, there are m * (m-1)^(r-1) ways of creating a string of
n letters consisting of s_1 occurrences of one letter, followed by s_2
occurrences of another letter, and so on, with no two consecutive groups
having the same letter. Calling the number of such r-term sums g(n, r, k),
we have
f(n, m, k) = SUM, r >= 1, m*(m-1)^(r-1) * g(n, r, k).
Now g(n, r, k) is simply the coefficient of x^n in the expansion of
[x + x^2 + ... + x^(k-1)]^r.
It follows that f(n, m, k) is the coefficient of x^n in
SUM, r >=1, m*(m-1)^(r-1) * (x + x^2 + ... + x^(k-1))^r
which (assuming |x| is small enough) converges to
(A) [m*(x + x^2 + ... + x^(k-1)]/[1 - (m-1)*(x + x^2 + ... + x^(k-1))].
If we assume m and k are given, we may suppress the dependence of f on
these variables, and write f(n) for f(n, m, k). We than have the linear
recurrence
(B) f(n+k-1) = (m-1)[f(n+k-2) + f(n+k-3) + ... + f(n)].
The "initial conditions" for (B) "should be" f(r) = m^r for 1 =< r < k;
and by multiplying the numerator and denominator of (A) by (1-x) we obtain
(A') m*(x - x^k)/[ 1 - (m*x - (m-1)*x^k)],
from which we see that the coefficient of x^r is indeed m^r for 1 =< r < k.
One may check that these formulas give f(n, 2, 2) = 2 for every positive
integer n, which is correct; since the only strings of (say) 1's and 0's
with neither two consecutive 1's nor two consecutive 0's, are the
"alternating" strings 010101... and 101010... . The formulas also give the
correct expression for f(n, m, 2), m*(m-1)^(n-1), for every m >= 2.
QSCGZ
---------------------
I've always been wondering , whether there is some software,
that solves such problems automatically.
I meen, we can just calculate some dozends of such numbers for
small m,n,k and then look for patterns.
There _should_ be some programs out there , which check such numbers
for the most common patterns like polynomials,factorials,sums,
alternating sums,products,binomials,fibonaccis, etc.
---------------------------
twobirds wrote:
> N(n+1) = m*N(n) - (m-1)*N(n-k+1)
> and N(n) = m*(m-1)^(n-1), for k=2.
looks Fibonacci-like.
>I'm rusty on this, but I believe this means we need to look for a
> real root of
> x^(n+1) - m*x^n + (m-1)*x^(n-k+1) = 0.
x=0 or x^k-m*x^(k-1)+m-1=0 .. (?)
> It would be nice if someone with the books by Feller, or perhaps Knuth,
> would do a quick check to see if they discuss this problem -- it's got
> to be a classic.
I haven't these books. But I checked Sloane's Database and didn't find
these numbers.
-----------------------
if instead , we keep k and n fixed and form
y(n,m,k)=(N(n,m,k)-N(n,m,k-1))/m/(m-1) ,
then the y(n,m,k) are polynomials in m of degree n-k.
For n=2..8 we get : (k=2..n)
1
m,2
m^2,3m+ 1, 2
m^3,4m^2+ 3m, 3m+ 2, 2
m^4,5m^3+ 6m^2+ m, 4m^2+ 6m+1, 3m+ 2, 2
m^5,6m^4+10m^3+ 4m^2, 5m^3+12m^2+ 6m, 4m^2+ 6m+ 1, 3m+ 2, 2
m^6,7m^5+15m^4+10m^3+m^2,6m^4+20m^3+18m^2+3m,5m^3+12m^2+9m+1,4m^2+6m+1,3m+2,2
this leaves to find the patterns in the coefficients ,
which seem again to be polynomials ...(etc.?)
qscgz