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

%I M1068 #83 Apr 14 2022 07:23:44

%S 1,1,2,4,7,13,23,41,72,127,222,388,677,1179,2052,3569,6203,10778,

%T 18722,32513,56455,98017,170161,295389,512755,890043,1544907,2681554,

%U 4654417,8078679,14022089,24337897,42242732,73319574,127258596,220878683

%N Expansion of the reciprocal of the g.f. defining A039924.

%C 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 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 Former definition was "Expansion of reciprocal of a determinant." - _N. J. A. Sloane_, Aug 10 2018

%C From _Doron Zeilberger_, Aug 10 2018: (Start)

%C 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 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 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 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 H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 Roland Bacher, <a href="https://hal.archives-ouvertes.fr/hal-03221466">Generic numerical semigroups</a>, hal-03221466 [math.CO], 2021.

%H 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 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 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 Herman P. Robinson, <a href="/A003116/a003116.pdf">Letter to N. J. A. Sloane, Nov 13 1973</a>.

%H Herman P. Robinson, <a href="/A003116/a003116_1.pdf">Letter to N. J. A. Sloane, Nov 19 1973</a>.

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

%F a(n) ~ c * d^n, where d = 1/A347901 = 1.73566282453034742565826074971966853... and c = 0.9180565304926754125870866477349969555868577236908640010903420353... - _Vaclav Kotesovec_, Nov 01 2021

%e From _Joerg Arndt_, Dec 29 2012: (Start)

%e There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)-p(k-1) <= 1:

%e [ 1] [ 1 1 1 1 1 1 ]

%e [ 2] [ 1 1 1 1 2 ]

%e [ 3] [ 1 1 1 2 1 ]

%e [ 4] [ 1 1 2 1 1 ]

%e [ 5] [ 1 1 2 2 ]

%e [ 6] [ 1 2 1 1 1 ]

%e [ 7] [ 1 2 1 2 ]

%e [ 8] [ 1 2 2 1 ]

%e [ 9] [ 1 2 3 ]

%e [10] [ 2 1 1 1 1 ]

%e [11] [ 2 1 1 2 ]

%e [12] [ 2 1 2 1 ]

%e [13] [ 2 2 1 1 ]

%e [14] [ 2 2 2 ]

%e [15] [ 2 3 1 ]

%e [16] [ 3 1 1 1 ]

%e [17] [ 3 1 2 ]

%e [18] [ 3 2 1 ]

%e [19] [ 3 3 ]

%e [20] [ 4 1 1 ]

%e [21] [ 4 2 ]

%e [22] [ 5 1 ]

%e [23] [ 6 ]

%e Replacing the condition with p(k)-p(k-1) <= 0 gives integer partitions.

%e (End)

%t 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 b[n_, k_] := b[n, k] = Expand[If[n == 0, 1, x*

%t Sum[b[n - j, j], {j, 1, Min[n, k + 1]}]]];

%t a[n_] := Total@CoefficientList[b[n, n], x];

%t Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Apr 14 2022, after _Alois P. Heinz_ in A168443 *)

%o (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 (Haskell)

%o a003116 n = a168396 (2 * n + 1) n -- _Reinhard Zumkeller_, Sep 13 2013

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

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_, _Herman P. Robinson_

%E Definition revised by _N. J. A. Sloane_, Aug 10 2018 at the suggestion of _Doron Zeilberger_