login
Number of n-stacks with strictly receding walls, or the number of Type A partitions of n in the sense of Auluck (1951).
(Formerly M0644 N0238)
60

%I M0644 N0238 #132 Sep 26 2022 10:39:39

%S 1,1,1,1,2,3,5,7,10,14,19,26,35,47,62,82,107,139,179,230,293,372,470,

%T 591,740,924,1148,1422,1756,2161,2651,3244,3957,4815,5844,7075,8545,

%U 10299,12383,14859,17794,21267,25368,30207,35902,42600,50462,59678,70465,83079,97800,114967,134956,158205,185209,216546,252859

%N Number of n-stacks with strictly receding walls, or the number of Type A partitions of n in the sense of Auluck (1951).

%C Also number of partitions of n with positive crank (n>=2), cf. A064391. - _Vladeta Jovovic_, Sep 30 2001

%C Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1 (smooth means that successive parts differ by at most one), see example. Dropping the requirement for unimodality gives A186085. - _Joerg Arndt_, Dec 09 2012

%C Number of weakly unimodal compositions of n where the maximal part m appears at least m times, see example. - _Joerg Arndt_, Jun 11 2013

%C Also weakly unimodal compositions of n with first part 1, maximal up-step 1, and no consecutive up-steps; see example. The smooth weakly unimodal compositions are recovered by shifting all rows above the bottom row to the left by one position with respect to the next lower row. - _Joerg Arndt_, Mar 30 2014

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

%C From _Gus Wiseman_, Mar 30 2021: (Start)

%C Also the number of odd-length compositions of n with alternating parts strictly decreasing. These are finite odd-length sequences q of positive integers summing to n such that q(i) > q(i+2) for all possible i. The even-length version is A064428. For example, the a(1) = 1 through a(9) = 14 compositions are:

%C (1) (2) (3) (4) (5) (6) (7) (8) (9)

%C (211) (221) (231) (241) (251) (261)

%C (311) (312) (322) (332) (342)

%C (321) (331) (341) (351)

%C (411) (412) (413) (423)

%C (421) (422) (432)

%C (511) (431) (441)

%C (512) (513)

%C (521) (522)

%C (611) (531)

%C (612)

%C (621)

%C (711)

%C (32211)

%C (End)

%C In the Ferrers diagram of a partition x of n, count the dots in each diagonal parallel to the main diagonal (starting at the top-right, say). The result diag(x) is a smooth weakly unimodal composition of n into positive parts such that the first and last part are 1. For example, diag(5541) = 11233221. The function diag is many-to-one; the size of its codomain as a set is a(n). If diag(x) = diag(y), each hook of x can be slid by the same amount past the main diagonal to get y. For example, diag(5541) = diag(44331). - _George Beck_, Sep 26 2021

%C From _Gus Wiseman_, May 23 2022: (Start)

%C Conjecture: Also the number of integer partitions y of n with a fixed point y(i) = i. These partitions are ranked by A352827. The conjecture is stated at A238395, but Resta tells me he may not have had a proof. The a(1) = 1 through a(8) = 10 partitions are:

%C (1) (11) (111) (22) (32) (42) (52) (62)

%C (1111) (221) (222) (322) (422)

%C (11111) (321) (421) (521)

%C (2211) (2221) (2222)

%C (111111) (3211) (3221)

%C (22111) (4211)

%C (1111111) (22211)

%C (32111)

%C (221111)

%C (11111111)

%C Note that these are not the same partitions (compare A352827 to A352874), only the same count (apparently).

%C (End)

%C The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - _Jeremy Lovejoy_, Sep 26 2022

%D G. E. Andrews, The reasonable and unreasonable effectiveness of number theory in statistical mechanics, pp. 21-34 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.

%D G. E. Andrews, Three-quadrant Ferrers graphs, Indian J. Math., 42 (No. 1, 2000), 1-7.

%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 Seiichi Manyama, <a href="/A001522/b001522.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.

%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 A. Blecher and A. Knopfmacher, <a href="http://doi.org/10.1007/s11139-022-00551-x">Fixed points and matching points in partitions</a>, Ramanujan J. 58 (2022), 23-41.

%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 Erich Friedman, <a href="/A001522/a001522.gif">Illustration of initial terms</a>

%H A. 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 E. M. Wright, <a href="http://qjmath.oxfordjournals.org/content/23/2/153.extract">Stacks, III</a>, Quart. J. Math. Oxford, 23 (1972), 153-158.

%F a(n) = (A000041(n) - A064410(n)) / 2 for n>=2.

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

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

%F a(n) ~ exp(Pi*sqrt(2*n/3)) / (8*sqrt(3)*n) [Auluck, 1951]. - _Vaclav Kotesovec_, Sep 26 2016

%F a(n) = A000041(n) - A064428(n). - _Gus Wiseman_, Mar 30 2021

%F a(n) = A064428(n) - A064410(n). - _Gus Wiseman_, May 23 2022

%e For a(6)=5 we have the following stacks:

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

%e xxxxx xxxxx xxxxx xxxx xxxxxx

%e .

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

%e There are a(9) = 14 smooth weakly unimodal compositions of 9:

%e 01: [ 1 1 1 1 1 1 1 1 1 ]

%e 02: [ 1 1 1 1 1 1 2 1 ]

%e 03: [ 1 1 1 1 1 2 1 1 ]

%e 04: [ 1 1 1 1 2 1 1 1 ]

%e 05: [ 1 1 1 1 2 2 1 ]

%e 06: [ 1 1 1 2 1 1 1 1 ]

%e 07: [ 1 1 1 2 2 1 1 ]

%e 08: [ 1 1 2 1 1 1 1 1 ]

%e 09: [ 1 1 2 2 1 1 1 ]

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

%e 11: [ 1 2 1 1 1 1 1 1 ]

%e 12: [ 1 2 2 1 1 1 1 ]

%e 13: [ 1 2 2 2 1 1 ]

%e 14: [ 1 2 3 2 1 ]

%e (End)

%e From _Joerg Arndt_, Jun 11 2013: (Start)

%e There are a(9) = 14 weakly unimodal compositions of 9 where the maximal part m appears at least m times:

%e 01: [ 1 1 1 1 1 1 1 1 1 ]

%e 02: [ 1 1 1 1 1 2 2 ]

%e 03: [ 1 1 1 1 2 2 1 ]

%e 04: [ 1 1 1 2 2 1 1 ]

%e 05: [ 1 1 1 2 2 2 ]

%e 06: [ 1 1 2 2 1 1 1 ]

%e 07: [ 1 1 2 2 2 1 ]

%e 08: [ 1 2 2 1 1 1 1 ]

%e 09: [ 1 2 2 2 1 1 ]

%e 10: [ 1 2 2 2 2 ]

%e 11: [ 2 2 1 1 1 1 1 ]

%e 12: [ 2 2 2 1 1 1 ]

%e 13: [ 2 2 2 2 1 ]

%e 14: [ 3 3 3 ]

%e (End)

%e From _Joerg Arndt_, Mar 30 2014: (Start)

%e There are a(9) = 14 compositions of 9 with first part 1, maximal up-step 1, and no consecutive up-steps:

%e 01: [ 1 1 1 1 1 1 1 1 1 ]

%e 02: [ 1 1 1 1 1 1 1 2 ]

%e 03: [ 1 1 1 1 1 1 2 1 ]

%e 04: [ 1 1 1 1 1 2 1 1 ]

%e 05: [ 1 1 1 1 1 2 2 ]

%e 06: [ 1 1 1 1 2 1 1 1 ]

%e 07: [ 1 1 1 1 2 2 1 ]

%e 08: [ 1 1 1 2 1 1 1 1 ]

%e 09: [ 1 1 1 2 2 1 1 ]

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

%e 11: [ 1 1 2 1 1 1 1 1 ]

%e 12: [ 1 1 2 2 1 1 1 ]

%e 13: [ 1 1 2 2 2 1 ]

%e 14: [ 1 1 2 2 3 ]

%e (End)

%e G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 14*x^9 + ...

%p b:= proc(n, i, t) option remember; `if`(n<=0, `if`(i=1, 1, 0),

%p `if`(n<0 or i<1, 0, b(n-i, i, t)+b(n-(i-1), i-1, false)+

%p `if`(t, b(n-(i+1), i+1, t), 0)))

%p end:

%p a:= n-> b(n-1, 1, true):

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

%p # second Maple program:

%p A001522 := proc(n)

%p local r,a;

%p a := 0 ;

%p if n = 0 then

%p return 1 ;

%p end if;

%p for r from 1 do

%p if r*(r+1) > 2*n then

%p return a;

%p else

%p a := a-(-1)^r*combinat[numbpart](n-r*(r+1)/2) ;

%p end if;

%p end do:

%p end proc: # _R. J. Mathar_, Mar 07 2015

%t max = 50; f[x_] := 1 + Sum[-(-1)^k*x^(k*(k+1)/2), {k, 1, max}] / Product[(1-x^k), {k, 1, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* _Jean-François Alcover_, Dec 27 2011, after g.f. *)

%t b[n_, i_, t_] := b[n, i, t] = If[n <= 0, If[i == 1, 1, 0], If[n<0 || i<1, 0, b[n-i, i, t] + b[n - (i-1), i-1, False] + If[t, b[n - (i+1), i+1, t], 0]]]; a[n_] := b[n-1, 1, True]; Table[a[n], {n, 0, 70}] (* _Jean-François Alcover_, Dec 01 2015, after _Alois P. Heinz_ *)

%t Flatten[{1, Table[Sum[(-1)^(j-1)*PartitionsP[n-j*((j+1)/2)], {j, 1, Floor[(Sqrt[8*n + 1] - 1)/2]}], {n, 1, 60}]}] (* _Vaclav Kotesovec_, Sep 26 2016 *)

%t ici[q_]:=And@@Table[q[[i]]>q[[i+2]],{i,Length[q]-2}];

%t Table[If[n==0,1,Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],OddQ@*Length],ici]]],{n,0,15}] (* _Gus Wiseman_, Mar 30 2021 *)

%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)), n))}; /* _Michael Somos_, Jul 22 2003 */

%o (PARI) N=66; q='q+O('q^N);

%o Vec( 1 + sum(n=1, N, q^(n^2)/(prod(k=1,n-1,1-q^k)^2*(1-q^n)) ) ) \\ _Joerg Arndt_, Dec 09 2012

%o (Sage)

%o def A001522(n):

%o if n < 4: return 1

%o return (number_of_partitions(n) - [p.crank() for p in Partitions(n)].count(0))/2

%o [A001522(n) for n in range(30)] # _Peter Luschny_, Sep 15 2014

%Y Cf. A000041, A059776, A001523, A001524.

%Y A version for permutations is A002467, complement A000166.

%Y The case of zero crank is A064410, ranked by A342192.

%Y The case of nonnegative crank is A064428, ranked by A352873.

%Y A strict version is A352829, complement A352828.

%Y Conjectured to be column k = 1 of A352833.

%Y These partitions (positive crank) are ranked by A352874.

%Y A000700 counts self-conjugate partitions, ranked by A088902.

%Y A064391 counts partitions by crank.

%Y A115720 and A115994 count partitions by their Durfee square.

%Y A257989 gives the crank of the partition with Heinz number n.

%Y Counting compositions: A003242, A114921, A238351, A342527, A342528, A342532.

%Y Fixed points of reversed partitions: A238352, A238394, A238395, A352822, A352830, A352872.

%Y Cf. A008292, A114088, A118199, A325187, A352827, A352832.

%K nonn,easy,nice

%O 0,5

%A _N. J. A. Sloane_

%E a(0) changed from 0 to 1 by _Joerg Arndt_, Mar 30 2014

%E Edited definition. - _N. J. A. Sloane_, Mar 31 2021