Analogs of the Richard Stanley Amer. Math. Monthly Problem 11610
for ALL pairs of words of length, 2, in an alphabet of, 2
letters.
By Shalosh B. Ekhad
Proposition Number , 1, : Let a(n) be the number of n-lettered words
in the alphabet, {1, 2}
With as many occurrences of the substring (consecutive subword), [1, 1]
as those of, [1, 2]
Let P(t), be the ordinary generating function of a(n)
infinity
-----
\ n
P(t) = ) a(n) t
/
-----
n = 0
Then P=P(t) satisfies the quadratic equation
2 2 2 2
-t - (t - 1) (2 t - 1) (2 t + t + 1) P - (2 t - 1) (2 t + t + 1) (t - 1) P
= 0
Not only that, a(n) safisfies the following linear recurrence
2 2
(37 + 22 n + 3 n ) a(n + 4) (27 + 20 n + 3 n ) a(n + 3)
a(n + 5) = --------------------------- - ---------------------------
(n + 5) (n + 3) (n + 5) (n + 3)
2 2
(41 + 32 n + 5 n ) a(n + 2) 2 (26 + 23 n + 4 n ) a(n + 1)
+ --------------------------- - -----------------------------
(n + 5) (n + 3) (n + 5) (n + 3)
4 (n + 4) (n + 1) a(n)
+ ----------------------
(n + 5) (n + 3)
subject to the initial conditions
a[1] = 2, a[2] = 2, a[3] = 3, a[4] = 6, a[5] = 9
Finally, the asymptotics of a(n) to order, 4, is :
n 1/2 / 3 193 9945 2936619 \
0.56418958354776 2 (1/n) |1 + ---- + ------ + ------- + ---------|
| 16 n 2 3 4|
\ 512 n 8192 n 524288 n /
Note that everything is rigorous except the constant in front, 0.56418958354776
that is a mere non-rigorous estimate
Maple conjectures that its exact value
1
is equal to, -----
1/2
Pi
Sketch of proof: The above has been proved completely rigorously
internally, and I will spare you the details. If you insist you
can get them yourself by tracing the code, or else donate
50 dollars to the Society for the Liberation of Computerkind.
QED.
For the sake of people who want to use these formulas here
are the quardaric equation, recurrence operator, and asymptotics
in Maple input format
-t-(t-1)*(2*t-1)*(2*t^2+t+1)*P-(2*t-1)*(2*t^2+t+1)*(t-1)^2*P^2, [-4*(n+4)*(n+1)
/(n+5)/(n+3)+2*(26+23*n+4*n^2)/(n+5)/(n+3)*N-(41+32*n+5*n^2)/(n+5)/(n+3)*N^2+(
27+20*n+3*n^2)/(n+5)/(n+3)*N^3-(37+22*n+3*n^2)/(n+5)/(n+3)*N^4+N^5, [2, 2, 3, 6
, 9]], .56418958354776*2^n*(1/n)^(1/2)*(1+3/16/n+193/512/n^2+9945/8192/n^3+
2936619/524288/n^4)
For the sake of Sloane, here are the first 50 terms of the sequece
[1, 2, 2, 3, 6, 9, 15, 30, 54, 97, 189, 360, 675, 1304, 2522, 4835, 9358, 18193,
35269, 68568, 133737, 260802, 509132, 995801, 1948931, 3816904, 7483636,
14683721, 28827798, 56637969, 111347879, 219019294, 431043814, 848764585,
1672056525, 3295390800, 6497536449, 12816241994, 25289138108, 49918633705,
98568303577, 194692842346, 384675955966, 760266611407, 1502991025384,
2972085630055, 5878623677485, 11630395584040, 23015129434347,
45554191858072, 90185202686164]
Proposition Number , 2, : Let a(n) be the number of n-lettered words
in the alphabet, {1, 2}
With as many occurrences of the substring (consecutive subword), [1, 1]
as those of, [2, 2]
Let P(t), be the ordinary generating function of a(n)
infinity
-----
\ n
P(t) = ) a(n) t
/
-----
n = 0
Then P=P(t) satisfies the quadratic equation
2 3 2
1 - 4 t - 4 t + 2 (t + 1) (2 t - 1) P + (1 - 2 t) P = 0
Not only that, a(n) safisfies the following linear recurrence
2 a(n + 1) 4 (n - 1) a(n)
a(n + 2) = ---------- + --------------
n + 1 n + 1
subject to the initial conditions
a[1] = 2, a[2] = 2
Sketch of proof: The above has been proved completely rigorously
internally, and I will spare you the details. If you insist you
can get them yourself by tracing the code, or else donate
50 dollars to the Society for the Liberation of Computerkind.
QED.
For the sake of people who want to use these formulas here
are the quardaric equation, recurrence operator, and asymptotics
in Maple input format
1-4*t^2-4*t^3+2*(t+1)*(2*t-1)*P+(1-2*t)*P^2, [-4*(n-1)/(n+1)-2/(n+1)*N+N^2, [2,
2]], FAIL
For the sake of Sloane, here are the first 50 terms of the sequece
[1, 2, 2, 2, 4, 6, 12, 20, 40, 70, 140, 252, 504, 924, 1848, 3432, 6864, 12870,
25740, 48620, 97240, 184756, 369512, 705432, 1410864, 2704156, 5408312,
10400600, 20801200, 40116600, 80233200, 155117520, 310235040, 601080390,
1202160780, 2333606220, 4667212440, 9075135300, 18150270600, 35345263800,
70690527600, 137846528820, 275693057640, 538257874440, 1076515748880,
2104098963720, 4208197927440, 8233430727600, 16466861455200, 32247603683100,
64495207366200]
Proposition Number , 3, : Let a(n) be the number of n-lettered words
in the alphabet, {1, 2}
With as many occurrences of the substring (consecutive subword), [1, 2]
as those of, [2, 1]
Let P(t), be the ordinary generating function of a(n)
infinity
-----
\ n
P(t) = ) a(n) t
/
-----
n = 0
Then P=P(t) satisfies the algebaric equation
2
-1 + 2 t + (1 - 2 t) P = 0
Not only that, a(n) safisfies the following linear recurrence
a(n + 2) = 2 a(n + 1)
subject to the initial conditions
a[1] = 2, a[2] = 2
Finally, the asymptotics of a(n) to order, 4, is :
0.50000000000000000000000000000000000000000000000000000000000000000000000000\
n
00000000000000000000000026 2
Note that everything is rigorous except the constant in front, 0.500000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000026
that is a mere non-rigorous estimate
Sketch of proof: The above has been proved completely rigorously
internally, and I will spare you the details. If you insist you
can get them yourself by tracing the code, or else donate
50 dollars to the Society for the Liberation of Computerkind.
QED.
For the sake of people who want to use these formulas here
are the quardaric equation, recurrence operator, and asymptotics
in Maple input format
-1+2*t^2+(1-2*t)*P, [-2*N+N^2, [2, 2]], .50000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000026*2^n
For the sake of Sloane, here are the first 50 terms of the sequece
[1, 2, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472,
274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104,
8796093022208, 17592186044416, 35184372088832, 70368744177664,
140737488355328, 281474976710656, 562949953421312]
It took, 7.516, seconds to generate this book.