|
|
A001523
|
|
Number of stacks, or planar partitions of n; also weakly unimodal compositions of n.
(Formerly M1102 N0420)
|
|
114
|
|
|
1, 1, 2, 4, 8, 15, 27, 47, 79, 130, 209, 330, 512, 784, 1183, 1765, 2604, 3804, 5504, 7898, 11240, 15880, 22277, 31048, 43003, 59220, 81098, 110484, 149769, 202070, 271404, 362974, 483439, 641368, 847681, 1116325, 1464999, 1916184, 2498258, 3247088, 4207764
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) counts stacks of integer-length boards of total length n where no board overhangs the board underneath.
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
It would seem from Stanley that he regards a(0)=0 for this sequence and A001522. - Michael Somos, Feb 22 2015
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
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see section 2.5 on page 76.
|
|
LINKS
|
E. M. Wright, Stacks, III, Quart. J. Math. Oxford, 23 (1972), 153-158.
|
|
FORMULA
|
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
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
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
a(n) ~ exp(2*Pi*sqrt(n/3)) / (8 * 3^(3/4) * n^(5/4)) [Auluck, 1951]. - Vaclav Kotesovec, Jun 22 2015
|
|
EXAMPLE
|
For a(4)=8 we have the following stacks:
x
x x. .x
x x. .x x.. .x. ..x xx
x xx xx xxx xxx xxx xx xxxx
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 + ...
The a(1) = 1 through a(5) = 15 unimodal compositions:
(1) (2) (3) (4) (5)
(11) (12) (13) (14)
(21) (22) (23)
(111) (31) (32)
(112) (41)
(121) (113)
(211) (122)
(1111) (131)
(221)
(311)
(1112)
(1121)
(1211)
(2111)
(11111)
(End)
|
|
MAPLE
|
b:= proc(n, i) option remember;
`if`(i>n, 0, `if`(irem(n, i)=0, 1, 0)+
add(b(n-i*j, i+1)*(j+1), j=0..n/i))
end:
a:= n-> `if`(n=0, 1, b(n, 1)):
|
|
MATHEMATICA
|
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 *)
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 *)
unimodQ[q_]:=Or[Length[q]<=1, If[q[[1]]<=q[[2]], unimodQ[Rest[q]], OrderedQ[Reverse[q]]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], unimodQ[#]&]], {n, 0, 10}] (* Gus Wiseman, Mar 04 2020 *)
|
|
PROG
|
(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 */
(Python)
def b(n, i):
if i>n: return 0
if n%i==0: x=1
else: x=0
return x + sum([b(n - i*j, i + 1)*(j + 1) for j in range(n//i + 1)])
(Magma)
m:=100;
R<x>:=PowerSeriesRing(Integers(), m);
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
|
|
CROSSREFS
|
The complement is counted by A115981.
The case covering an initial interval is A227038.
The version whose negation is unimodal as well appears to be A329398.
Unimodal sequences covering an initial interval are A007052.
Non-unimodal permutations are A059204.
Non-unimodal sequences covering an initial interval are A328509.
Partitions with unimodal run-lengths are A332280.
Numbers whose prime signature is not unimodal are A332282.
Partitions whose 0-appended first differences are unimodal are A332283.
The number of unimodal permutations of the prime indices of n is A332288.
Compositions whose negation is unimodal are A332578.
Compositions whose run-lengths are unimodal are A332726.
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|