Analogs of the Richard Stanley Amer. Math. Monthly Problem 11610 for ALL pairs of words of length, 2, in an alphabet of, 3 letters. By Shalosh B. Ekhad Proposition Number , 1, : Let a(n) be the number of n-lettered words in the alphabet, {1, 2, 3} 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 3 2 -t - (3 t - 1) (3 t + t + t - 1) P 3 2 2 - (3 t - 1) (2 t - 1) (3 t + t + t - 1) P = 0 Not only that, a(n) safisfies the following linear recurrence 2 3 2 (-78 + 97 n + 80 n + 12 n ) a(n + 4) a(n + 5) = --------------------------------------- 2 (n + 5) (4 n + 8 n - 9) 2 3 2 2 (-15 + 173 n + 128 n + 20 n ) a(n + 3) 4 (4 n + 4 n + 3) a(n + 2) - ----------------------------------------- + --------------------------- 2 2 (n + 5) (4 n + 8 n - 9) 4 n + 8 n - 9 2 3 9 (-29 + 3 n + 20 n + 4 n ) a(n + 1) - ------------------------------------- 2 (n + 5) (4 n + 8 n - 9) 2 18 (n + 1) (4 n + 16 n + 3) a(n) + --------------------------------- 2 (n + 5) (4 n + 8 n - 9) subject to the initial conditions a[1] = 3, a[2] = 7, a[3] = 18, a[4] = 47, a[5] = 123 Finally, the asymptotics of a(n) to order, 4, is : n 1/2 / 7 481 27085 8567979 \ 0.846284375322 3 (1/n) |1 + --- + ------ + ------- + --------| | 8 n 2 3 4| \ 128 n 1024 n 32768 n / Note that everything is rigorous except the constant in front, 0.846284375322 that is a mere non-rigorous estimate Maple conjectures that its exact value 3 is equal to, ------- 1/2 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-(3*t-1)*(3*t^3+t^2+t-1)*P-(3*t-1)*(2*t-1)*(3*t^3+t^2+t-1)*P^2, [-18*(n+1)*(4 *n^2+16*n+3)/(n+5)/(4*n^2+8*n-9)+9*(-29+3*n+20*n^2+4*n^3)/(n+5)/(4*n^2+8*n-9)*N -4*(4*n^2+4*n+3)/(4*n^2+8*n-9)*N^2+2*(-15+173*n+128*n^2+20*n^3)/(n+5)/(4*n^2+8* n-9)*N^3-2*(-78+97*n+80*n^2+12*n^3)/(n+5)/(4*n^2+8*n-9)*N^4+N^5, [3, 7, 18, 47, 123]], .846284375322*3^n*(1/n)^(1/2)*(1+7/8/n+481/128/n^2+27085/1024/n^3+ 8567979/32768/n^4) For the sake of Sloane, here are the first 50 terms of the sequece [1, 3, 7, 18, 47, 123, 328, 886, 2419, 6675, 18587, 52164, 147404, 418991, 1197002, 3434568, 9891715, 28580469, 82808899, 240511642, 700024987, 2041255981, 5962023006, 17439034426, 51075928264, 149767494573, 439619556301, 1291671623988, 3798447661874, 11179106282223, 32925086562548, 97037818165796, 286172291838827, 844436948190849, 2493117000312793, 7364416807779786, 21764081804718227, 64348138175413289, 190332869113455848, 563200879565499326, 1667151343073733519, 4936738796794820477, 14623477090967810633, 43331040183953714352, 128433612979313434298, 380787836063948726565, 1129292215828454240074, 3349986339881616145644, 9940038785825422125280, 29500998214555495948039, 87575876235306559481287] Proposition Number , 2, : Let a(n) be the number of n-lettered words in the alphabet, {1, 2, 3} 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 3 2 2 1 - 6 t - 7 t - t - 2 (3 t - 1) (2 t - 1) (t + 1) P 2 2 - (3 t - 1) (2 t - 1) (t + 1) (t + t - 1) P = 0 Not only that, a(n) safisfies the following linear recurrence (16 + 3 n) a(n + 5) 2 (3 n + 7) a(n + 4) (57 + 17 n) a(n + 3) a(n + 6) = ------------------- + -------------------- - -------------------- n + 5 n + 5 n + 5 (18 + 11 n) a(n + 2) 10 (5 + 2 n) a(n + 1) 12 (n + 2) a(n) - -------------------- + --------------------- + --------------- n + 5 n + 5 n + 5 subject to the initial conditions a[1] = 3, a[2] = 7, a[3] = 17, a[4] = 43, a[5] = 109, a[6] = 285 Finally, the asymptotics of a(n) to order, 4, is : n 1/2 / 113 64153 5859631 2956478259 \ 0.655529058355 3 (1/n) |1 + ---- + -------- + --------- + -----------| | 80 n 2 3 4| \ 12800 n 204800 n 13107200 n / Note that everything is rigorous except the constant in front, 0.655529058355 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-6*t^3-7*t^2-t-2*(3*t-1)*(2*t-1)*(t+1)^2*P-(3*t-1)*(2*t-1)*(t+1)*(t^2+t-1)*P^2 , [-12*(n+2)/(n+5)-10*(5+2*n)/(n+5)*N+(18+11*n)/(n+5)*N^2+(57+17*n)/(n+5)*N^3-2 *(3*n+7)/(n+5)*N^4-(16+3*n)/(n+5)*N^5+N^6, [3, 7, 17, 43, 109, 285]], .65552905\ 8355*3^n*(1/n)^(1/2)*(1+113/80/n+64153/12800/n^2+5859631/204800/n^3+2956478259/ 13107200/n^4) For the sake of Sloane, here are the first 50 terms of the sequece [1, 3, 7, 17, 43, 109, 285, 753, 2029, 5529, 15265, 42531, 119557, 338357, 963447, 2756727, 7921673, 22843917, 66078463, 191637251, 557045705, 1622405135, 4733543307, 13831907295, 40473954863, 118578027369, 347789276215, 1021094753633, 3000649670809, 8825309734939, 25976499888045, 76514058832783, 225521956773155, 665124435402201, 1962750914283707, 5795077474288769, 17118680228967457, 50592353108331319, 149585975506995893, 442463225133558271, 1309283366767710583, 3875707501147524891, 11476796173230341795, 33996546806949604045, 100736332981611619903, 298584965866408363291, 885266366309463476241, 2625417788325860699013, 7788178849022677582063, 23109013644368291545269, 68585166897280660832285] Proposition Number , 3, : Let a(n) be the number of n-lettered words in the alphabet, {1, 2, 3} With as many occurrences of the substring (consecutive subword), [1, 1] as those of, [2, 3] 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 4 2 -t + (3 t - 1) (t - 1) P - (3 t - 1) (t - 1) P = 0 Not only that, a(n) safisfies the following linear recurrence a(n + 4) = 2 (n + 7) a(n + 2) 4 (n + 1) a(n + 1) 3 (n + 2) a(n) 4 a(n + 3) - ------------------ - ------------------ + -------------- n + 4 n + 4 n + 4 subject to the initial conditions a[1] = 3, a[2] = 7, a[3] = 16, a[4] = 38 Finally, the asymptotics of a(n) to order, 4, is : n 1/2 / 7 445 19945 4852659 \ 0.73290376785438 3 (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.73290376785438 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 -t+(3*t-1)*(t-1)^2*P-(3*t-1)*(t-1)^4*P^2, [-3*(n+2)/(n+4)+4*(n+1)/(n+4)*N+2*(n+ 7)/(n+4)*N^2-4*N^3+N^4, [3, 7, 16, 38]], .73290376785438*3^n*(1/n)^(1/2)*(1+7/ 16/n+445/512/n^2+19945/8192/n^3+4852659/524288/n^4) For the sake of Sloane, here are the first 50 terms of the sequece [1, 3, 7, 16, 38, 95, 248, 668, 1838, 5131, 14470, 41112, 117475, 337203, 971515, 2807744, 8136090, 23630215, 68768210, 200481036, 585381973, 1711647959, 5011157073, 14687848012, 43095321203, 126565380735, 372030471493, 1094437253428, 3221999290418, 9492019319771, 27981390048004, 82535070088048, 243584292592314, 719260380812855, 2124883496835514, 6280345231488444, 18570334115507917, 54932973378157191, 162560095822581505, 481230651092809948, 1425091849082705513, 4221580226185571495, 12509581940713427231, 37079985749414410412, 109940891030905937324, 326059018594608183707, 967264334079435168434, 2870127536217116887904, 8518432176933741699599, 25288104633952181626331, 75087384066681607888745] Proposition Number , 4, : Let a(n) be the number of n-lettered words in the alphabet, {1, 2, 3} With as many occurrences of the substring (consecutive subword), [1, 2] as those of, [1, 3] 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 -1 - (3 t - 1) (4 t - 3 t + 1) P = 0 Not only that, a(n) safisfies the following linear recurrence 3 (5 + 2 n) a(n + 2) 13 (n + 2) a(n + 1) 6 (3 + 2 n) a(n) a(n + 3) = -------------------- - ------------------- + ---------------- n + 3 n + 3 n + 3 subject to the initial conditions a[1] = 3, a[2] = 7, a[3] = 15 Finally, the asymptotics of a(n) to order, 4, is : n 1/2 / 1 167 8155 253701 \ 0.84628437532163 3 (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.84628437532163 that is a mere non-rigorous estimate Maple conjectures that its exact value 3 is equal to, ------- 1/2 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 -1-(3*t-1)*(4*t^2-3*t+1)*P^2, [-6*(3+2*n)/(n+3)+13*(n+2)/(n+3)*N-3*(5+2*n)/(n+3 )*N^2+N^3, [3, 7, 15]], .84628437532163*3^n*(1/n)^(1/2)*(1-1/16/n-167/512/n^2-\ 8155/8192/n^3-253701/524288/n^4) For the sake of Sloane, here are the first 50 terms of the sequece [1, 3, 7, 15, 33, 81, 223, 651, 1915, 5559, 15921, 45333, 129309, 371025, 1071411, 3108951, 9047853, 26374005, 76959295, 224790195, 657326803, 1924486719, 5641225341, 16554458025, 48627650779, 142963972275, 420635073625, 1238489452437, 3648942571185, 10757537699373, 31733207206191, 93660093102483, 276579184070151, 817136196575355, 2415274760456469, 7142071672125225, 21127934320477125, 62525273556333537, 185102040379378875, 548170682949293823, 1623909844241591013, 4812187906265839389, 14264328418875780855, 42294331451732282235, 125438108066957778495, 372124371069778200579, 1104213762567482327217, 3277329209811896859693, 9729366977595732062625, 28889677718799986046717, 85800662357312770086483] Proposition Number , 5, : Let a(n) be the number of n-lettered words in the alphabet, {1, 2, 3} 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 quadratic equation 2 -2 - 3 t - 2 (t + 1) (3 t - 1) P - t (t + 1) (3 t - 1) P = 0 Not only that, a(n) safisfies the following linear recurrence (5 + 2 n) a(n + 1) 3 (n + 2) a(n) a(n + 2) = ------------------ + -------------- n + 3 n + 3 subject to the initial conditions a[1] = 3, a[2] = 7 Finally, the asymptotics of a(n) to order, 4, is : n 1/2 / 11 337 5345 339339 \ 1.465807535708760 3 (1/n) |1 - ---- + ------ - ------- + ---------| | 16 n 2 3 4| \ 512 n 8192 n 524288 n / Note that everything is rigorous except the constant in front, 1.465807535708760 that is a mere non-rigorous estimate Maple conjectures that its exact value 1/2 3 3 is equal to, ------- 1/2 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 -2-3*t-2*(t+1)*(3*t-1)*P-t*(t+1)*(3*t-1)*P^2, [-3*(n+2)/(n+3)-(5+2*n)/(n+3)*N+N ^2, [3, 7]], 1.465807535708760*3^n*(1/n)^(1/2)*(1-11/16/n+337/512/n^2-5345/8192 /n^3+339339/524288/n^4) For the sake of Sloane, here are the first 50 terms of the sequece [1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819, 18252025766941, 53876592856681, 159114492071763, 470139239360787, 1389754816243449, 4109922421017093, 12159131877715993, 35986168879543609, 106542797484006471, 315544068167601787, 934837217271732457, 2770417140954208377, 8212609533895771131, 24352194654450483759, 72228808291130603703, 214285636273290835239, 635888739568958641449, 1887427033736750828037, 5603455843421135356413, 16639279789182494873661, 49419934162239477797703, 146809908211050225267003] Proposition Number , 6, : Let a(n) be the number of n-lettered words in the alphabet, {1, 2, 3} With as many occurrences of the substring (consecutive subword), [1, 2] as those of, [2, 3] 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 -1 + (3 t - 1) (2 t - 1) (2 t - t + 1) P = 0 Not only that, a(n) safisfies the following linear recurrence 3 (2 n + 7) a(n + 3) 13 (n + 3) a(n + 2) 8 (5 + 2 n) a(n + 1) a(n + 4) = -------------------- - ------------------- + -------------------- n + 4 n + 4 n + 4 12 (n + 2) a(n) - --------------- n + 4 subject to the initial conditions a[1] = 3, a[2] = 7, a[3] = 17, a[4] = 45 Finally, the asymptotics of a(n) to order, 4, is : n 1/2 / 11 2401 411665 409053099 \ 1.036482448414 3 (1/n) |1 + ---- + ------- + -------- + ----------| | 32 n 2 3 4| \ 2048 n 65536 n 8388608 n / Note that everything is rigorous except the constant in front, 1.036482448414 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+(3*t-1)*(2*t-1)*(2*t^2-t+1)*P^2, [12*(n+2)/(n+4)-8*(5+2*n)/(n+4)*N+13*(n+3)/ (n+4)*N^2-3*(2*n+7)/(n+4)*N^3+N^4, [3, 7, 17, 45]], 1.036482448414*3^n*(1/n)^(1 /2)*(1+11/32/n+2401/2048/n^2+411665/65536/n^3+409053099/8388608/n^4) For the sake of Sloane, here are the first 50 terms of the sequece [1, 3, 7, 17, 45, 123, 337, 927, 2575, 7225, 20427, 58085, 165967, 476241, 1371615, 3962817, 11480157, 33335691, 96998137, 282751095, 825549445, 2413818011, 7066833237, 20713316043, 60775993945, 178497281223, 524702227369, 1543636437591, 4544652411561, 13389233104135, 39471952247297, 116434090600575, 343647414203247, 1014779796899801, 2998073409794235, 8861589706651637, 26204041915394087, 77517821049285081, 229404375011527207, 679140675610232825, 2011256416043019795, 5958228842374451661, 17656389756909683907, 52337755533205799613, 155185334072344216995, 460259760454802477805, 1365421789561607080875, 4051699526647913872725, 12025679355061511729535, 35700943731937029401985, 106009168422048204946527] It took, 29.460, seconds to generate this book.