Author |
Topic: Find the limiting pattern (Read 315 times) |
|
gkwal
Newbie
Posts: 25
|
 |
Find the limiting pattern
« on: Jul 16th, 2007, 9:21pm » |
 Quote  Modify
|
Let S1=A, S2=ABB, S3=ABBAA, S4=ABBAAABBABB, S5=ABBAAABBABBABBAAABBAA, etc. be a sequence of strings such that Sn is formed from Sn-1 by replacing every A by ABB and every B by A. Find the limiting frequency of the pattern AAB among 3-letter patterns in Sn as n grows to infinity.
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
|
Re: Find the limiting pattern
« Reply #1 on: Jul 18th, 2007, 1:30am » |
Quote Modify
|
Let an, bn be the number of A's and B's in Sn. We have
an = an-1 + bn-1 = an-1 + 2an-2,
and this recurrence has solutions of the form
an = c*2n + d*(-1)n.
It follows from this that an ~ bn ~ c*2n as n goes to infinity.
Each AAB in Sn corresponds to a BA in Sn-1, and the BA's in Sn-1 correspond to the A's in Sn-2, except for the last A when Sn-2 ends in an A (when n is odd). So the ratio is
(an-2 - (1-(-1)n)/2)/(an+bn) ~ c*2n-2 / (c*2n + c*2n) = 1/8.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print