The O(1/n^{85}) Asymptotic expansion of OEIS sequence A85

Shalosh B. EKHAD, Manuel KAUERS, and Doron ZEILBERGER

In honor of our two heroes, Don Knuth who was 85, a year ago, and Neil Sloane, who is

now 85

On Oct. 10, 2024, exactly 85 years after his birth, guru Neil Sloane gave a great Zoom talk:

https://vimeo.com/1018688642?share=copy .

After the talk was over his many fans discussed the significance of the number 85, and someone mentioned that the OEIS sequence A85 (https://oeis.org/A000085) is a very important sequence, the number of involutions of length n, and also, thanks to the famous RSK (Robinson-Schenstead-KNUTH) correspondence, the number of Young tableaux with n boxes. And indeed this sequence was important enough that guru Don Knuth, in his bible, The Art of Computer Programming ([Kn], pp. 62-64) spent three pages deriving, by hand, using Laplace’s method, the asymptotic formula for the members of A85, first determined, using a different method by Moser and Wyman ([MW]). Namely, t_{n} := A85[n] (Eq. (53), p. 64, in [Kn]) is given by the following formula.

t_{n} = \frac{1}{\sqrt{2}}n^{n/2}e^{−n/2+\sqrt{n}−1/4} (1 + \frac{7}{24}n^{−1/2} + O(n^{−3/4})) .

Knuth remarked:

In principle, the method we have used could be extended to any O(n^{−k}), for any k, instead of O(n^{−3/4}).

In this modest tribute to our two heroes, we will do it in practice for the important number k = 85. Ideally one should be able to use the Maple package

http://sites.math.rutgers.edu/~zeilberg/tokhniot/AsyRec.txt written by the third author,

and executed by the first author, that, alas, for some mysterious reason, can only go as far as k = 22. Its extension, written in Sage by the second author, using the method in [KaJJ], and executed by his computer, can go as far as one wishes, but in honor of the two gurus we will stop at O(1/n^{85}).

We have (to order O(n^{−5}))

Theorem:

t_{n} = \frac{1}{\sqrt{2}}n^{n/2}e^{−n/2+\sqrt{n}−1/4} ·

(1 + \frac{7}{24\sqrt{n}} − \frac{119}{1152n} − \frac{7933}{414720n^{\frac{3}{2}}} + \frac{1967381}{39813120n^{2}} − \frac{57200419}{1337720832n^{\frac{5}{2}}} − \frac{562799}{47775744n^{3}} − \frac{526420847}{40131624960n^{\frac{7}{2}}}

+\frac{1856209}{573308928n^{4}} − \frac{267645803}{2407897497600n^{\frac{9}{2}}} + O(\frac{1}{n^{5}} )) .

To get the O(\frac{1}{n^{85}} ) asymptotics, that is too long to be typyset in humanese, see the output file:

http://sites.math.rutgers.edu/~zeilberg/tokhniot/A85asympt.txt .

Comments

1. Our method is different from both the one used by Moser and Wyman and the one used by Knuth (that he attributes to Laplace). We use the method exposited in [WZ], originally invented by George D. Birkhoff and W. J. Trjitzinsky, and implemented by us in Maple and Sage. We use the fact, mentioned in [Kn] (p. 62, Eq. (40) there), that t_{n} (i.e. A85[n]) satisfies the second-order recurrence

t_{n} = t_{n−1} + (n − 1)t_{n−2} .

2. The combinatorial proof given in [Kn] (p. 62), goes like this: A permutation is its own inverse if and only if its cycle form consists of one-cycles (fixed points) and two cycles (transpositions). Since t_{n−1} of the t_{n} involutions have (n) as a one-cycle, and since t_{n−2} of them have (jn) as a two-cyle, for fixed j < n, we obtain this formula. We have two additional proofs, for what there are worth. Eq, (41) of ([Kn], p.62) says:

t_{n} = ∑_{k=1}^{⌊n/2⌋} \frac{n!}{(n − 2k)!2^{k}k!} ,

(as explained in [Kn], suppose there are k two-cycles and n − 2k one-cycles. There are \binom{n}{2k} ways to choose the fixed points, and the multinomial coefficient (2k)!/(2!)^{k} is the number of ways to arrange the other elements into k distinguished transpositions; dividing by k! to make the transpositions indistinguishable.) Now download the Maple package:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/EKHAD.txt ,

and type

zeil(n!/((n-2*k)!*2**k*k!),k,n,N); ,

and you would get the above recurrence, followed by its proof certificate. Eq. (42) in [Kn], p. 62,

∑_{n} t_{n}z^{n}/n! = e^{z+z^{2}/2} ,

yields yet-another proof. In the above-mentioned Maple package, type

AZd(n!*exp(z+z**2/2)/z**(n+1),z,n,N); ,

and you would get the recurrence, followed by its proof certificate.

3. This article is accompanied by a Maple package A85.txt available from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/A85.txt ,

that lets you find the asymptotic expansion to order O(1/n^{(k+1)/2}) for any 1 ≤ k ≤ 169. Just type ‘AsyI(n,k);’ if n is numeric, and ‘AsyIs(n,k);’, if n is symbolic. Procedures SeqWn(N) outputs the list of first N terms of OEIS sequence A85. Just for fun, to get A85[1000], (the number of involutions of length 1000) type:

SeqWn(1000)[1000]; ,

getting, right away, the number in the following output file:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/A85w1000.txt .

This is a 1296-digit number, that in floating point to twenty digits is: 2.1439289538422655419 · 10^{1296} . The approximation from using O(1/n) asymptotics is gotten by typing

evalf(AsyI(1000,1),20);

yielding

2.1441496003431008422 · 10^{1296} .

The ratio to the exact value is:

1.0001029168902448312

On the other hand with evalf(AsyI(1000,30),20); (the O(1/n^{31/2})) formula), the ratio is: 0.9999999999999999999999999996 ….

Pas mal! . References

[Kn] Donald E. Knuth, “The Art of Computer Programming volume 3: Sorting and Searching”; Second Edition, Addison-Wesley, 1998.

[KaJJ] Manuel Kauers, Maximilian Jaroschek, Fredrik Johansson, Ore polynomials in Sage, in “Computer Algebra and Polynomials”, Springer LNCS 8942, pages 105-125, 2015.

[MW] Leo Moser and Max Wyman, On solutions of x^{d} = 1 in symmetric groups, Canadian Journal of Mathematics 7 (1955), 159-168.

[WZ] Jet Wimp and Doron Zeilberger, Resurrecting the Asymptotics of Linear Recurrences, J. of Math. Anal. Appl. 111 (1985), 162-176.

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Manuel Kauers, Institute for Algebra, J. Kepler University Linz, Austria

Email: manuel dot kauers at jku dot at

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Oct. 20, 2024.