A173258 -id:A173258

Search: a173258 -id:a173258

Displaying 1-10 of 22 results found.

page 1 2 3

A325557

Number of compositions of n with equal differences up to sign.

+10
20

1, 1, 2, 4, 6, 8, 13, 12, 20, 24, 25, 29, 49, 40, 50, 64, 86, 80, 105, 102, 164, 175, 186, 208, 325, 316, 382, 476, 624, 660, 814, 961, 1331, 1500, 1739, 2140, 2877, 3274, 3939, 4901, 6345, 7448, 9054, 11157, 14315, 17181, 20769, 25843, 32947, 39639, 48257, 60075

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

A composition of n is a finite sequence of positive integers summing to n.

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..200

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

EXAMPLE

The a(1) = 1 through a(8) = 20 compositions:

(1) (2) (3) (4) (5) (6) (7) (8)

(11) (12) (13) (14) (15) (16) (17)

(21) (22) (23) (24) (25) (26)

(111) (31) (32) (33) (34) (35)

(121) (41) (42) (43) (44)

(1111) (131) (51) (52) (53)

(212) (123) (61) (62)

(11111) (141) (151) (71)

(222) (232) (161)

(321) (313) (242)

(1212) (12121) (323)

(2121) (1111111) (1232)

(111111) (1313)

(2123)

(2222)

(2321)

(3131)

(3212)

(21212)

(11111111)

MATHEMATICA

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Abs[Differences[#]]&]], {n, 0, 15}]

PROG

(PARI)

step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[i-j, j-s]) + if(j+s<=n, R[i-j, j+s])) )}

w(n, s)={my(R=matid(n), t=0); while(R, R=step(R, n, s); t+=vecsum(R[n, ])); t}

a(n) = {numdiv(max(1, n)) + sum(s=1, n-1, w(n, s))} \\ Andrew Howroyd, Aug 22 2019

CROSSREFS

Cf. A000079, A047966, A049988, A070211, A098504, A173258, A175342, A325545, A325546, A325547, A325548, A325552, A325558.

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 11 2019

EXTENSIONS

a(26)-a(42) from Lars Blomberg, May 30 2019

Terms a(43) and beyond from Andrew Howroyd, Aug 22 2019

STATUS

approved

A227310

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

+10
13

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,13

COMMENTS

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

LINKS

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.

FORMULA

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

EXAMPLE

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)

PROG

(PARI) 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)

(PARI)

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

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

Joerg Arndt, Jul 06 2013

STATUS

approved

A325546

Number of compositions of n with weakly increasing differences.

+10
13

1, 1, 2, 4, 7, 11, 19, 28, 41, 62, 87, 120, 170, 228, 303, 408, 534, 689, 899, 1145, 1449, 1842, 2306, 2863, 3571, 4398, 5386, 6610, 8039, 9716, 11775, 14157, 16938, 20293, 24166, 28643, 33995, 40134, 47199, 55540, 65088, 75994, 88776, 103328, 119886, 139126

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Also compositions of n whose plot is concave-up.

A composition of n is a finite sequence of positive integers summing to n.

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

EXAMPLE

The a(1) = 1 through a(6) = 19 compositions:

(1) (2) (3) (4) (5) (6)

(11) (12) (13) (14) (15)

(21) (22) (23) (24)

(111) (31) (32) (33)

(112) (41) (42)

(211) (113) (51)

(1111) (212) (114)

(311) (123)

(1112) (213)

(2111) (222)

(11111) (312)

(321)

(411)

(1113)

(2112)

(3111)

(11112)

(21111)

(111111)

MATHEMATICA

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], LessEqual@@Differences[#]&]], {n, 0, 15}]

PROG

(PARI) \\ Row sums of R(n) give A007294 (=breakdown by width).

R(n)={my(L=List(), v=vectorv(n, i, 1), w=1, t=1); while(v, listput(L, v); w++; t+=w; v=vectorv(n, i, sum(k=1, (i-w-1)\t + 1, v[i-w-(k-1)*t]))); Mat(L)}

seq(n)={my(M=R(n)); Vec(1 + sum(i=1, n, my(p=sum(w=1, min(#M, n\i), x^(w*i)*sum(j=1, n-i*w, x^j*M[j, w]))); x^i/(1 - x^i)*(1 + p + O(x*x^(n-i)))^2))} \\ Andrew Howroyd, Aug 28 2019

CROSSREFS

Cf. A000079, A000740, A007294, A008965, A070211 (concave-down compositions), A173258, A175342, A240026, A325360, A325545, A325547, A325548, A325552, A325557.

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 10 2019

EXTENSIONS

More terms from Alois P. Heinz, May 11 2019

STATUS

approved

A214247

Number A(n,k) of compositions of n where differences between neighboring parts are in {-k,k}; square array A(n,k), n>=0, k>=0, read by antidiagonals.

+10
12

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 4, 4, 1, 1, 1, 1, 1, 2, 5, 2, 1, 1, 1, 1, 1, 3, 3, 5, 4, 1, 1, 1, 1, 1, 1, 2, 2, 7, 3, 1, 1, 1, 1, 1, 1, 3, 3, 6, 10, 4, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 9, 2

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

Alois P. Heinz, Antidiagonals n = 0..140

EXAMPLE

A(5,0) = 2: [5], [1,1,1,1,1].

A(5,1) = 4: [5], [3,2], [2,3], [2,1,2].

A(5,2) = 2: [5], [1,3,1].

A(5,3) = 3: [5], [4,1], [1,4].

Square array A(n,k) begins:

1, 1, 1, 1, 1, 1, 1, 1, ...

2, 1, 1, 1, 1, 1, 1, 1, ...

2, 3, 1, 1, 1, 1, 1, 1, ...

3, 2, 3, 1, 1, 1, 1, 1, ...

2, 4, 2, 3, 1, 1, 1, 1, ...

4, 5, 3, 2, 3, 1, 1, 1, ...

2, 5, 2, 3, 2, 3, 1, 1, ...

MAPLE

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

`if`(n<1 or i<1, 0, `if`(n=i, 1, add(b(n-i, i+j, k), j={-k, k})))

end:

A:= (n, k)-> `if`(n=0, 1, add(b(n, j, k), j=1..n)):

seq(seq(A(n, d-n), n=0..d), d=0..15);

MATHEMATICA

b[n_, i_, k_] := b[n, i, k] = If[n < 1 || i < 1, 0, If[n == i, 1, Sum[b[n - i, i + j, k], { j, Union[{-k, k}]}]]]; a[n_, k_] := If[n == 0, 1, Sum[b[n, j, k], {j, 1, n}]]; Table[Table[a[n, d - n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

CROSSREFS

Columns k=0-2 give: A000005, A173258, A214254.

Rows n=0, 1 and main diagonal give: A000012.

Cf. A214246, A214248, A214249, A214257, A214258, A214268, A214269.

KEYWORD

nonn,tabl,look

AUTHOR

Alois P. Heinz, Jul 08 2012

STATUS

approved

A214249

Number A(n,k) of compositions of n where differences between neighboring parts are in {-k,...,k} \ {0}; square array A(n,k), n>=0, k>=0, read by antidiagonals.

+10
10

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 3, 4, 4, 1, 1, 1, 1, 3, 4, 5, 5, 1, 1, 1, 1, 3, 4, 7, 11, 5, 1, 1, 1, 1, 3, 4, 7, 12, 14, 7, 1, 1, 1, 1, 3, 4, 7, 14, 20, 18, 10, 1, 1, 1, 1, 3, 4, 7, 14, 21, 30, 36, 9, 1, 1, 1, 1, 3, 4, 7, 14, 23, 36, 50, 49, 14, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,14

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

EXAMPLE

A(3,0) = 1: [3].

A(4,1) = 2: [4], [1,2,1].

A(5,2) = 5: [5], [3,2], [2,3], [2,1,2], [1,3,1].

A(6,3) = 12: [6], [4,2], [3,2,1], [3,1,2], [2,4], [2,3,1], [2,1,3], [2,1,2,1], [1,4,1], [1,3,2], [1,2,3], [1,2,1,2].

Square array A(n,k) begins:

1, 1, 1, 1, 1, 1, 1, 1, ...

1, 3, 3, 3, 3, 3, 3, 3, ...

1, 2, 4, 4, 4, 4, 4, 4, ...

1, 4, 5, 7, 7, 7, 7, 7, ...

1, 5, 11, 12, 14, 14, 14, 14, ...

1, 5, 14, 20, 21, 23, 23, 23, ...

MAPLE

b:= proc(n, i, k) option remember; `if`(n<1 or i<1, 0,

`if`(n=i, 1, add(b(n-i, i+j, k), j={$-k..k} minus{0})))

end:

A:= (n, k)-> `if`(n=0, 1, add(b(n, j, min(n, k)), j=1..n)):

seq(seq(A(n, d-n), n=0..d), d=0..15);

MATHEMATICA

b[n_, i_, k_] := b[n, i, k] = If[n<1 || i<1, 0, If[n == i, 1, Sum[b[n-i, i+j, k], {j, Range[-k, -1] ~Join~ Range[k]}]]]; A[n_, k_] := If[n == 0, 1, Sum[b[n, j, Min[n, k]], {j, 1, n}]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Jan 15 2014, translated from Maple *)

CROSSREFS

Columns k=0-2 give: A000012, A173258, A214256.

Main diagonal gives: A003242.

Cf. A214246, A214247, A214248, A214257, A214258, A214268, A214269.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 08 2012

STATUS

approved

A325558

Number of compositions of n with equal circular differences up to sign.

+10
9

1, 2, 4, 5, 6, 10, 8, 16, 13, 16, 18, 32, 20, 30, 30, 57, 34, 52, 46, 96, 74, 86, 84, 174, 119, 170, 192, 306, 244, 332, 372, 628, 560, 694, 812, 1259, 1228, 1566, 1852, 2696, 2806, 3538, 4260, 5894, 6482, 8098, 9890, 13392, 15049, 18706, 23018, 30298, 35198

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A composition of n is a finite sequence of positive integers summing to n.

The circular differences of a composition c of length k are c_{i + 1} - c_i for i < k and c_1 - c_i for i = k. For example, the circular differences of (1,2,1,3) are (1,-1,2,-2).

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

EXAMPLE

The a(1) = 1 through a(8) = 16 compositions:

(1) (2) (3) (4) (5) (6) (7) (8)

(11) (12) (13) (14) (15) (16) (17)

(21) (22) (23) (24) (25) (26)

(111) (31) (32) (33) (34) (35)

(1111) (41) (42) (43) (44)

(11111) (51) (52) (53)

(222) (61) (62)

(1212) (1111111) (71)

(2121) (1232)

(111111) (1313)

(2123)

(2222)

(2321)

(3131)

(3212)

(11111111)

MATHEMATICA

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Abs[Differences[Append[#, First[#]]]]&]], {n, 15}]

PROG

(PARI)

step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[i-j, j-s]) + if(j+s<=n, R[i-j, j+s])) )}

w(n, k, s)={my(R=matrix(n, n, i, j, i==j&&abs(i-k)==s), t=0); while(R, R=step(R, n, s); t+=R[n, k]); t}

a(n) = {numdiv(max(1, n)) + sum(s=1, n-1, sum(k=1, n, w(n, k, s)))} \\ Andrew Howroyd, Aug 22 2019

CROSSREFS

Cf. A000079, A008965, A047966, A049988, A098504, A173258, A175342, A325553, A325557, A325588, A325589.

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 11 2019

EXTENSIONS

a(26)-a(42) from Lars Blomberg, May 30 2019

Terms a(43) and beyond from Andrew Howroyd, Aug 22 2019

STATUS

approved

A309938

Triangle read by rows: T(n,k) is the number of compositions of n with k parts and differences all equal to 1 or -1.

+10
8

1, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 2, 2, 0, 0, 1, 2, 1, 0, 1, 0, 0, 1, 0, 1, 4, 1, 0, 0, 0, 1, 2, 2, 0, 3, 2, 0, 0, 0, 1, 0, 1, 4, 2, 0, 1, 0, 0, 0, 1, 2, 1, 0, 3, 6, 1, 0, 0, 0, 0, 1, 0, 2, 4, 3, 0, 4, 2, 0, 0, 0, 0, 1, 2, 1, 0, 3, 8, 3, 0, 1, 0, 0, 0, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

Parts will alternate between being odd and even. For even k, a composition cannot be the same as its reversal and therefore for even k, T(n,k) is even.

LINKS

Alois P. Heinz, Rows n = 1..200, flattened

EXAMPLE

Triangle begins:

1, 0;

1, 2, 0;

1, 0, 1, 0;

1, 2, 1, 0, 0;

1, 0, 2, 2, 0, 0;

1, 2, 1, 0, 1, 0, 0;

1, 0, 1, 4, 1, 0, 0, 0;

1, 2, 2, 0, 3, 2, 0, 0, 0;

1, 0, 1, 4, 2, 0, 1, 0, 0, 0;

1, 2, 1, 0, 3, 6, 1, 0, 0, 0, 0;

1, 0, 2, 4, 3, 0, 4, 2, 0, 0, 0, 0;

1, 2, 1, 0, 3, 8, 3, 0, 1, 0, 0, 0, 0;

1, 0, 1, 4, 3, 0, 6, 8, 1, 0, 0, 0, 0, 0;

1, 2, 2, 0, 4, 10, 5, 0, 5, 2, 0, 0, 0, 0, 0;

...

For n = 6 there are a total of 5 compositions:

k = 1: (6)

k = 3: (123), (321)

k = 4: (2121), (1212)

MAPLE

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

`if`(n=i, x, add(expand(x*b(n-i, i+j)), j=[-1, 1])))

end:

T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(add(b(n, j), j=1..n)):

seq(T(n), n=1..14); # Alois P. Heinz, Jul 22 2023

MATHEMATICA

b[n_, i_] := b[n, i] = If[n < 1 || i < 1, 0, If[n == i, x, Sum[Expand[x*b[n - i, i + j]], {j, {-1, 1}}]]];

T[n_] := CoefficientList[Sum[b[n, j], {j, 1, n}], x] // Rest // PadRight[#, n]&;

Table[T[n], {n, 1, 13}] // Flatten (* Jean-François Alcover, Sep 06 2023, after Alois P. Heinz *)

PROG

(PARI)

step(R, n)={matrix(n, n, i, j, if(i>j, if(j>1, R[i-j, j-1]) + if(j+1<=n, R[i-j, j+1])) )}

T(n)={my(v=vector(n), R=matid(n), m=0); while(R, m++; v[m]+=vecsum(R[n, ]); R=step(R, n)); v}

for(n=1, 15, print(T(n)))

CROSSREFS

Row sums are A173258.

T(2n,n) gives A364529.

Cf. A309931, A309937, A309939, A325557.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Aug 23 2019

STATUS

approved

A363718

Irregular triangle read by rows. An infinite binary tree which has root node 1 in row n = 0. Each node then has left child m-1 if greater than 0 and right child m+1, where m is the value of the parent node.

+10
8

1, 2, 1, 3, 2, 2, 4, 1, 3, 1, 3, 3, 5, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 2, 4, 2, 4, 4, 6, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4, 6, 4, 6, 6, 8, 1, 3, 1, 3, 3, 5, 1, 3, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

The paths through the tree represent the compositions counted in A173258 that have first part 1.

For rows n > 1, row n starts with row n-2.

Any positive number k will first appear in the (k-1)-th row and thereafter in rows of opposite parity to k. The number of times k will appear in row n is A053121(n,k-1).

Row n >= 1 gives the row lengths of the Christmas tree pattern of order n (cf. A367508). - Paolo Xausa, Nov 26 2023

A new row can be generated by applying the morphism 1 -> 2, t -> {t-1,t+1} (for t > 1) to the previous row. - Paolo Xausa, Dec 08 2023

LINKS

Paolo Xausa, Table of n, a(n) for n = 0..13494 (rows 0..15 of the triangle, flattened).

EXAMPLE

Triangle begins:

n=0: 1;

n=1: 2;

n=2: 1, 3;

n=3: 2, 2, 4;

n=4: 1, 3, 1, 3, 3, 5;

n=5: 2, 2, 4, 2, 2, 4, 2, 4, 4, 6;

n=6: 1, 3, 1, 3, 3, 5, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7;

...

The binary tree starts with root 1 in row n = 0. In row n = 2, the parent node 2 has the first left child since 2 - 1 > 0.

The tree begins:

row

[n]

[0] 1

[1] _________2_________

/ \

[2] 1 _____3_____

\ / \

[3] __2__ __2__ __4__

/ \ / \ / \

[4] 1 3 1 3 3 5

\ / \ \ / \ / \ / \

[5] 2 2 4 2 2 4 2 4 4 6

MATHEMATICA

SubstitutionSystem[{1->{2}, t_/; t>1:>{t-1, t+1}}, {1}, 8] (* Paolo Xausa, Dec 23 2023 *)

PROG

(Python)

def A363718_rowlist(root, row):

A = [[root]]

for i in range(0, row):

A.append([])

for j in range(0, len(A[i])):

if A[i][j] != 1:

A[i+1].append(A[i][j]-1)

A[i+1].append(A[i][j]+1)

return(A)

A363718_rowlist(1, 8)

CROSSREFS

Cf. A001405 (row lengths), A000079 (row sums).

Cf. A000108, A007001, A053121, A173258, A367508, A367951, A367953.

KEYWORD

nonn,easy,tabf,changed

AUTHOR

John Tyler Rascoe, Jun 17 2023

STATUS

approved

A325553

Number of compositions of n with distinct circular differences up to sign.

+10
7

1, 1, 1, 1, 1, 1, 1, 7, 21, 31, 41, 87, 99, 191, 245, 381, 501, 735, 883, 1309, 1841, 2589, 3435, 4941, 6857, 9791, 13503, 19475, 27073, 37175, 52299, 72249, 100359, 139317, 190549, 256769, 355193, 471963, 644433, 858793, 1159161, 1530879, 2056073, 2711921

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

A composition of n is a finite sequence of positive integers summing to n.

The circular differences of a composition c of length k are c_{i + 1} - c_i for i < k and c_1 - c_i for i = k. For example, the circular differences of (1,2,1,3) are (1,-1,2,-2).

LINKS

Table of n, a(n) for n=0..43.

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

EXAMPLE

The a(1) = 1 through a(8) = 21 compositions:

(1) (2) (3) (4) (5) (6) (7) (8)

(124) (125)

(142) (134)

(214) (143)

(241) (152)

(412) (215)

(421) (251)

(314)

(341)

(413)

(431)

(512)

(521)

(1124)

(1142)

(1241)

(1421)

(2114)

(2411)

(4112)

(4211)

MATHEMATICA

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@Abs[Differences[Append[#, First[#]]]]&]], {n, 20}]

CROSSREFS

Cf. A000079, A008965, A167606, A173258, A325324, A325349, A325545, A325549, A325551, A325552, A325553, A325556, A325558.

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 11 2019

EXTENSIONS

a(0) and a(26)-a(43) from Alois P. Heinz, Jan 28 2024

STATUS

approved

A325589

Number of compositions of n whose circular differences are all 1 or -1.

+10
6

0, 0, 2, 0, 2, 2, 2, 4, 4, 2, 8, 6, 8, 10, 12, 16, 18, 20, 28, 34, 42, 48, 62, 78, 92, 112, 146, 174, 216, 264, 326, 412, 500, 614, 770, 944, 1166, 1444, 1784, 2214, 2730, 3366, 4182, 5164, 6386, 7898, 9770, 12098, 14950, 18488, 22894, 28312, 35020, 43330, 53606

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

A composition of n is a finite sequence of positive integers summing to n.

The circular differences of a composition c of length k are c_{i + 1} - c_i for i < k and c_1 - c_i for i = k. For example, the circular differences of (1,2,1,3) are (1,-1,2,-2).

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

EXAMPLE

The a(3) = 2 through a(11) = 8 compositions (empty columns not shown):

(12) (23) (1212) (34) (1232) (45) (2323) (56)

(21) (32) (2121) (43) (2123) (54) (3232) (65)

(2321) (121212) (121232)

(3212) (212121) (123212)

(212123)

(212321)

(232121)

(321212)

MATHEMATICA

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ[1, ##]&@@Abs[Differences[Append[#, First[#]]]]&]], {n, 15}]

PROG

(PARI)

step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[i-j, j-s]) + if(j+s<=n, R[i-j, j+s])) )}

a(n)={sum(k=1, n, my(R=matrix(n, n, i, j, i==j&&abs(i-k)==1), t=0); while(R, R=step(R, n, 1); t+=R[n, k]); t)} \\ Andrew Howroyd, Aug 23 2019

CROSSREFS

Cf. A000079, A008965, A034297, A173258, A325553, A325558, A325590, A325591.

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 11 2019

EXTENSIONS

Terms a(26) and beyond from Andrew Howroyd, Aug 23 2019

STATUS

approved

page 1 2 3

Search completed in 0.012 seconds