[go: up one dir, main page]

login
A003116
Expansion of the reciprocal of the g.f. defining A039924.
(Formerly M1068)
24
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,3
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)
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.
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
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(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)
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 *)
PROG
(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))
(Haskell)
a003116 n = a168396 (2 * n + 1) n -- Reinhard Zumkeller, Sep 13 2013
CROSSREFS
KEYWORD
nonn,nice,easy
EXTENSIONS
Definition revised by N. J. A. Sloane, Aug 10 2018 at the suggestion of Doron Zeilberger
STATUS
approved