A309931 -id:A309931 - cp's OEIS frontend

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.

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

Offset: 1

Andrew Howroyd, Aug 23 2019

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.

			Triangle begins:
  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;
  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)

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

Row sums are A173258.
T(2n,n) gives A364529.
Cf. A309931, A309937, A309939, A325557.

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

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

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

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

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 3, 4, 1, 1, 1, 3, 6, 5, 1, 1, 2, 3, 6, 10, 6, 1, 1, 1, 3, 7, 12, 15, 7, 1, 1, 2, 3, 6, 14, 22, 21, 8, 1, 1, 1, 3, 8, 15, 27, 37, 28, 9, 1, 1, 2, 3, 6, 16, 32, 50, 58, 36, 10, 1, 1, 1, 3, 7, 16, 35, 63, 88, 86, 45, 11, 1

Offset: 1

Andrew Howroyd, Aug 23 2019

			Triangle begins:
  1;
  1, 1;
  1, 2, 1;
  1, 1, 3, 1;
  1, 2, 3, 4,  1;
  1, 1, 3, 6,  5,  1;
  1, 2, 3, 6, 10,  6,  1;
  1, 1, 3, 7, 12, 15,  7,   1;
  1, 2, 3, 6, 14, 22, 21,   8,   1;
  1, 1, 3, 8, 15, 27, 37,  28,   9,   1;
  1, 2, 3, 6, 16, 32, 50,  58,  36,  10,   1;
  1, 1, 3, 7, 16, 35, 63,  88,  86,  45,  11,   1;
  1, 2, 3, 6, 16, 38, 74, 118, 147, 122,  55,  12,  1;
  1, 1, 3, 8, 16, 37, 83, 148, 212, 234, 167,  66, 13,  1;
  1, 2, 3, 6, 17, 40, 88, 174, 282, 366, 357, 222, 78, 14, 1;
  ...
For n = 6 there are a total of 17 compositions:
  k = 1: (6)
  k = 2: (33)
  k = 3: (123), (222), (321)
  k = 4: (1122), (1212), (1221), (2112), (2121), (2211)
  k = 5: (11112), (11121), (11211), (12111), (21111)
  k = 6: (111111)

Row sums are A034297.

Cf. A309931, A309937, A309938.

step(R,n)={matrix(n, n, i, j, if(i>j, if(j>1, R[i-j, j-1]) + R[i-j, j] + 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, 12, print(T(n)))

T(n, 1) = T(n, n) = 1.
T(n, 2) = (3 - (-1)^n)/2 for n > 1.
T(n, 3) = 3 for n > 3.
T(n, n - 1) = binomial(n-1, 1) = n - 1.
T(n, n - 2) = binomial(n-2, 2).

A309937 Irregular triangle read by rows: T(n,k) is the number of compositions of n with 2k parts and circular differences all equal to 1 or -1, (n >= 3, 1 <= k <= n/3).

Original entry on oeis.org

2, 0, 2, 0, 2, 2, 0, 0, 4, 2, 0, 2, 0, 2, 0, 2, 0, 6, 0, 4, 0, 2, 2, 0, 6, 0, 0, 2, 0, 8, 2, 0, 8, 0, 2, 0, 4, 0, 12, 0, 2, 0, 6, 0, 10, 0, 2, 0, 16, 0, 2, 2, 0, 6, 0, 20, 0, 0, 4, 0, 18, 0, 12, 2, 0, 8, 0, 30, 0, 2, 0, 2, 0, 16, 0, 30, 0, 2, 0, 6, 0, 40, 0, 14, 0, 4, 0, 20, 0, 52, 0, 2

Offset: 3

Andrew Howroyd, Aug 23 2019

All values are even since the parts must alternate between even and odd and therefore a composition is never equal to its reversal.

The longest compositions will consist of alternating 1's and 2's. The number of parts cannot then exceed n / 3.

			Triangle begins:
  2;
  0;
  2;
  0, 2;
  2, 0;
  0, 4;
  2, 0, 2;
  0, 2, 0;
  2, 0, 6;
  0, 4, 0,  2;
  2, 0, 6,  0;
  0, 2, 0,  8;
  2, 0, 8,  0,  2;
  0, 4, 0, 12,  0;
  2, 0, 6,  0, 10;
  0, 2, 0, 16,  0,   2;
  2, 0, 6,  0, 20,   0;
  0, 4, 0, 18,  0,  12;
  2, 0, 8,  0, 30,   0,   2;
  0, 2, 0, 16,  0,  30,   0;
  2, 0, 6,  0, 40,   0,  14;
  0, 4, 0, 20,  0,  52,   0,   2;
  2, 0, 6,  0, 42,   0,  42,   0;
  0, 2, 0, 16,  0,  78,   0,  16;
  2, 0, 8,  0, 50,   0,  84,   0,  2;
  0, 4, 0, 18,  0,  96,   0,  56,  0;
  2, 0, 6,  0, 50,   0, 140,   0, 18;
  0, 2, 0, 16,  0, 116,   0, 128,  0, 2;
  ...
For n = 11 there are a total of 8 compositions:
  k = 1: (56), (65)
  k = 3: (121232), (123212), (212123), (212321), (232121), (321212)

Row sums are A325589.

Cf. A309931, A309938, A309939, A325558, A325590.

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\3)); for(k=1, n, my(R=matrix(n,n,i,j,i==j&&abs(i-k)==1), m=0); while(R, m++; if(m%2==0, v[m/2]+=R[n,k]); R=step(R,n))); v}
for(n=3, 24, print(T(n)))

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

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

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A309937 Irregular triangle read by rows: T(n,k) is the number of compositions of n with 2k parts and circular differences all equal to 1 or -1, (n >= 3, 1 <= k <= n/3).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI