cp's OEIS Frontend

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

%I A003116 M1068 #83 Apr 14 2022 07:23:44
%S A003116 1,1,2,4,7,13,23,41,72,127,222,388,677,1179,2052,3569,6203,10778,
%T A003116 18722,32513,56455,98017,170161,295389,512755,890043,1544907,2681554,
%U A003116 4654417,8078679,14022089,24337897,42242732,73319574,127258596,220878683
%N A003116 Expansion of the reciprocal of the g.f. defining A039924.
%C A003116 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
%C A003116 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
%C A003116 Former definition was "Expansion of reciprocal of a determinant." - _N. J. A. Sloane_, Aug 10 2018
%C A003116 From _Doron Zeilberger_, Aug 10 2018: (Start)
%C A003116 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).
%C A003116 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.
%C A003116 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)
%D A003116 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.
%D A003116 H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
%D A003116 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003116 Alois P. Heinz, <a href="/A003116/b003116.txt">Table of n, a(n) for n = 0..4176</a> (first 401 terms from T. D. Noe)
%H A003116 Roland Bacher, <a href="https://hal.archives-ouvertes.fr/hal-03221466">Generic numerical semigroups</a>, hal-03221466 [math.CO], 2021.
%H A003116 George Beck and Shane Chern, <a href="https://arxiv.org/abs/2108.04363">Reciprocity between partitions and compositions</a>, arXiv:2108.04363 [math.CO], 2021.
%H A003116 Shalosh B. Ekhad and Doron Zeilberger, <a href="https://arxiv.org/abs/1808.06730">D.H. Lehmer's Tridiagonal determinant: An Etude in (Andrews-Inspired) Experimental Mathematics</a>, arXiv:1808.06730 [math.CO], 2018.
%H A003116 Miguel Mendez, <a href="https://arxiv.org/abs/2009.04623">Shift-plethysm, Hydra continued fractions, and m-distinct partitions</a>, arXiv:2009.04623 [math.CO], 2020.
%H A003116 Herman P. Robinson, <a href="/A003116/a003116.pdf">Letter to N. J. A. Sloane, Nov 13 1973</a>.
%H A003116 Herman P. Robinson, <a href="/A003116/a003116_1.pdf">Letter to N. J. A. Sloane, Nov 19 1973</a>.
%F A003116 G.f.: 1/(Sum_{k>=0} x^(k^2)(-1)^k/(Product_{i=1..k} 1-x^i)).
%F A003116 a(n) ~ c * d^n, where d = 1/A347901 = 1.73566282453034742565826074971966853... and c = 0.9180565304926754125870866477349969555868577236908640010903420353... - _Vaclav Kotesovec_, Nov 01 2021
%e A003116 From _Joerg Arndt_, Dec 29 2012: (Start)
%e A003116 There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)-p(k-1) <= 1:
%e A003116 [ 1]  [ 1 1 1 1 1 1 ]
%e A003116 [ 2]  [ 1 1 1 1 2 ]
%e A003116 [ 3]  [ 1 1 1 2 1 ]
%e A003116 [ 4]  [ 1 1 2 1 1 ]
%e A003116 [ 5]  [ 1 1 2 2 ]
%e A003116 [ 6]  [ 1 2 1 1 1 ]
%e A003116 [ 7]  [ 1 2 1 2 ]
%e A003116 [ 8]  [ 1 2 2 1 ]
%e A003116 [ 9]  [ 1 2 3 ]
%e A003116 [10]  [ 2 1 1 1 1 ]
%e A003116 [11]  [ 2 1 1 2 ]
%e A003116 [12]  [ 2 1 2 1 ]
%e A003116 [13]  [ 2 2 1 1 ]
%e A003116 [14]  [ 2 2 2 ]
%e A003116 [15]  [ 2 3 1 ]
%e A003116 [16]  [ 3 1 1 1 ]
%e A003116 [17]  [ 3 1 2 ]
%e A003116 [18]  [ 3 2 1 ]
%e A003116 [19]  [ 3 3 ]
%e A003116 [20]  [ 4 1 1 ]
%e A003116 [21]  [ 4 2 ]
%e A003116 [22]  [ 5 1 ]
%e A003116 [23]  [ 6 ]
%e A003116 Replacing the condition with p(k)-p(k-1) <= 0 gives integer partitions.
%e A003116 (End)
%t A003116 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 *)
%t A003116 b[n_, k_] := b[n, k] = Expand[If[n == 0, 1, x*
%t A003116      Sum[b[n - j, j], {j, 1, Min[n, k + 1]}]]];
%t A003116 a[n_] := Total@CoefficientList[b[n, n], x];
%t A003116 Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Apr 14 2022, after _Alois P. Heinz_ in A168443 *)
%o A003116 (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))
%o A003116 (Haskell)
%o A003116 a003116 n = a168396 (2 * n + 1) n  -- _Reinhard Zumkeller_, Sep 13 2013
%Y A003116 Cf. A003114, A039924, A034297, A168443, A224959.
%K A003116 nonn,nice,easy
%O A003116 0,3
%A A003116 _N. J. A. Sloane_, _Herman P. Robinson_
%E A003116 Definition revised by _N. J. A. Sloane_, Aug 10 2018 at the suggestion of _Doron Zeilberger_