

A003116


Expansion of the reciprocal of the g.f. defining A039924.
(Formerly M1068)


23



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Conjecture: a(n) is the number of compositions p(1) + p(2) + ... + p(m) = n with p(i)p(i1) <= 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 signchanging 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 ba>=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 signedenumeration of the set given by L1. (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. 5374. 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)
Shalosh B. Ekhad and Doron Zeilberger, D.H. Lehmer's Tridiagonal determinant: An Etude in (AndrewsInspired) Experimental Mathematics, arXiv:1808.06730 [math.CO], 2018.
Miguel Mendez, Shiftplethysm, Hydra continued fractions, and mdistinct 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.


FORMULA

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


EXAMPLE

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(k1) <= 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(k1) <= 0 gives integer partitions.
(End)


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](* JeanFrançois Alcover, Jun 12 2012, after PARI *)


PROG

(PARI) a(n)=if(n<0, 0, polcoeff(1/sum(k=0, sqrtint(n), x^k^2/prod(i=1, k, x^i1, 1+x*O(x^n))), n))
(Haskell)
a003116 n = a168396 (2 * n + 1) n  Reinhard Zumkeller, Sep 13 2013


CROSSREFS

Cf. A003114, A039924, A034297, A224959.
Sequence in context: A319255 A136299 A208354 * A303666 A260917 A165648
Adjacent sequences: A003113 A003114 A003115 * A003117 A003118 A003119


KEYWORD

nonn,nice,easy


AUTHOR

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


EXTENSIONS

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


STATUS

approved



