login
Number of stacks, or planar partitions of n; also weakly unimodal compositions of n.
(Formerly M1102 N0420)
115

%I M1102 N0420 #123 Jul 17 2024 10:35:18

%S 1,1,2,4,8,15,27,47,79,130,209,330,512,784,1183,1765,2604,3804,5504,

%T 7898,11240,15880,22277,31048,43003,59220,81098,110484,149769,202070,

%U 271404,362974,483439,641368,847681,1116325,1464999,1916184,2498258,3247088,4207764

%N Number of stacks, or planar partitions of n; also weakly unimodal compositions of n.

%C a(n) counts stacks of integer-length boards of total length n where no board overhangs the board underneath.

%C Number of graphical partitions on 2n nodes that contain a 1. E.g. a(3)=4 and so there are 4 graphical partitions of 6 that contain a 1, namely (111111), (21111), (2211) and (3111). Only (222) fails. - _Jon Perry_, Jul 25 2003

%C It would seem from Stanley that he regards a(0)=0 for this sequence and A001522. - _Michael Somos_, Feb 22 2015

%C In the article by Auluck is a typo in the formula (24), 2*Pi is missing in an exponent on the left side of the equation for Q(n). The correct term is exp(2*Pi*sqrt(n/3)), not just exp(sqrt(n/3)). - _Vaclav Kotesovec_, Jun 22 2015

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see section 2.5 on page 76.

%H Alois P. Heinz, <a href="/A001523/b001523.txt">Table of n, a(n) for n = 0..10000</a> (first 1001 terms from T. D. Noe)

%H F. C. Auluck, <a href="http://dx.doi.org/10.1017/S0305004100027134">On some new types of partitions associated with generalized Ferrers graphs</a>, Proc. Cambridge Philos. Soc. 47, (1951), 679-686, g(x).

%H F. C. Auluck, <a href="/A001524/a001524.pdf">On some new types of partitions associated with generalized Ferrers graphs</a> (annotated scanned copy)

%H H. Bottomley, <a href="/A001523/a001523.gif">Illustration of initial terms</a>

%H Shouvik Datta, Matthias R. Gaberdiel, Wei Li, and Cheng Peng, <a href="https://arxiv.org/abs/1606.07070">Twisted sectors from plane partitions</a>, arXiv preprint arXiv:1606.07070 [hep-th], 2016. See Sect. 2.1.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 46.

%H Rigoberto Flórez, José L. Ramírez, and Diego Villamizar, <a href="https://doi.org/10.1016/j.jcta.2024.105934">Restricted bargraphs and unimodal compositions</a>, J. Comb. Theory, Series A, (2024) Vol. 208, Art. No. 105934.

%H R. C. Rhoades, <a href="http://math.stanford.edu/~rhoades/FILES/unimodal.pdf">Strongly Unimodal Sequences and Mixed Mock Modular Forms</a>

%H Alan D. Sokal, <a href="http://arxiv.org/abs/1106.1003">The leading root of the partial theta function</a>, arXiv preprint arXiv:1106.1003 [math.CO], 2011.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/UnimodalSequence.html">Unimodal Sequence</a>

%H E. M. Wright, <a href="https://doi.org/10.1093/qmath/23.2.153">Stacks, III</a>, Quart. J. Math. Oxford, 23 (1972), 153-158.

%F a(n) = Sum_{k=1..n} f(k, n-k), where f(n, k) (= A054250) = 1 if k = 0; Sum_{j=1..min(n, k)} (n-j+1) f(j, k-j)) if k > 0. - _David W. Wilson_, May 05 2000

%F a(n) = Sum_{k} A059623(n, k) for n > 0. - _Henry Bottomley_, Feb 01 2001

%F A006330(n) + a(n) = A000712(n). - _Michael Somos_, Jul 22 2003

%F G.f.: 1 + (Sum_{k>0} -(-1)^k x^(k(k+1)/2))/(Product_{k>0} (1-x^k))^2. - _Michael Somos_, Jul 22 2003

%F G.f.: 1 + Sum_{n>=1} (x^n / ( ( Product_{k=1..n-1} (1 - x^k)^2 ) * (1-x^n) ) ). - _Joerg Arndt_, Oct 01 2012

%F a(n) ~ exp(2*Pi*sqrt(n/3)) / (8 * 3^(3/4) * n^(5/4)) [Auluck, 1951]. - _Vaclav Kotesovec_, Jun 22 2015

%F a(n) + A115981(n) = 2^(n - 1). - _Gus Wiseman_, Mar 04 2020

%e For a(4)=8 we have the following stacks:

%e x

%e x x. .x

%e x x. .x x.. .x. ..x xx

%e x xx xx xxx xxx xxx xx xxxx

%e G.f. = 1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 27*x^6 + 47*x^7 + 79*x^8 + ...

%e From _Gus Wiseman_, Mar 04 2020: (Start)

%e The a(1) = 1 through a(5) = 15 unimodal compositions:

%e (1) (2) (3) (4) (5)

%e (11) (12) (13) (14)

%e (21) (22) (23)

%e (111) (31) (32)

%e (112) (41)

%e (121) (113)

%e (211) (122)

%e (1111) (131)

%e (221)

%e (311)

%e (1112)

%e (1121)

%e (1211)

%e (2111)

%e (11111)

%e (End)

%p b:= proc(n, i) option remember;

%p `if`(i>n, 0, `if`(irem(n, i)=0, 1, 0)+

%p add(b(n-i*j, i+1)*(j+1), j=0..n/i))

%p end:

%p a:= n-> `if`(n=0, 1, b(n, 1)):

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Mar 26 2014

%t max = 40; s = 1 + Sum[(-1)^(k + 1)*q^(k*(k + 1)/2), {k, 1, max}] / QPochhammer[q]^2 + O[q]^max; CoefficientList[s, q] (* _Jean-François Alcover_, Jan 25 2012, updated Nov 29 2015 *)

%t b[n_, i_] := b[n, i] = If[i>n, 0, If[Mod[n, i]==0, 1, 0] + Sum[b[n-i*j, i+1]*(j+1), {j, 0, n/i}]]; a[n_] := If[n==0, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Nov 24 2015, after _Alois P. Heinz_ *)

%t unimodQ[q_]:=Or[Length[q]<=1,If[q[[1]]<=q[[2]],unimodQ[Rest[q]],OrderedQ[Reverse[q]]]];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],unimodQ[#]&]],{n,0,10}] (* _Gus Wiseman_, Mar 04 2020 *)

%o (PARI) {a(n) = if( n<1, n==0, polcoeff( sum(k=1, (sqrt(1 + 8*n) - 1)\2, -(-1)^k * x^((k + k^2)/2)) / eta(x + x * O(x^n))^2 ,n))}; /* _Michael Somos_, Jul 22 2003 */

%o (Python)

%o def b(n, i):

%o if i>n: return 0

%o if n%i==0: x=1

%o else: x=0

%o return x + sum([b(n - i*j, i + 1)*(j + 1) for j in range(n//i + 1)])

%o def a(n): return 1 if n==0 else b(n, 1) # _Indranil Ghosh_, Jun 09 2017, after Maple code by _Alois P. Heinz_

%o (Magma)

%o m:=100;

%o R<x>:=PowerSeriesRing(Integers(), m);

%o Coefficients(R!( 1 + (&+[ x^n*(1-x^n)/(&*[(1-x^j)^2: j in [1..n]]): n in [1..m+2]]) )); // _G. C. Greubel_, Apr 03 2023

%Y Cf. A054250, A059618, A059623, A001522, A001524.

%Y Cf. A000569. Bisections give A100505, A100506.

%Y Row sums of A247255.

%Y Row sums of A072704.

%Y The strict case is A072706.

%Y The complement is counted by A115981.

%Y The case covering an initial interval is A227038.

%Y The version whose negation is unimodal as well appears to be A329398.

%Y Unimodal sequences covering an initial interval are A007052.

%Y Non-unimodal permutations are A059204.

%Y Non-unimodal sequences covering an initial interval are A328509.

%Y Partitions with unimodal run-lengths are A332280.

%Y Numbers whose prime signature is not unimodal are A332282.

%Y Partitions whose 0-appended first differences are unimodal are A332283.

%Y The number of unimodal permutations of the prime indices of n is A332288.

%Y Compositions whose negation is unimodal are A332578.

%Y Compositions whose run-lengths are unimodal are A332726.

%Y Cf. A107429, A156253, A332285, A332294, A332577, A332642, A332669.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, May 05 2000

%E Definition corrected by _Wolfdieter Lang_, Dec 05 2018