A173258 -id:A173258 - cp's OEIS frontend

A325590 Number of necklace compositions of n with circular differences all equal to 1 or -1.

0, 0, 1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 3, 3, 4, 4, 5, 7, 6, 7, 10, 10, 11, 15, 16, 18, 23, 25, 32, 38, 43, 53, 64, 73, 89, 108, 131, 153, 188, 223, 272, 329, 395, 475, 583, 697, 848, 1027, 1247, 1506, 1837, 2223, 2708, 3282, 3993, 4848, 5913, 7175, 8745, 10640

Offset: 1

Gus Wiseman, May 12 2019

nonn

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
The circular differences of a sequence 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).
Up to rotation, a(n) is the number of ways to arrange positive integers summing to n in a circle such that adjacent parts differ by 1 or -1.

			The first 16 terms count the following compositions:
   3: (12)
   5: (23)
   6: (1212)
   7: (34)
   8: (1232)
   9: (45)
   9: (121212)
  10: (2323)
  11: (56)
  11: (121232)
  12: (2343)
  12: (12121212)
  13: (67)
  13: (123232)
  14: (3434)
  14: (12121232)
  15: (78)
  15: (123432)
  15: (232323)
  15: (1212121212)
  16: (3454)
  16: (12321232)
  16: (12123232)
The a(21) = 7 necklace compositions:
  (10,11)
  (2,3,4,5,4,3)
  (3,4,3,4,3,4)
  (1,2,1,2,1,2,3,4,3,2)
  (1,2,3,2,1,2,3,2,3,2)
  (1,2,1,2,3,2,3,2,3,2)
  (1,2,1,2,1,2,1,2,1,2,1,2,1,2)

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

Cf. A000079, A000740, A008965, A034297, A173258, A325556, A325588, A325589, A325591.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&(SameQ[1,##]&@@Abs[Differences[Append[#,First[#]]]])&]],{n,15}]

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, m=1); while(R, R=step(R,n,1); m++; t+=sumdiv(n, d, R[d,k]*d*eulerphi(n/d))/m ); t/n)} \\ Andrew Howroyd, Aug 23 2019

a(26)-a(40) from Lars Blomberg, Jun 11 2019

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

A291904 Triangle read by rows: T(n,k) = T(n-k,k-1) + T(n-k,k+1) with T(0,0) = 1 for 0 <= k <= A003056(n).

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 2, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 3, 2, 0, 0, 3, 2, 1, 1, 1, 0, 2, 3, 2, 1, 0, 0, 3, 4, 3, 1, 0, 0, 4, 4, 3, 2, 1, 0, 4, 6, 4, 2, 0, 0, 6, 7

Offset: 0

Seiichi Manyama, Sep 05 2017

T(n,k) is the number of integer compositions of n with first part 1, last part k, and all adjacent differences in {-1,1}. - John Tyler Rascoe, Aug 14 2023

			First few rows are:
  1;
  0, 1;
  0, 0;
  0, 0, 1;
  0, 1, 0;
  0, 0, 0;
  0, 0, 1, 1;
  0, 1, 0, 0;
  0, 0, 1, 0;
  0, 1, 1, 1;
  0, 1, 0, 0, 1;
  0, 0, 2, 1, 0;
  0, 2, 1, 1, 0.

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

Row sums give A291905.
Columns 0-1 give A000007, A227310 (for n>0).
Cf. A008289, A173258, A291895, A291929.

T[0, 0] = 1; T[, 0] = 0; T[n?Positive, k_] /; 0 < k <= Floor[(Sqrt[8n+1] - 1)/2] := T[n, k] = T[n-k, k-1] + T[n-k, k+1]; T[, ] = 0;
Table[T[n, k], {n, 0, 20}, {k, 0, Floor[(Sqrt[8n+1] - 1)/2]}] // Flatten (* Jean-François Alcover, May 29 2019 *)

From John Tyler Rascoe, Aug 14 2023: (Start)
This triangle is T_1(n,k) of the general triangle T_m(n,k) for compositions of this kind with first part m.
T_m(n,k) for 0 < m, 0 <= n, and 0 <= k <= A003056(n+A000217(m-1)).
T_m(0,0) = T_m(m,m) = 1.
T_m(n,k) = T_m(n-k,k-1) + T_m(n-k,k+1) for m < n and 0 < k <= A003056(n+A000217(m-1)).
T_m(n,k) = 0 for 0 < n < m or n < k.
T_m(n,0) = 0 for 0 < n. (End)

A325591 Number of compositions of n with circular differences all equal to 1, 0, or -1.

Original entry on oeis.org

1, 2, 4, 6, 11, 15, 27, 43, 68, 116, 189, 311, 519, 860, 1433, 2380, 3968, 6613, 11018, 18374, 30633, 51089, 85208, 142113, 237055, 395409, 659576, 1100262, 1835382, 3061711, 5107445, 8520122, 14213135, 23710173, 39553138, 65982316, 110071459, 183620990, 306316328

Offset: 1

Gus Wiseman, May 12 2019

nonn

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).

			The a(1) = 1 through a(6) = 15 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (22)    (23)     (33)
             (21)   (112)   (32)     (222)
             (111)  (121)   (122)    (1122)
                    (211)   (212)    (1212)
                    (1111)  (221)    (1221)
                            (1112)   (2112)
                            (1121)   (2121)
                            (1211)   (2211)
                            (2111)   (11112)
                            (11111)  (11121)
                                     (11211)
                                     (12111)
                                     (21111)
                                     (111111)

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

Row sums of A309931.

Cf. A000079, A008965, A034297, A173258, A325351, A325551, A325553, A325558, A325589, A325590.

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

step(R,n,D)={matrix(n, n, i, j, if(i>j, sum(k=1, #D, my(s=D[k]); if(j>s && 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, t+=R[n,k]; R=step(R,n,[0,1,-1])); t)} \\ Andrew Howroyd, Aug 23 2019

a(n) ~ c * d^n, where d = 1.66820206701846111636107... (see A034297), c = 0.65837031047271348106444... - Vaclav Kotesovec, Sep 21 2019

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

A362500 Number of symmetric compositions of n where differences between adjacent parts are in {-1,1}.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 3, 2, 3, 4, 2, 5, 6, 3, 5, 7, 5, 8, 8, 8, 8, 12, 10, 12, 14, 15, 16, 21, 17, 23, 24, 27, 28, 37, 34, 43, 43, 51, 51, 66, 63, 80, 78, 97, 97, 122, 116, 150, 146, 183, 179, 229, 220, 277, 276, 344, 337, 430, 413, 528, 516, 652, 635

Offset: 0

John Tyler Rascoe, Apr 22 2023

nonn

a(n) and A173258(n) have the same parity.

			The a(9) = 2 through a(14) = 6 compositions:
  (9)      (10)       (11)       (12)     (13)         (14)
  (12321)  (343)      (434)      (23232)  (454)        (545)
           (1212121)  (32123)             (32323)      (23432)
                      (2121212)           (2123212)    (1232321)
                                          (121212121)  (3212123)
                                                       (212121212)

John Tyler Rascoe, Python program

Cf. A016116 (symmetric compositions).
Cf. A173258 (compositions where differences between adjacent parts are in {-1,1}).
Cf. A003242, A350837.

Python
```
# see linked program
```

A364529 Number of compositions of 2n into n parts where differences between neighboring parts are in {-1,1}.

Original entry on oeis.org

1, 1, 0, 2, 4, 2, 0, 6, 14, 8, 0, 25, 60, 35, 0, 114, 270, 157, 0, 528, 1242, 722, 0, 2481, 5826, 3390, 0, 11816, 27728, 16145, 0, 56841, 133316, 77660, 0, 275485, 645878, 376382, 0, 1343083, 3148000, 1835076, 0, 6579707, 15418652, 8990528, 0, 32363357, 75826214

Offset: 0

Alois P. Heinz, Jul 27 2023

nonn

			a(0) = 1: (), the empty composition.
a(1) = 1: [2].
a(3) = 2: [1,2,3], [3,2,1].
a(4) = 4: [1,2,3,2], [2,1,2,3], [2,3,2,1], [3,2,1,2].
a(5) = 2: [2,1,2,3,2], [2,3,2,1,2].
a(7) = 6: [1,2,1,2,3,2,3], [1,2,3,2,1,2,3], [1,2,3,2,3,2,1], [3,2,1,2,1,2,3], [3,2,1,2,3,2,1], [3,2,3,2,1,2,1].

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

Cf. A016825, A173258, A309938.

b:= proc(n, i, k) option remember;
      `if`(n<1 or i<1 or k<0 or 3/2*k>n, 0,
      `if`(n=i, `if`(k=0, 1, 0),
       add(b(n-i, i+j, k-1), j=[-1, 1])))
    end:
a:= n-> `if`(n=0, 1, add(b(2*n, j, n-1), j=1..2*n)):
seq(a(n), n=0..48);

b[n_, i_, k_] := b[n, i, k] = If[n < 1 || i < 1 || k < 0 || 3/2*k > n, 0,       If[n == i, If[k == 0, 1, 0], Sum[b[n - i, i + j, k - 1], {j, {-1, 1}}]]];
a[n_] := If[n == 0, 1, Sum[b[2*n, j, n - 1], {j, 1, 2 n}]];
Table[a[n], {n, 0, 48}] (* Jean-François Alcover, Oct 27 2023, after Alois P. Heinz *)

a(n) = A309938(2n,n).

a(n) = 0 <=> n in { A016825 }.

A364039 Triangle read by rows: T(n,k) is the number of integer compositions of n with first part k and differences between neighboring parts in {-1,1}.

Original entry on oeis.org

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

Offset: 0

John Tyler Rascoe, Aug 06 2023

			Triangle begins:
  1;
  0, 1;
  0, 0, 1;
  0, 1, 1, 1;
  0, 1, 0, 0, 1;
  0, 0, 2, 1, 0, 1;
  0, 2, 1, 1, 0, 0, 1;
  0, 1, 1, 1, 1, 0, 0, 1;
  0, 1, 3, 2, 0, 0, 0, 0, 1;
  0, 3, 2, 1, 2, 1, 0, 0, 0, 1;
  0, 2, 3, 2, 1, 0, 0, 0, 0, 0, 1;
  ...
For n = 6 there are a total of 5 compositions:
  T(6,1) = 2: (123), (1212)
  T(6,2) = 1: (2121)
  T(6,3) = 1: (321)
  T(6,6) = 1: (6)

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

Cf. A291905 (column k=1), A173258 (row sums).

Cf. A227310, A291904, A309938, A362500, A364529.

T:= proc(n, i) option remember; `if`(n<1 or i<1, 0,
     `if`(n=i, 1, add(T(n-i, i+j), j=[-1, 1])))
    end: T(0$2):=1:
seq(seq(T(n, k), k=0..n), n=0..14);  # Alois P. Heinz, Aug 08 2023

def A364039_rowlist(row_max):
    A = []
    for n in range(0,row_max+1):
        A.append([])
        for k in range(0,n+1):
            z = 0
            if n==k: z += 1
            elif k > 1 and k-1 <= n-k: z += A[n-k][k-1]
            if k+1 <= n-k and k != 0: z += A[n-k][k+1]
            A[n].append(z)
        print(A[n])
A364039_rowlist(12)

T(n,n) = 1.
T(n,k) = T(n-k,k+1) + T(n-k,k-1) for 0 < k < n.
T(n,k) = 0 for n < k.
T(n,0) = 0 for 0 < n.

A372646 Irregular triangle read by rows, T(n,k) is the number of integer compositions of n such that their set of adjacent differences is a subset of {-1,1}, they contain 1 as a part, and have k parts. T(n,k) for n >= 0, floor(sqrt(2(n+1))-(1/2)) <= k <= floor((2n+1)/3).

Original entry on oeis.org

0, 1, 0, 2, 0, 1, 0, 1, 2, 2, 0, 0, 1, 0, 4, 1, 0, 0, 3, 2, 2, 2, 0, 1, 0, 3, 6, 1, 0, 2, 0, 4, 2, 0, 2, 8, 3, 0, 1, 0, 0, 0, 6, 8, 1, 2, 8, 5, 0, 5, 2, 0, 0, 7, 14, 4, 0, 1, 0, 4, 6, 0, 10, 10, 1, 0, 0, 8, 20, 8, 0, 6, 2, 0, 2, 3, 0, 14, 22, 5, 0, 1, 0, 0, 6

Offset: 0

John Tyler Rascoe, May 08 2024

Is there a bijection between the unrestricted compositions of k-1 and compositions of this kind with k parts for k > 0?

			T(10,4) = 2: (1,2,3,4), (4,3,2,1).
T(10,5) = 2: (2,1,2,3,2), (2,3,2,1,2).
T(10,7) = 1: (1,2,1,2,1,2,1).
Triangle T(n,k) begins:
  0;
  .  1;
  .  0;
  .  .  2;
  .  .  0, 1;
  .  .  0, 1;
  .  .  .  2, 2;
  .  .  .  0, 0, 1;
  .  .  .  0, 4, 1;
  .  .  .  0, 0, 3, 2;
  .  .  .  .  2, 2, 0, 1;
  ...

John Tyler Rascoe, Rows n = 0..70, flattened
John Tyler Rascoe, Python program.

Cf. A131577 (empirical column sums), A372647 (row sums).

Cf. A003242, A173258, A227310, A309938, A364039.

Python
```
# see linked program
```

G.f. for k-th column is C(x,k) - (x^k)*C(x,k) for k > 0 where C(x,k) is the g.f of the k-th column of A309938.

A368557 Number of compositions of n such that the set of absolute differences is a subset of the set of parts.

Original entry on oeis.org

1, 1, 1, 3, 2, 2, 11, 10, 13, 27, 58, 87, 157, 253, 438, 850, 1462, 2474, 4472, 7716, 13544, 24115, 42360, 74013, 131038, 229009, 401946, 707293, 1242059, 2177682, 3828831, 6716062, 11777179, 20678592, 36267148, 63586772, 111556751, 195610763, 342949281

Offset: 0

John Tyler Rascoe, Dec 29 2023

nonn

			For n=12, composition [2,1,2,4,3] of 12 has the set of absolute differences {1,2}, which is a subset of the set of parts {1,2,3,4}, so it counts towards a(12) = 157.
a(3) = 3 compositions: [3], [2,1], [1,2].
a(6) = 11 compositions: [6], [4,2], [2,4], [3,2,1], [3,1,2], [2,3,1], [2,1,3], [1,3,2], [1,2,3], [2,1,2,1], [1,2,1,2].

John Tyler Rascoe, Python program

Cf. A003242, A032020, A173258, A214248, A214270.

g[0] = {{}}; g[n_Integer] := g[n] = Flatten[ParallelTable[Append[#, i] & /@ g[n - i], {i, 1, n}], 1];
isC[p_List] := Module[{d}, d = Abs[Differences[p]]; Union[d] === Union[Select[d, MemberQ[p, #] &]]];
a[n_Integer] := a[n] = Count[g[n], p_ /; isC[p]];
Monitor[Table[a[n], {n, 0, 19}], {n, Table[a[m], {m, 0, n - 1}]}] (* Robert P. P. McKone, Jan 02 2024 *)

a(24)-a(38) from Alois P. Heinz, Dec 30 2023

A370665 Number of standard hexagonal Young tableaux with n cells.

Original entry on oeis.org

1, 1, 1, 3, 2, 6, 7, 16, 19, 63, 83, 172, 485, 833

Offset: 0

John Tyler Rascoe, Feb 24 2024

A hexagonal Young diagram is a finite collection of hexagons or cells, arranged in center justified rows, with row lengths being either -1 or +1 of any adjacent rows above or below a given row, see illustration in links.
Reading the number of hexagons by row gives a integer composition (ordered partition) where differences between neighboring parts are in {-1,1}. These diagrams can also be drawn with tangent circles on a hexagonal grid oriented pointy side up, see illustration link in A173258.
A standard hexagonal Young tableau is then created by filling the cells of a hexagonal Young diagram with numbers {1..n} such that all rows and downward diagonals form increasing sequences. For every hexagonal young diagram there is at least one hexagonal Young tableau.

			The integer composition [2,3,2] of 7, corresponds to the hexagonal Young diagram:
  diagram      tableau
    0 0          1 2
   0 0 0  --->  3 4 5
    0 0          6 7
Then filling in the cells sequentially by rows gives the tableau having rows [[1,2], [3,4,5], [6,7]] right diagonals [[3,6], [1,4,7], [2,5]] and left diagonals [[1,3], [2,4,6], [5,7]]; all of which contain increasing sequences.
The a(5) = 6 hexagonal Young tableaux with 5 cells are:
 1 2 3 4 5    1 2     1 2      1 3    1 2 3    1 2 4
               3     3 4 5    2 4 5    4 5      3 5
              4 5

John Tyler Rascoe, Illustration of example.
John Tyler Rascoe, Python program.
Wikipedia, Young tableau.

Cf. A173258 counts compositions where differences between neighboring parts are in {-1,1}.

Cf. A000085, A300121.

Python
```
# see linked program
```

A370929 Number of compositions of n with parts (p_1, ..., p_i) such that the set of adjacent differences is a subset of {-k,k} for some k > 0 and the number of parts equals ceiling(p_1/k).

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 3, 5, 5, 7, 5, 9, 7, 7, 10, 11, 9, 13, 9, 13, 17, 11, 14, 19, 15, 13, 20, 19, 18, 23, 19, 20, 26, 21, 20, 32, 22, 25, 27, 33, 25, 37, 21, 34, 36, 35, 24, 50, 26, 40, 37, 44, 32, 51, 31, 48, 46, 49, 34, 65, 40, 45, 54, 56, 48, 63, 42, 58

Offset: 0

John Tyler Rascoe, Mar 06 2024

			The compositions for n = 6 and n = 8 are:
6: [6], [5,1], [4,2], [3,2,1].
8: [8], [7,1], [6,2], [3,2,3], [3,5].

John Tyler Rascoe, Table of n, a(n) for n = 0..1000

Compositions such that no adjacent parts are equal is A003242.
Compositions such that the set of adjacent differences is a subset of {-1,1} is A173258 and {-2,2} is A214254.
The array A214247 counts compositions such that the set of adjacent differences is a subset of {-k,k}.

{ my(N=75, x='x+O('x^N));
my(gf= 1 + sum(p=1, N, sum(k=1, p, x^(p*ceil(p/k)) * prod(j=1, ceil(p/k)-1, (x^(-j*k) + x^(j*k))))));
Vec(gf) }

G.f.: 1 + Sum_{p>0} Sum_{k=1..p} x^(p*i) * Product_{j=1..i-1} (x^(-j*k) + x^(j*k)), where i = ceiling(p/k).

cp's OEIS Frontend

A325590 Number of necklace compositions of n with circular differences all equal to 1 or -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A291904 Triangle read by rows: T(n,k) = T(n-k,k-1) + T(n-k,k+1) with T(0,0) = 1 for 0 <= k <= A003056(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A325591 Number of compositions of n with circular differences all equal to 1, 0, or -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A362500 Number of symmetric compositions of n where differences between adjacent parts are in {-1,1}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A364529 Number of compositions of 2n into n parts where differences between neighboring parts are in {-1,1}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A364039 Triangle read by rows: T(n,k) is the number of integer compositions of n with first part k and differences between neighboring parts in {-1,1}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A372646 Irregular triangle read by rows, T(n,k) is the number of integer compositions of n such that their set of adjacent differences is a subset of {-1,1}, they contain 1 as a part, and have k parts. T(n,k) for n >= 0, floor(sqrt(2*(n+1))-(1/2)) <= k <= floor((2*n+1)/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A372646 Irregular triangle read by rows, T(n,k) is the number of integer compositions of n such that their set of adjacent differences is a subset of {-1,1}, they contain 1 as a part, and have k parts. T(n,k) for n >= 0, floor(sqrt(2(n+1))-(1/2)) <= k <= floor((2n+1)/3).