In how many ways can I carry a total of n coins in my two pockets, and have the same amount in both pockets?

Shalosh B. EKHAD and Doron ZEILBERGER

In fond memory of Gert Almkvist^{∗} (April 17, 1934- Nov. 24, 2018).

Theorem 1: Let a(n) be the number of ways of having a total of n coins in your two pockets (each of them either a penny, a nickel, a dime, or a quarter), so that the amounts in the pockets are identical, then

∑_{n=0}^{∞} a(n)t^{n} = \frac{P (t)}{Q(t)} , where

P (t) = t^{54} + t^{53} + 3 t^{52} + 4 t^{51} + 9 t^{50} + 15 t^{49} + 25 t^{48} + 37 t^{47} + 54 t^{46} + 76 t^{45} + 101 t^{44} + 128 t^{43}

+158 t^{42} + 190 t^{41} + 226 t^{40} + 256 t^{39} + 290 t^{38} + 318 t^{37} + 353 t^{36} + 372 t^{35} + 394 t^{34} + 405 t^{33} + 425 t^{32}

+431 t^{31} + 439 t^{30} + 438 t^{29} + 448 t^{28} + 448 t^{27} + 448 t^{26} + 438 t^{25} + 439 t^{24} + 431 t^{23} + 425 t^{22} + 405 t^{21}

+394 t^{20} + 372 t^{19} + 353 t^{18} + 318 t^{17} + 290 t^{16} + 256 t^{15} + 226 t^{14} + 190 t^{13} + 158 t^{12} + 128 t^{11} + 101 t^{10}

+76 t^{9} + 54 t^{8} + 37 t^{7} + 25 t^{6} + 15 t^{5} + 9 t^{4} + 4 t^{3} + 3 t^{2} + t + 1 ,

and

Q(t) = (1 − t)^{7} (1 + t)^{5} (t^{2} + t + 1)^{3} (t^{2} − t + 1)^{2} (t^{12} + t^{11} + t^{10} + t^{9} + t^{8} + t^{7} + t^{6} + t^{5} + t^{4} + t^{3} + t^{2} + t + 1) ·

(t^{12} − t^{11} + t^{10} − t^{9} + t^{8} − t^{7} + t^{6} − t^{5} + t^{4} − t^{3} + t^{2} − t + 1) (t^{10} + t^{9} + t^{8} + t^{7} + t^{6} + t^{5} + t^{4} + t^{3} + t^{2} + t + 1) ·

(t^{6} + t^{5} + t^{4} + t^{3} + t^{2} + t + 1) .

Furthermore a(n) is a quasi-polynomial, and asymptotically,

a(n) = \frac{5821}{311351040} n^{6} + O(n^{5}) .

∗ Gert Almkvist was one of the most creative and original mathematicians that we have ever met. He was known,

among his friends, as “the guy who generalized a mistake of Bourbaki” [see http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gert.html], a master expositor (1989 Lester Ford award, joint with Bruce Berndt, and numerous articles in Swedish), the co-inventor of the Almkvist-Zeilberger algorithm, and a great authority on Calabi-Yao differential equations. In addition to his official affiliation with the University of Lund, he was the founder of the Institute of Algebraic Meditation, and many of his papers used it as his affiliation.

Finally

a(10^{100}) =

1869593883482772371661260550149439038327927216816105704994593883482772371661260 5501494390383279272213031310253532475754697976920199142421364643586865809088031 3102535324757546979769201991424213646436436428797539908651019762130873241984353 0954642065753176864287975399086510197621308732419843530954646363924141701919479 6972574750352528130305908083685861463639241417019194796972574750352528130305908 1017544132821910599688377466155243933021710799488577266355044132821910599688377 4661552439330217107995247753069975292197514419736641958864181086403308625530847 7530699752921975144197366419588641810864035 .

The first 31 terms are:

1, 0, 4, 2, 12, 12, 34, 40, 85, 108, 190, 250, 394, 516, 762, 984, 1385, 1764, 2396,
2998, 3966, 4886, 6316, 7684, 9739, 11706, 14594, 17358, 21320, 25134, 30470 .

As of Jan. 23, 2019, this sequence is not in the OEIS [Sl].

For analogous theorems where one can also have a half-dollar coin, and a half-dollar coin as well as a dollar coin, see the output files

http://sites.math.rutgers.edu/~zeilberg/tokhniot/oEvenChange1b.txt, and
http://sites.math.rutgers.edu/~zeilberg/tokhniot/oEvenChange1c.txt .

How did we get this amazing theorem?

let A(n, m) be the number of ways of having n coins in your two pockets (with denominations 1, 5, 10, 25) in such a way that the difference between the amount in the left pocket and the amount in the right pocket is m cents. Then, if we define

R(z, t) := ∑_{n=0}^{∞} ∑_{m=−∞}^{∞} A(n, m) t^{n}z^{m} ,

then we have

R(z, t) = \frac{1}{(1 − tz)(1 − tz^{5})(1 − tz^{10})(1 − tz^{25})} · \frac{1}{(1 − t/z)(1 − t/z^{5})(1 − t/z^{10})(1 − t/z^{25})} .

This should be viewed as a formal power series in t whose coefficients are Laurent polynomials in z, and we are interested in extracting the coefficient of z^{0}. Now you ask Maple to kindly convert the above rational function into partial fractions, with respect to the variable z, getting something of the form

\frac{P_{1}(z, t)}{1 − tz} + \frac{P_{2}(z, t)}{1 − tz^{5}} + \frac{P_{3}(z, t)}{1 − tz^{10}} + \frac{P_{4}(z, t)}{1 − tz^{25}} + \frac{Q_{1}(z, t)}{z − t} + \frac{Q_{2}(z, t)}{z^{5} − t} + \frac{Q_{3}(z, t)}{z^{10} − t} + \frac{Q_{4}(z, t)}{z^{25} − t} ,

for some explicit expressions in z, t, P_{1}(z, t) … P_{4}(z, t), Q_{1}(z, t) … Q_{4}(z, t), that Maple finds for you. These are rational functions in t but polynomials in z.

When we view them all as a formal power series in t, and take the coefficient of z^{0}, the Q’s do not contribute anything, so the constant term, in z, is simply

P_{1}(0, t) + P_{2}(0, t) + P_{3}(0, t) + P_{4}(0, t) .

This is implemented in the Maple package EvenChange.txt by procedure GfPAB(P,z,t,A,B) that finds the coefficient of z^{0} of

\frac{P (z)}{∏_{a∈A}(1 − z^{a} t) ∏_{b∈B}(1 − t/z^{b})} ,

for any polynomial P of z and any sets of positive integers A and B (so you can have different kinds of coins in each pocket, and also talk about the number of ways of doing it where the difference between the amounts is not necessarily 0).

The Maple package EvenChange.txt is available from the front of this article

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/change.html .

Since all the generating functions have denominators whose roots are roots of unity, the sequence of interest itself, a(n), is a quasi-polynomial, albeit of a very large period. It is more efficient (still using partial fractions, this time with respect to t) to express it as a sum of quasi-polynomials of small periods. This is done via the procedure GFtoQPS that is lifted from the Maple package

http://sites.math.rutgers.edu/~zeilberg/tokhniot/PARTITIONS ,

that accompanies [SiZ].

This is how we found so quickly a(10^{100}) and the leading asymptotics of a(n) in Theorem 1.

Computing the generating functions ψ_{n}(t) dear to Gert Almkvist, Cayley, and Sylvester

In his 1980 paper [A], Gert Almkvist was interested in the sequence of rational functions {ψ_{n}(t)} that he defined as the constant term, in the variable z, of the rational function

\frac{(1 + z)^{2}}{2 z ∏_{i=0}^{n}(1 − t z^{n−2i})} .

Using procedure GfPAB again, we got the following theorem. According to Almkvist [A], the cases n = 2, 3, 4 are due to Faa de Bruno and n ≤ 12, except for n = 11 are due to Sylvester and Franklin.

Theorem 2:

• n = 2:

ψ_{2}(t) = \frac{1}{(1 − t)^{2} (t + 1)} ,

and its n-th coefficient, a_{2}(n), is asymptotically

a_{2}(n) = \frac{1}{2}n + O(1) .

The first 31 terms (starting with n = 0) are:

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16 .

This is A4536 [http://oeis.org/A004526] in [Sl].

• n = 3:

ψ_{3}(t) = \frac{t^{2} − t + 1}{(1 − t)^{3} (t + 1) (t^{2} + 1)} ,

and its n-th coefficient, a_{3}(n), is asymptotically

a_{3}(n) = \frac{1}{8}n^{2} + O(n) .

The first 31 terms (starting with n = 0) are: 1, 1, 2, 3, 5, 6, 8, 10, 13, 15, 18, 21, 25, 28, 32, 36, 41, 45, 50, 55, 61, 66, 72, 78, 85, 91, 98, 105, 113, 120, 128 . This is A1971 [http://oeis.org/A001971] in [Sl], that references [A].

• n = 4:

ψ_{4}(t) = \frac{t^{2} − t + 1}{(t + 1) (t^{2} + t + 1) (−1 + t)^{4}}

and its n-th coefficient, a_{4}(n), is asymptotically

a_{4}(n) = \frac{1}{36} n^{3} + O(n^{2}) .

The first 31 terms (starting with n = 0) are: 1, 1, 3, 5, 8, 12, 18, 24, 33, 43, 55, 69, 86, 104, 126, 150, 177, 207, 241, 277, 318, 362, 410, 462, 519, 579, 645,

715, 790, 870, 956 .

This is A1973 [http://oeis.org/A001973] in [Sl].

• n = 5:

ψ_{5}(t) = \frac{t^{14} − t^{13} + 2 t^{12} + t^{11} + 2 t^{10} + 3 t^{9} + t^{8} + 5 t^{7} + t^{6} + 3 t^{5} + 2 t^{4} + t^{3} + 2 t^{2} − t + 1}{(1 − t)^{5} (t + 1)^{3} (t^{2} + 1)^{2} (t^{2} + t + 1) (t^{2} − t + 1) (t^{4} + 1)} ,

and its n-th coefficient, a_{5}(n), is asymptotically

a_{5}(n) = \frac{23}{4608} n^{4} + O(n^{3}) = \frac{23}{2^{9} 3^{2}} n^{4} + O(n^{3}) .

The first 31 terms (starting with n = 0) are:

1, 1, 3, 6, 12, 20, 32, 49, 73, 102, 141, 190, 252, 325, 414, 521, 649, 795, 967, 1165, 1394, 1651, 1944,

2275, 2649, 3061, 3523, 4035, 4604, 5225, 5910 .

This is A1975 [http://oeis.org/A001975] in [Sl].

• n = 6:

ψ_{6}(t) = \frac{t^{10} + t^{8} + 3 t^{7} + 4 t^{6} + 4 t^{5} + 4 t^{4} + 3 t^{3} + t^{2} + 1}{(1 − t)^{6} (t^{2} + 1) (t^{4} + t^{3} + t^{2} + t + 1) (t + 1)^{3} (t^{2} + t + 1)} ,

and its n-th coefficient, a_{6}(n), is asymptotically

a_{6}(n) = \frac{11}{14400} n^{5} + O(n^{4}) = \frac{11}{2^{6} 3^{2} 5^{2}} n^{5} + O(n^{4}) .

The first 31 terms (starting with n = 0) are: 1, 1, 4, 8, 18, 32, 58, 94, 151, 227, 338, 480, 676, 920, 1242, 1636, 2137, 2739, 3486, 4370, 5444, 6698, 8196, 9926,

11963, 14293, 17002, 20076, 23612, 27594, 32134 .

This is A1977 [http://oeis.org/A001977] in [Sl].

• n = 7:

ψ_{7}(t) = \frac{P_{7}(t)}{Q_{7}(t)} ,

where P_{7}(t) = t^{34} − t^{33} + 3 t^{32} + 3 t^{31} + 7 t^{30} + 12 t^{29} + 16 t^{28} + 28 t^{27} + 33 t^{26} + 46 t^{25} + 56 t^{24} + 73 t^{23} +83 t^{22} + 90 t^{21} + 106 t^{20} + 109 t^{19} + 121 t^{18} + 110 t^{17} + 121 t^{16} + 109 t^{15} + 106 t^{14} + 90 t^{13} + 83 t^{12}

+73 t^{11} + 56 t^{10} + 46 t^{9} + 33 t^{8} + 28 t^{7} + 16 t^{6} + 12 t^{5} + 7 t^{4} + 3 t^{3} + 3 t^{2} − t + 1 , and

Q_{7}(t) = (1 − t)^{7} (t + 1)^{5} (t^{2} + 1)^{3} (t^{2} + t + 1)^{2} (t^{2} − t + 1)^{2} ·
(t^{4} + 1) (t^{4} + t^{3} + t^{2} + t + 1) (t^{4} − t^{3} + t^{2} − t + 1) (t^{4} − t^{2} + 1) ,

and its n-th coefficient, a_{7}(n), is, asymptotically

a_{7}(n) = \frac{841}{829440} n^{6} + O(n^{5}) = \frac{29^{2}}{2^{12}3^{4}5^{2}} n^{6} + O(n^{5}) .

The first 31 terms (starting with n = 0) are:

1, 1, 4, 10, 24, 49, 94, 169, 289, 468, 734, 1117, 1656, 2385, 3370, 4672, 6375, 8550,

11322, 14800, 19138, 24460, 30982, 38882, 48417, 59779, 73316, 89291, 108108, 130053, 15564 .

This is A1979 [http://oeis.org/A001979] in [Sl].

For the cases 8 ≤ n ≤ 18, see the output file

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

The case n = 8 is A1981 [http://oeis.org/A001981] in [Sl]. As of Jan. 23, 2019, the cases n = 9 and n = 10 are not in the OEIS, and probably (we were too lazy to check) neither are the higher ones.

References

[A] Gert Almkvist, Invariants, mostly old ones, Pacific J. Math. 86(1980), 1-13.

https://projecteuclid.org/euclid.pjm/1102780612 .

[SiZ] Andrew V. Sills and Doron Zeilberger, Formulae for the Number of Partitions of n into at most m parts(Using the Quasi-Polynomial Ansatz), Advances in Applied Mathematics 48 (2012), 640-645.

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pmn.html .

[Sl] Neil A. J. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org/ .

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 .

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 .

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org .

First Written: Jan. 23, 2019. This version: Jan. 25, 2019 (correcting a cut-and-paste error spotted by Sarah Selkirk).