A186085 -id:A186085 - cp's OEIS frontend

A186084 Triangle T(n,k) read by rows: number of 1-dimensional sandpiles (see A186085) with n grains and base length k.

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 3, 4, 1, 0, 0, 0, 0, 1, 6, 5, 1, 0, 0, 0, 0, 1, 4, 10, 6, 1, 0, 0, 0, 0, 0, 3, 10, 15, 7, 1, 0, 0, 0, 0, 0, 2, 8, 20, 21, 8, 1, 0, 0, 0, 0, 0, 1, 7, 19, 35, 28, 9, 1, 0, 0, 0, 0, 0, 0, 5, 18, 40, 56, 36, 10, 1, 0, 0, 0, 0, 0, 0, 3, 16, 41, 76, 84, 45, 11, 1, 0, 0, 0, 0, 0, 0, 1, 12, 41, 86, 133, 120, 55, 12, 1

Offset: 0

Joerg Arndt, Feb 13 2011

Compositions of n into k nonzero parts such that the first and last parts are 1 and the absolute difference between consecutive parts is <=1.
Row sums are A186085.
Column sums are the Motzkin numbers (A001006).
First nonzero entry in row n appears in column A055086(n).
From Joerg Arndt, Nov 06 2012: (Start)
The transposed triangle (with zeros omitted) is A129181.
For large k, the columns end in reverse([1, 1, 3, 5, 9, 14, 24, 35, ...]) for k even (cf. A053993) and reverse([1, 2, 3, 6, 10, 16, 26, 40, 60, 90, ...]) for k odd (cf. A201077).
The diagonals below the main diagonal are (apart from leading zeros), n, n*(n+1)/2, n*(n+1)*(n+2)/6, and the e-th diagonal appears to have a g.f. of the form f(x)/(1-x)^e.
(End)

			Triangle begins:
1;
0,1;
0,0,1;
0,0,1,1;
0,0,0,2,1;
0,0,0,1,3,1;
0,0,0,0,3,4,1;
0,0,0,0,1,6,5,1;
0,0,0,0,1,4,10,6,1;
0,0,0,0,0,3,10,15,7,1;
0,0,0,0,0,2,8,20,21,8,1;
0,0,0,0,0,1,7,19,35,28,9,1;

Alois P. Heinz, Rows n = 0..140, flattened
Joerg Arndt, the first 36 rows as Pari script.

Cf. A186085 (sandpiles with n grains, row sums), A001006 (Motzkin numbers, column sums), A055086.

Cf. A186505 (antidiagonal sums).

b:= proc(n, i) option remember; `if`(n=0, `if`(i=1, 1, 0),
      `if`(n<0 or i<1, 0, expand(x*add(b(n-i, i+j), j=-1..1)) ))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..20);  # Alois P. Heinz, Jul 24 2013

b[n_, i_] := b[n, i] = If[n == 0, If[i == 1, 1, 0], If[n<0 || i<1, 0, Expand[ x*Sum[b[n-i, i+j], {j, -1, 1}]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 1]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Feb 18 2015, after Alois P. Heinz *)

{T(n,k)=local(A=1+x*y);for(i=1,n,A=1/(1-x*y-x^3*y^2*subst(A,y,x*y+x*O(x^n))));polcoeff(polcoeff(A,n,x),k,y)}
/* Paul D. Hanna */

G.f. A(x,y) satisfies:  A(x,y) = 1/(1 - x*y - x^3*y^2*A(x, x*y) ). [Paul D. Hanna, Feb 22 2011]
G.f.: (formatting to make the structure apparent)
A(x,y) = 1 /
(1 - x^1*y / (1 - x^2*y / (1 - x^5*y^2 /
(1 - x^3*y / (1 - x^4*y / (1 - x^9*y^2 /
(1 - x^5*y / (1 - x^6*y / (1 - x^13*y^2 /
(1 - x^7*y / (1 - x^8*y / (1 - x^17*y^2 / (1 -...)))))))))))))
(continued fraction). [Paul D. Hanna]
G.f.: A(x,y) = 1/(1-x*y - x^3*y^2/(1-x^2*y - x^5*y^2/(1-x^3*y - x^7*y^2/(1 -...)))) (continued fraction). [Paul D. Hanna]

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

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 35, 47, 62, 82, 107, 139, 179, 230, 293, 372, 470, 591, 740, 924, 1148, 1422, 1756, 2161, 2651, 3244, 3957, 4815, 5844, 7075, 8545, 10299, 12383, 14859, 17794, 21267, 25368, 30207, 35902, 42600, 50462, 59678, 70465, 83079, 97800, 114967, 134956, 158205, 185209, 216546, 252859

Offset: 0

N. J. A. Sloane

Also number of partitions of n with positive crank (n>=2), cf. A064391. - Vladeta Jovovic, Sep 30 2001
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
Number of weakly unimodal compositions of n where the maximal part m appears at least m times, see example. - Joerg Arndt, Jun 11 2013
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
It would seem from Stanley that he regards a(0)=0 for this sequence and A001523. - Michael Somos, Feb 22 2015
From Gus Wiseman, Mar 30 2021: (Start)
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:
  (1)  (2)  (3)  (4)    (5)    (6)    (7)    (8)    (9)
                 (211)  (221)  (231)  (241)  (251)  (261)
                        (311)  (312)  (322)  (332)  (342)
                               (321)  (331)  (341)  (351)
                               (411)  (412)  (413)  (423)
                                      (421)  (422)  (432)
                                      (511)  (431)  (441)
                                             (512)  (513)
                                             (521)  (522)
                                             (611)  (531)
                                                    (612)
                                                    (621)
                                                    (711)
                                                    (32211)
(End)
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
From Gus Wiseman, May 23 2022: (Start)
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:
  (1)  (11)  (111)  (22)    (32)     (42)      (52)       (62)
                    (1111)  (221)    (222)     (322)      (422)
                            (11111)  (321)     (421)      (521)
                                     (2211)    (2221)     (2222)
                                     (111111)  (3211)     (3221)
                                               (22111)    (4211)
                                               (1111111)  (22211)
                                                          (32111)
                                                          (221111)
                                                          (11111111)
Note that these are not the same partitions (compare A352827 to A352874), only the same count (apparently).
(End)
The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - Jeremy Lovejoy, Sep 26 2022

			For a(6)=5 we have the following stacks:
.x... ..x.. ...x. .xx.
xxxxx xxxxx xxxxx xxxx xxxxxx
.
From _Joerg Arndt_, Dec 09 2012: (Start)
There are a(9) = 14 smooth weakly unimodal compositions of 9:
01:   [ 1 1 1 1 1 1 1 1 1 ]
02:   [ 1 1 1 1 1 1 2 1 ]
03:   [ 1 1 1 1 1 2 1 1 ]
04:   [ 1 1 1 1 2 1 1 1 ]
05:   [ 1 1 1 1 2 2 1 ]
06:   [ 1 1 1 2 1 1 1 1 ]
07:   [ 1 1 1 2 2 1 1 ]
08:   [ 1 1 2 1 1 1 1 1 ]
09:   [ 1 1 2 2 1 1 1 ]
10:   [ 1 1 2 2 2 1 ]
11:   [ 1 2 1 1 1 1 1 1 ]
12:   [ 1 2 2 1 1 1 1 ]
13:   [ 1 2 2 2 1 1 ]
14:   [ 1 2 3 2 1 ]
(End)
From _Joerg Arndt_, Jun 11 2013: (Start)
There are a(9) = 14 weakly unimodal compositions of 9 where the maximal part m appears at least m times:
01:  [ 1 1 1 1 1 1 1 1 1 ]
02:  [ 1 1 1 1 1 2 2 ]
03:  [ 1 1 1 1 2 2 1 ]
04:  [ 1 1 1 2 2 1 1 ]
05:  [ 1 1 1 2 2 2 ]
06:  [ 1 1 2 2 1 1 1 ]
07:  [ 1 1 2 2 2 1 ]
08:  [ 1 2 2 1 1 1 1 ]
09:  [ 1 2 2 2 1 1 ]
10:  [ 1 2 2 2 2 ]
11:  [ 2 2 1 1 1 1 1 ]
12:  [ 2 2 2 1 1 1 ]
13:  [ 2 2 2 2 1 ]
14:  [ 3 3 3 ]
(End)
From _Joerg Arndt_, Mar 30 2014: (Start)
There are a(9) = 14 compositions of 9 with first part 1, maximal up-step 1, and no consecutive up-steps:
01:  [ 1 1 1 1 1 1 1 1 1 ]
02:  [ 1 1 1 1 1 1 1 2 ]
03:  [ 1 1 1 1 1 1 2 1 ]
04:  [ 1 1 1 1 1 2 1 1 ]
05:  [ 1 1 1 1 1 2 2 ]
06:  [ 1 1 1 1 2 1 1 1 ]
07:  [ 1 1 1 1 2 2 1 ]
08:  [ 1 1 1 2 1 1 1 1 ]
09:  [ 1 1 1 2 2 1 1 ]
10:  [ 1 1 1 2 2 2 ]
11:  [ 1 1 2 1 1 1 1 1 ]
12:  [ 1 1 2 2 1 1 1 ]
13:  [ 1 1 2 2 2 1 ]
14:  [ 1 1 2 2 3 ]
(End)
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 + ...

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.
G. E. Andrews, Three-quadrant Ferrers graphs, Indian J. Math., 42 (No. 1, 2000), 1-7.
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.

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
F. C. Auluck, On some new types of partitions associated with generalized Ferrers graphs, Proc. Cambridge Philos. Soc. 47, (1951), 679-686.
F. C. Auluck, On some new types of partitions associated with generalized Ferrers graphs (annotated scanned copy)
A. Blecher and A. Knopfmacher, Fixed points and matching points in partitions, Ramanujan J. 58 (2022), 23-41.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
Erich Friedman, Illustration of initial terms
A. D. Sokal, The leading root of the partial theta function, arXiv preprint arXiv:1106.1003 [math.CO], 2011.
E. M. Wright, Stacks, III, Quart. J. Math. Oxford, 23 (1972), 153-158.

Cf. A000041, A059776, A001523, A001524.
A version for permutations is A002467, complement A000166.
The case of zero crank is A064410, ranked by A342192.
The case of nonnegative crank is A064428, ranked by A352873.
A strict version is A352829, complement A352828.
Conjectured to be column k = 1 of A352833.
These partitions (positive crank) are ranked by A352874.
A000700 counts self-conjugate partitions, ranked by A088902.
A064391 counts partitions by crank.
A115720 and A115994 count partitions by their Durfee square.
A257989 gives the crank of the partition with Heinz number n.
Counting compositions: A003242, A114921, A238351, A342527, A342528, A342532.
Fixed points of reversed partitions: A238352, A238394, A238395, A352822, A352830, A352872.
Cf. A008292, A114088, A118199, A325187, A352827, A352832.

b:= proc(n, i, t) option remember; `if`(n<=0, `if`(i=1, 1, 0),
      `if`(n<0 or 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)))
    end:
a:= n-> b(n-1, 1, true):
seq(a(n), n=0..70);  # Alois P. Heinz, Feb 26 2014
# second Maple program:
A001522 := proc(n)
    local r,a;
    a := 0 ;
    if n = 0 then
        return 1 ;
    end if;
    for r from 1 do
        if r*(r+1) > 2*n then
            return a;
        else
            a := a-(-1)^r*combinat[numbpart](n-r*(r+1)/2) ;
        end if;
    end do:
end proc: # R. J. Mathar, Mar 07 2015

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. *)
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 *)
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 *)
ici[q_]:=And@@Table[q[[i]]>q[[i+2]],{i,Length[q]-2}];
Table[If[n==0,1,Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],OddQ@*Length],ici]]],{n,0,15}] (* Gus Wiseman, Mar 30 2021 *)

{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 */

N=66; q='q+O('q^N);
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

def A001522(n):
    if n < 4: return 1
    return (number_of_partitions(n) - [p.crank() for p in Partitions(n)].count(0))/2
[A001522(n) for n in range(30)]  # Peter Luschny, Sep 15 2014

a(n) = (A000041(n) - A064410(n)) / 2 for n>=2.
G.f.: 1 + ( Sum_{k>=1} -(-1)^k * x^(k*(k+1)/2) ) / ( Product_{k>=1} 1-x^k ).
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
a(n) ~ exp(Pi*sqrt(2*n/3)) / (8*sqrt(3)*n) [Auluck, 1951]. - Vaclav Kotesovec, Sep 26 2016
a(n) = A000041(n) - A064428(n). - Gus Wiseman, Mar 30 2021
a(n) = A064428(n) - A064410(n). - Gus Wiseman, May 23 2022

a(0) changed from 0 to 1 by Joerg Arndt, Mar 30 2014

Edited definition. - N. J. A. Sloane, Mar 31 2021

A227310 G.f.: 1/G(0) where G(k) = 1 + (-q)^(k+1) / (1 - (-q)^(k+1)/G(k+1) ).

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 2, 1, 1, 3, 2, 3, 4, 4, 6, 7, 8, 11, 13, 16, 20, 24, 31, 37, 46, 58, 70, 88, 108, 133, 167, 204, 252, 315, 386, 479, 594, 731, 909, 1122, 1386, 1720, 2124, 2628, 3254, 4022, 4980, 6160, 7618, 9432, 11665, 14433, 17860, 22093, 27341, 33824, 41847, 51785, 64065, 79267

Offset: 0

Joerg Arndt, Jul 06 2013

nonn

Number of rough sandpiles: 1-dimensional sandpiles (see A186085) with n grains without flat steps (no two successive parts of the corresponding composition equal), see example. - Joerg Arndt, Mar 08 2014
The sequence of such sandpiles by base length starts (n>=0) 1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, ... (A097331, essentially A000108 with interlaced zeros).  This is a consequence of the obvious connection to Dyck paths, see example. - Joerg Arndt, Mar 09 2014
a(n>=1) are the Dyck paths with area n between the x-axis and the path which return to the x-axis only once (at their end), whereas A143951 includes paths with intercalated touches of the x-axis. - R. J. Mathar, Aug 22 2018

			From _Joerg Arndt_, Mar 08 2014: (Start)
The a(21) = 7 rough sandpiles are:
:
:   1:      [ 1 2 1 2 1 2 1 2 1 2 3 2 1 ]  (composition)
:
:           o
:  o o o o ooo
: ooooooooooooo  (rendering of sandpile)
:
:
:   2:      [ 1 2 1 2 1 2 1 2 3 2 1 2 1 ]
:
:         o
:  o o o ooo o
: ooooooooooooo
:
:
:   3:      [ 1 2 1 2 1 2 3 2 1 2 1 2 1 ]
:
:       o
:  o o ooo o o
: ooooooooooooo
:
:
:   4:      [ 1 2 1 2 3 2 1 2 1 2 1 2 1 ]
:
:     o
:  o ooo o o o
: ooooooooooooo
:
:
:   5:      [ 1 2 3 2 1 2 1 2 1 2 1 2 1 ]
:
:   o
:  ooo o o o o
: ooooooooooooo
:
:
:   6:      [ 1 2 3 2 3 4 3 2 1 ]
:
:      o
:   o ooo
:  ooooooo
: ooooooooo
:
:
:   7:      [ 1 2 3 4 3 2 3 2 1 ]
:
:    o
:   ooo o
:  ooooooo
: ooooooooo
(End)
From _Joerg Arndt_, Mar 09 2014: (Start)
The A097331(9) = 14 such sandpiles with base length 9 are:
01:  [ 1 2 1 2 1 2 1 2 1 ]
02:  [ 1 2 1 2 1 2 3 2 1 ]
03:  [ 1 2 1 2 3 2 3 2 1 ]
04:  [ 1 2 1 2 3 2 1 2 1 ]
05:  [ 1 2 1 2 3 4 3 2 1 ]
06:  [ 1 2 3 2 1 2 3 2 1 ]
07:  [ 1 2 3 2 1 2 1 2 1 ]
08:  [ 1 2 3 2 3 2 1 2 1 ]
09:  [ 1 2 3 2 3 2 3 2 1 ]
10:  [ 1 2 3 4 3 2 1 2 1 ]
11:  [ 1 2 3 2 3 4 3 2 1 ]
12:  [ 1 2 3 4 3 2 3 2 1 ]
13:  [ 1 2 3 4 3 4 3 2 1 ]
14:  [ 1 2 3 4 5 4 3 2 1 ]
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from Joerg Arndt)
A. M. Odlyzko and H. S. Wilf, The editor's corner: n coins in a fountain, Amer. Math. Monthly, 95 (1988), 840-843.

Cf. A049346 (g.f.: 1 - 1/G(0), where G(k)= 1 + q^(k+1) / (1 - q^(k+1)/G(k+1) ) ).
Cf. A226728 (g.f.: 1/G(0), where G(k) = 1 + q^(k+1) / (1 - q^(k+1)/G(k+2) ) ).
Cf. A226729 (g.f.: 1/G(0), where G(k) = 1 - q^(k+1) / (1 - q^(k+1)/G(k+2) ) ).
Cf. A006958 (g.f.: 1/G(0), where G(k) = 1 - q^(k+1) / (1 - q^(k+1)/G(k+1) ) ).
Cf. A227309 (g.f.: 1/G(0), where G(k) = 1 - q^(k+1) / (1 - q^(k+2)/G(k+1) ) ).
Cf. A173258, A291874.

N = 66;  q = 'q + O('q^N);
G(k) = if(k>N, 1, 1 + (-q)^(k+1) / (1 - (-q)^(k+1) / G(k+1) ) );
gf = 1 / G(0);
Vec(gf)

N = 66;  q = 'q + O('q^N);
F(q,y,k) = if(k>N, 1, 1/(1 - y*q^2 * F(q, q^2*y, k+1) ) );
Vec( 1 + q * F(q,q,0) ) \\ Joerg Arndt, Mar 09 2014

a(0) = 1 and a(n) = abs(A049346(n)) for n>=1.
G.f.: 1/ (1-q/(1+q/ (1+q^2/(1-q^2/ (1-q^3/(1+q^3/ (1+q^4/(1-q^4/ (1-q^5/(1+q^5/ (1+-...) )) )) )) )) )).
G.f.: 1 + q * F(q,q) where F(q,y) = 1/(1 - y * q^2 * F(q, q^2*y) ); cf. A005169 and p. 841 of the Odlyzko/Wilf reference; 1/(1 - q * F(q,q)) is the g.f. of A143951. - Joerg Arndt, Mar 09 2014
G.f.: 1 + q/(1 - q^3/(1 - q^5/(1 - q^7/ (...)))) (from formulas above). - Joerg Arndt, Mar 09 2014
G.f.: F(x, x^2) where F(x,y) is the g.f. of A239927. - Joerg Arndt, Mar 29 2014
a(n) ~ c * d^n, where d = 1.23729141259673487395949649334678514763130846902468... and c = 0.0773368373684184197215007198148835507944051447907... - Vaclav Kotesovec, Sep 05 2017
G.f.: A(x) = 2 -1/A143951(x). - R. J. Mathar, Aug 23 2018

A291896 Number of 1-dimensional sandpiles with n grains piling up against the wall.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 14, 24, 40, 67, 112, 186, 312, 520, 868, 1449, 2417, 4034, 6730, 11229, 18735, 31254, 52143, 86989, 145119, 242096, 403871, 673751, 1123964, 1875014, 3127926, 5218034, 8704769, 14521354, 24224601, 40411595, 67414781, 112461579, 187608762

Offset: 0

Seiichi Manyama, Sep 05 2017

nonn

Number of compositions of n where the first part is 1 and the absolute difference between consecutive parts is <=1 (smooth compositions).

			The a(6)=9 smooth compositions of 6 are:
:
: oooooo|
:
:     o|
: ooooo|
:
:    o |
: ooooo|
:
:   o  |
: ooooo|
:
:  o   |
: ooooo|
:
:   oo|
: oooo|
:
:  o o|
: oooo|
:
:  oo |
: oooo|
:
:   o|
:  oo|
: ooo|

Seiichi Manyama, Table of n, a(n) for n = 0..4501

Cf. A186085, A291895.

b:= proc(n, i) option remember; `if`(n=0, 1,
      add(b(n-j, j), j=max(1, i-1)..min(i+1, n)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Sep 05 2017

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j], {j, Max[1, i-1], Min[i+1, n]}]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 29 2019, after Alois P. Heinz *)

from sympy.core.cache import cacheit
@cacheit
def b(n, i): return 1 if n==0 else sum(b(n - j, j) for j in range(max(1, i - 1), min(i + 1, n) + 1))
def a(n): return b(n, 0)
print([a(n) for n in range(51)]) # Indranil Ghosh, Sep 06 2017, after Maple code

A291895 Triangle read by rows: T(n,k) = T(n-k,k-1) + T(n-k,k) + T(n-k,k+1) with T(0,0) = 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 1, 0, 2, 1, 0, 3, 2, 0, 5, 3, 1, 0, 8, 5, 1, 0, 13, 9, 2, 0, 22, 14, 4, 0, 36, 24, 6, 1, 0, 60, 40, 11, 1, 0, 100, 66, 18, 2, 0, 166, 111, 31, 4, 0, 277, 184, 52, 7, 0, 461, 308, 86, 12, 1, 0, 769, 513, 146, 20, 1, 0, 1282, 855, 243, 35, 2

Offset: 0

Seiichi Manyama, Sep 05 2017

			First few rows are:
  1;
  0,  1;
  0,  1;
  0,  1,  1;
  0,  2,  1;
  0,  3,  2;
  0,  5,  3, 1;
  0,  8,  5, 1;
  0, 13,  9, 2;
  0, 22, 14, 4;
  0, 36, 24, 6, 1.

Seiichi Manyama, Rows n = 0..481, flattened

Row sums give A291896.

Columns 0-1 give A000007, A186085 (for n>0).

A129181 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n such that the area between the x-axis and the path is k (n>=0; 0<=k<=floor(n^2/4)).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 1, 4, 6, 4, 3, 2, 1, 1, 5, 10, 10, 8, 7, 5, 3, 1, 1, 1, 6, 15, 20, 19, 18, 16, 12, 8, 6, 3, 2, 1, 1, 7, 21, 35, 40, 41, 41, 36, 29, 23, 18, 12, 9, 5, 3, 1, 1, 1, 8, 28, 56, 76, 86, 93, 92, 83, 72, 62, 50, 40, 30, 22, 14, 10, 6, 3, 2, 1, 1, 9, 36, 84, 133, 168

Offset: 0

Emeric Deutsch, Apr 08 2007

Row n has 1+floor(n^2/4) terms.

Row sums are the Motzkin numbers (A001006).

			T(5,3) = 4 because we have LULLD, ULLDL, UDULD and ULDUD, where U=(1,1), L=(1,0) and D=(1,-1).
Triangle starts:
00: 1;
01: 1;
02: 1, 1;
03: 1, 2,  1;
04: 1, 3,  3,  1,  1;
05: 1, 4,  6,  4,  3,  2,  1;
06: 1, 5, 10, 10,  8,  7,  5,  3, 1, 1;
07: 1, 6, 15, 20, 19, 18, 16, 12, 8, 6, 3, 2, 1;
...
From _Joerg Arndt_, Apr 19 2014: (Start)
Row n=5 corresponds to the following Motzkin paths (dots denote zeros):
# :   height in path   area    step in path
01:  [ . . . . . . ]     0     0 0 0 0 0
02:  [ . . . . 1 . ]     1     0 0 0 + -
03:  [ . . . 1 . . ]     1     0 0 + - 0
04:  [ . . . 1 1 . ]     2     0 0 + 0 -
05:  [ . . 1 . . . ]     1     0 + - 0 0
06:  [ . . 1 . 1 . ]     2     0 + - + -
07:  [ . . 1 1 . . ]     2     0 + 0 - 0
08:  [ . . 1 1 1 . ]     3     0 + 0 0 -
09:  [ . . 1 2 1 . ]     4     0 + + - -
10:  [ . 1 . . . . ]     1     + - 0 0 0
11:  [ . 1 . . 1 . ]     2     + - 0 + -
12:  [ . 1 . 1 . . ]     2     + - + - 0
13:  [ . 1 . 1 1 . ]     3     + - + 0 -
14:  [ . 1 1 . . . ]     2     + 0 - 0 0
15:  [ . 1 1 . 1 . ]     3     + 0 - + -
16:  [ . 1 1 1 . . ]     3     + 0 0 - 0
17:  [ . 1 1 1 1 . ]     4     + 0 0 0 -
18:  [ . 1 1 2 1 . ]     5     + 0 + - -
19:  [ . 1 2 1 . . ]     4     + + - - 0
20:  [ . 1 2 1 1 . ]     5     + + - 0 -
21:  [ . 1 2 2 1 . ]     6     + + 0 - -
(End)

Alois P. Heinz, Rows n = 0..50, flattened
Clementa Alonso-González and Miguel Ángel Navarro-Pérez, Motzkin numbers and flag codes, arXiv:2207.01997 [math.CO], 2022.
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Consecutive patterns in restricted permutations and involutions, arXiv:1902.02213 [math.CO], 2019.
A. Bärtschi, B. Geissmann, D. Graf, T. Hruz, P. Penna, and T. Tschager, On computing the total displacement number via weighted Motzkin paths, arXiv:1606.05538 [cs.DS], 2016.
Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.

Cf. A001006, A057585.

Antidiagonal sums give A186085(n+1).

G:=1/(1-z-t*z^2*g[1]): for i from 1 to 13 do g[i]:=1/(1-t^i*z-t^(2*i+1)*z^2*g[i+1]) od: g[14]:=0: Gser:=simplify(series(G,z=0,13)): for n from 0 to 10 do P[n]:=sort(coeff(Gser,z,n)) od: for n from 0 to 10 do seq(coeff(P[n],t,j),j=0..floor(n^2/4)) od; # yields sequence in triangular form
# second Maple program
b:= proc(x, y, k) option remember;
      `if`(x<0 or xx^2, 0,
      `if`(x=0, 1, add(b(x-1, y+i, k-y-i/2), i=-1..1)))
    end:
T:= (n, k)-> b(n, 0, k):
seq(seq(T(n, k), k=0..floor(n^2/4)), n=0..12); # Alois P. Heinz, Jun 28 2012

b[x_, y_, k_] := b[x, y, k] = If[x<0 || xx^2, 0, If[x==0, 1, Sum[b[x-1, y+i, k-y-i/2], {i, -1, 1}]]]; T[n_, k_] := b[n, 0, k]; Table[Table[ T[n, k], {k, 0, Floor[n^2/4]}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)

G.f. G(t,z) satisfies G(t,z) = 1 + z*G(t,z) + t*z^2*G(t,t*z)*G(t,z).
Sum_{k>=0} k * T(n,k) = A057585(n).
Sum_{j=0..n} T(n-j,j) = A186085(n+1). - Alois P. Heinz, Jun 25 2023

A186505 Antidiagonal sums of triangle A186084.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 8, 9, 14, 18, 25, 34, 46, 64, 86, 119, 162, 222, 304, 416, 571, 780, 1071, 1466, 2010, 2754, 3775, 5175, 7092, 9724, 13329, 18274, 25052, 34347, 47091, 64562, 88522, 121369, 166411, 228168, 312848, 428959, 588163

Offset: 0

Paul D. Hanna, Feb 23 2011

nonn

Triangle A186084 is the number of 1-dimensional sandpiles with n grains and base length k.

The g.f. T(x,y) of triangle A186084 satisfies: T(x,y) = 1/(1 - x*y - x^3*y^2*T(x,x*y)); therefore, the g.f. of this sequence is T(x,x).

			G.f.: 1 + x^2 + x^4 + x^5 + x^6 + 2*x^7 + 2*x^8 + 3*x^9 + 4*x^10 +...

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A186084, A186085.

b:= proc(n, i) option remember; `if`(n=0, `if`(i=1, 1, 0),
      `if`(n<0 or i<1, 0, expand(x*add(b(n-i, i+j), j=-1..1)) ))
    end:
a:= n-> add(coeff(b(n-k, 1), x, k), k=0..n):
seq(a(n), n=0..70);  # Alois P. Heinz, Jul 24 2013

m = 100;
f[i_] := If[i == 0, 1, -x^(2i+3)];
g[i_] := 1 - x^(i+2);
ContinuedFractionK[f[i], g[i], {i, 0, Sqrt[m] // Ceiling}] + O[x]^m // CoefficientList[#, x]& (* Jean-François Alcover, Oct 14 2019, after Sergei N. Gladkovskii *)

{a(n)=local(Txy=1+x*y); for(i=1, n, Txy=1/(1-x*y-x^3*y^2*subst(Txy, y, x*y+x*O(x^n)))); polcoeff(subst(Txy,y,x), n, x)}

N = 66; x = 'x + O('x^N);
Q(k) = if(k>N, 1, 1/x^(k+1) - 1 - 1/Q(k+1) );
gf = 1/x^3 - (Q(0) + 1)/x^2;
Vec(gf) \\ Joerg Arndt, May 07 2013

G.f.: (1 - x/(1 - 1/B(x)))/x^3 where B(x) equals the g.f. of the row sums of triangle A186084.
G.f.: 1/(1-x^2 - x^5/(1-x^3 - x^7/(1-x^4 - x^9/(1-x^5 - x^11/(1-x^6 - x^13/(1-...)))))) (continued fraction).
G.f.: 1/(1-x^2/(1-x^3/(1-x^7/(1-x^4/(1-x^5/(1-x^11/(1-x^6/(1 -x^7/(1-x^15/(1-...)))))))))) (continued fraction).
G.f.: 1/x^3 - (Q(0) + 1)/x^2, where Q(k)= 1/x^(k+1) - 1 - 1/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 07 2013
a(n) ~ c * d^n, where d = 1.3712018040437285..., c = 0.154355235026898... . - Vaclav Kotesovec, Sep 10 2014

A238870 Number of compositions of n with c(1) = 1, c(i+1) - c(i) <= 1, and c(i+1) - c(i) != 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 2, 1, 4, 4, 4, 9, 10, 11, 21, 25, 30, 51, 62, 80, 125, 157, 208, 309, 399, 536, 772, 1013, 1373, 1938, 2574, 3503, 4882, 6540, 8918, 12329, 16611, 22672, 31183, 42182, 57588, 78952, 107092, 146202, 200037, 271831, 371057, 507053, 689885, 941558, 1285655, 1750672, 2388951, 3260459, 4442179, 6060948

Offset: 0

Joerg Arndt, Mar 09 2014

nonn

Number of fountains of n coins with at most two successive coins on the same level.

			The a(10) = 4 such compositions are:
:
:   1:  [ 1 2 1 2 1 2 1 ]  (composition)
:
:  o o o
: ooooooo   (rendering as composition)
:
:     O   O   O
:    O O O O O O O  (rendering as fountain of coins)
:
:
:   2:  [ 1 2 1 2 3 1 ]
:
:     o
:  o oo
: oooooo
:
:           O
:      O   O O
:     O O O O O O
:
:
:   3:  [ 1 2 3 1 2 1 ]
:
:   o
:  oo o
: oooooo
:
:       O
:      O O   O
:     O O O O O O
:
:
:   4:  [ 1 2 3 4 ]
:
:    o
:   oo
:  ooo
: oooo
:
:         O
:        O O
:       O O O
:      O O O O
:

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A005169 (fountains of coins), A001524 (weakly unimodal fountains of coins).
Cf. A186085 (1-dimensional sandpiles), A227310 (rough sandpiles).
Cf. A023361 (fountains of coins with all valleys at lowest level).

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      `if`(i=j, 0, b(n-j, j)), j=1..min(n, i+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, Mar 11 2014

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[If[i == j, 0, b[n-j, j]], {j, 1, Min[n, i+1]}]];
a[n_] := b[n, 0];
a /@ Range[0, 60] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

# translation of the Maple program by Alois P. Heinz
@CachedFunction
def F(n, i):
    if n == 0: return 1
    return sum( (i!=j) * F(n-j, j) for j in [1..min(n,i+1)] ) # A238870
#    return sum( F(n-j, j) for j in [1, min(n,i+1)] ) # A005169
def a(n): return F(n, 0)
print([a(n) for n in [0..50]])
# Joerg Arndt, Mar 20 2014

a(n) ~ c / r^n, where r = 0.733216317061133379740342579187365700397652443391231594... and c = 0.172010618097928709454463097802313209201440229976513439... . - Vaclav Kotesovec, Feb 17 2017

A187081 Triangle T(n,k) read by rows: sandpiles of n grains and height k.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 0, 0, 0, 0, 1, 4, 0, 0, 0, 0, 0, 1, 7, 0, 0, 0, 0, 0, 0, 1, 12, 0, 0, 0, 0, 0, 0, 0, 1, 20, 1, 0, 0, 0, 0, 0, 0, 0, 1, 33, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 54, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 88, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 143, 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 232, 44, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 376, 84, 0, 0

Offset: 0

Joerg Arndt, Mar 08 2011

See A186085 for the definition of sandpiles.

			Triangle begins:
1;
0,1;
0,1,0;
0,1,0,0;
0,1,1,0,0;
0,1,2,0,0,0;
0,1,4,0,0,0,0;
0,1,7,0,0,0,0,0;
0,1,12,0,0,0,0,0,0;
0,1,20,1,0,0,0,0,0,0;
0,1,33,2,0,0,0,0,0,0,0;
0,1,54,5,0,0,0,0,0,0,0,0;
0,1,88,11,0,0,0,0,0,0,0,0,0;
0,1,143,22,0,0,0,0,0,0,0,0,0,0;
0,1,232,44,0,0,0,0,0,0,0,0,0,0,0;
0,1,376,84,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,609,158,1,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,986,293,2,0,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,1596,535,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,2583,969,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,4180,1739,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,6764,3099,52,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;
0,1,10945,5491,103,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;
The 22 compositions corresponding to sandpiles of 9 grains are the following:
    #:    composition              height
    1:    [ 1 2 3 2 1 ]              3
    2:    [ 1 2 2 2 1 1 ]            2
    3:    [ 1 2 2 1 2 1 ]            2
    4:    [ 1 2 1 2 2 1 ]            2
    5:    [ 1 1 2 2 2 1 ]            2
    6:    [ 1 2 2 1 1 1 1 ]          2
    7:    [ 1 2 1 2 1 1 1 ]          2
    8:    [ 1 1 2 2 1 1 1 ]          2
    9:    [ 1 2 1 1 2 1 1 ]          2
   10:    [ 1 1 2 1 2 1 1 ]          2
   11:    [ 1 1 1 2 2 1 1 ]          2
   12:    [ 1 2 1 1 1 2 1 ]          2
   13:    [ 1 1 2 1 1 2 1 ]          2
   14:    [ 1 1 1 2 1 2 1 ]          2
   15:    [ 1 1 1 1 2 2 1 ]          2
   16:    [ 1 2 1 1 1 1 1 1 ]        2
   17:    [ 1 1 2 1 1 1 1 1 ]        2
   18:    [ 1 1 1 2 1 1 1 1 ]        2
   19:    [ 1 1 1 1 2 1 1 1 ]        2
   20:    [ 1 1 1 1 1 2 1 1 ]        2
   21:    [ 1 1 1 1 1 1 2 1 ]        2
   22:    [ 1 1 1 1 1 1 1 1 1 ]      1
  stats:  0 1 20 1 0 0 0 0 0 0

Row sums are A186085 (sandpiles of n grains), cf. A186084 (sandpiles by base length), A047998 (fountains of coins by base length).

For n>=2 we have T(n,1)+T(n,2) = Fibonacci(n-1).

T(n,2) = A000071(n). [Joerg Arndt, Sep 17 2013]

cp's OEIS Frontend

A186084 Triangle T(n,k) read by rows: number of 1-dimensional sandpiles (see A186085) with n grains and base length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A227310 G.f.: 1/G(0) where G(k) = 1 + (-q)^(k+1) / (1 - (-q)^(k+1)/G(k+1) ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A291896 Number of 1-dimensional sandpiles with n grains piling up against the wall.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A291895 Triangle read by rows: T(n,k) = T(n-k,k-1) + T(n-k,k) + T(n-k,k+1) with T(0,0) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

A129181 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n such that the area between the x-axis and the path is k (n>=0; 0<=k<=floor(n^2/4)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A186505 Antidiagonal sums of triangle A186084.

Views

Author

Keywords

Comments

Examples