(* This Mathematica notebook computes the asymptotic number of pi ' shapes which are of length n *)

Clear["*"]

eqn = {U == z + 1, S == U * S * T * z^2 + U, T == U^2 * T^2 * S * z^4 + 2 * z^3 * T + z^4 * T + 1}

{U == 1 + z, S == U + S T U z^2, T == 1 + 2 T z^3 + T z^4 + S T^2 U^2 z^4}

sol = Simplify[Solve[eqn, S, {U, T}]]

Singularity occurs either where denominator is zero (0 or 1, but we know analytic at z=0 as it is a generating function.) or where square root is zero.  Let's find where square root is zero.

poly = 1 - 2 z^2 - 6 z^3 - 5 z^4 - 6 z^5 - z^6 + 2 z^7 + z^8

1 - 2 z^2 - 6 z^3 - 5 z^4 - 6 z^5 - z^6 + 2 z^7 + z^8

roots = NSolve[poly == 0, z]

r = z/.Part[roots, 7, 1]

0.415644

This is our (unique) dominant singularity.  (It is smaller in magnitude than the singularity z=-1 caused by the denominator.)

The next few commands are to simply divide poly by (1-z/r) to get poly2 and then check that this worked.

poly2a = poly/(1 - z/r)

(1 - 2 z^2 - 6 z^3 - 5 z^4 - 6 z^5 - z^6 + 2 z^7 + z^8)/(1 - 2.40591 z)

Series[poly2a, {z, 0, 10}]

1 + 2.40591 z + 3.78838 z^2 + 3.11449 z^3 + 2.49316 z^4 - 0.0016824 z^5 - 1.00405 z^6 - 0.415644 z^7 + O[z]^11

poly2 = 1 + 2.40591 z + 3.78838 z^2 + 3.11449 z^3 + 2.49316 z^4 - 0.0016824 z^5 - 1.00405 z^6 - 0.415644 z^7

1 + 2.40591 z + 3.78838 z^2 + 3.11449 z^3 + 2.49316 z^4 - 0.0016824 z^5 - 1.00405 z^6 - 0.415644 z^7

Expand[poly2 * (1 - z/r)]

1 + 0. z - 2. z^2 - 6. z^3 - 5. z^4 - 6. z^5 - 1. z^6 + 2. z^7 + 1. z^8

poly

1 - 2 z^2 - 6 z^3 - 5 z^4 - 6 z^5 - z^6 + 2 z^7 + z^8

So this last expansion is close to poly, so this poly2 is what we want.

left = -1/(2 z^2 (1 + z)) * Sqrt[poly2]

-1/(2 z^2 (1 + z)) (√ (1 + 2.40591 z + 3.78838 z^2 + 3.11449 z^3 + 2.49316 z^4 - 0.0016824 z^5 - 1.00405 z^6 - 0.415644 z^7))

This is the portion next to the singularity, (1-z/r)^(1/2).

K = left/.z→r

-3.50931

K2 = K/Gamma[-1/2]

0.989959

1/r

2.40591

So V_n ~ 0.98996*(2.40591)^n*n^(-3/2), and we are done

oursol = V/.Part[sol2, 2, 1]

1/(2 z^2 (-1 + z^2)) (-1 - 2 z^2 - 2 z^3 - z^4 + z^5 + z^6 + √ (1 - 4 z^3 - 2 z^4 - 2 z^5 + 2 z^6 - 7 z^8 - 6 z^9 - z^10 + 2 z^11 + z^12))

Series[oursol, {z, 0, 20}]

By the way, above can be checked with recursion program to make sure no bugs, provided that the grammar is correct.  Also, the Series command can help check your asymptotics, if you expand out further.

Created by Mathematica  (December 22, 2006) Valid XHTML 1.1!