A003116 Expansion of the reciprocal of the g.f. defining A039924.

1, 1, 2, 4, 7, 13, 23, 41, 72, 127, 222, 388, 677, 1179, 2052, 3569, 6203, 10778, 18722, 32513, 56455, 98017, 170161, 295389, 512755, 890043, 1544907, 2681554, 4654417, 8078679, 14022089, 24337897, 42242732, 73319574, 127258596, 220878683

Offset: 0

Author

N. J. A. Sloane, Herman P. Robinson

Keywords

• nonn
• nice
• easy

Comments

Conjecture: a(n) is the number of compositions p(1) + p(2) + ... + p(m) = n with p(i)-p(i-1) <= 1, see example; cf. A034297. - Vladeta Jovovic, Feb 09 2004

Row sums and central terms of the triangle in A168396: a(n) = A168396(2*n+1,n) and for n > 0: a(n) = Sum_{k=1..n} A168396(n,k). - Reinhard Zumkeller, Sep 13 2013

Former definition was "Expansion of reciprocal of a determinant." - N. J. A. Sloane, Aug 10 2018

From Doron Zeilberger, Aug 10 2018: (Start)

Jovovic's conjecture can be proved as follows. There is a sign-changing involution defined on pairs (L1,L2) where L1 is a partition with difference >= 2 between consecutive parts and L2 is the number of compositions described by Jovovic, with the sign (-1)^(Number of parts of L1).

Let a be the largest part of L1 and b the largest part of L2. If b-a>=2 then move b from L2 to the top of L1, otherwise move a to the top of L2.

Since this is an involution and it changes the sign (the number of parts of L1 changes parity) this proves it, since the g.f. of A039924 is exactly the signed-enumeration of the set given by L1. (End)

Examples

			From _Joerg Arndt_, Dec 29 2012: (Start)
There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)-p(k-1) <= 1:
[ 1]  [ 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 2 ]
[ 3]  [ 1 1 1 2 1 ]
[ 4]  [ 1 1 2 1 1 ]
[ 5]  [ 1 1 2 2 ]
[ 6]  [ 1 2 1 1 1 ]
[ 7]  [ 1 2 1 2 ]
[ 8]  [ 1 2 2 1 ]
[ 9]  [ 1 2 3 ]
[10]  [ 2 1 1 1 1 ]
[11]  [ 2 1 1 2 ]
[12]  [ 2 1 2 1 ]
[13]  [ 2 2 1 1 ]
[14]  [ 2 2 2 ]
[15]  [ 2 3 1 ]
[16]  [ 3 1 1 1 ]
[17]  [ 3 1 2 ]
[18]  [ 3 2 1 ]
[19]  [ 3 3 ]
[20]  [ 4 1 1 ]
[21]  [ 4 2 ]
[22]  [ 5 1 ]
[23]  [ 6 ]
Replacing the condition with p(k)-p(k-1) <= 0 gives integer partitions.
(End)
		

References

• D. H. Lehmer, Combinatorial and cyclotomic properties of certain tridiagonal matrices. Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), pp. 53-74. Congressus Numerantium, No. X, Utilitas Math., Winnipeg, Man., 1974. MR0441852.
• H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..4176 (first 401 terms from T. D. Noe)
• Roland Bacher, Generic numerical semigroups, hal-03221466 [math.CO], 2021.
• George Beck and Shane Chern, Reciprocity between partitions and compositions, arXiv:2108.04363 [math.CO], 2021.
• Shalosh B. Ekhad and Doron Zeilberger, D.H. Lehmer's Tridiagonal determinant: An Etude in (Andrews-Inspired) Experimental Mathematics, arXiv:1808.06730 [math.CO], 2018.
• Miguel Mendez, Shift-plethysm, Hydra continued fractions, and m-distinct partitions, arXiv:2009.04623 [math.CO], 2020.
• Herman P. Robinson, Letter to N. J. A. Sloane, Nov 13 1973.
• Herman P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.

Crossrefs

Cf. A003114, A039924, A034297, A168443, A224959.

Programs

Haskell

a003116 n = a168396 (2 * n + 1) n  -- Reinhard Zumkeller, Sep 13 2013

Mathematica

max = 35; f[x_] := 1/Sum[x^k^2*((-1)^k/Product[1 - x^i, {i, 1, k}]), {k, 0, Floor[Sqrt[max]]}]; CoefficientList[ Series[f[x], {x, 0, max}], x](* Jean-François Alcover, Jun 12 2012, after PARI *)
b[n_, k_] := b[n, k] = Expand[If[n == 0, 1, x*
     Sum[b[n - j, j], {j, 1, Min[n, k + 1]}]]];
a[n_] := Total@CoefficientList[b[n, n], x];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Apr 14 2022, after Alois P. Heinz in A168443 *)

PARI

a(n)=if(n<0,0,polcoeff(1/sum(k=0,sqrtint(n),x^k^2/prod(i=1,k,x^i-1,1+x*O(x^n))),n))

Formula

G.f.: 1/(Sum_{k>=0} x^(k^2)(-1)^k/(Product_{i=1..k} 1-x^i)).

a(n) ~ c * d^n, where d = 1/A347901 = 1.73566282453034742565826074971966853... and c = 0.9180565304926754125870866477349969555868577236908640010903420353... - Vaclav Kotesovec, Nov 01 2021

Extensions

Definition revised by N. J. A. Sloane, Aug 10 2018 at the suggestion of Doron Zeilberger