A309938 -id:A309938 - cp's OEIS frontend

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

1, 1, 1, 3, 2, 4, 5, 5, 7, 10, 9, 14, 16, 19, 24, 31, 35, 45, 55, 66, 84, 104, 124, 156, 192, 236, 292, 363, 444, 551, 681, 839, 1040, 1287, 1586, 1967, 2430, 3001, 3717, 4597, 5683, 7034, 8697, 10758, 13312, 16469, 20369, 25204, 31180, 38574, 47726, 59047

Offset: 0

Alois P. Heinz, Jul 08 2012

nonn

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

Alois P. Heinz, Table of n, a(n) for n = 0..5000
John Tyler Rascoe, Illustration of n = 1..16

Column k=1 of A214247, A214249.
Row sums of A309938, A364039.
Cf. A227310, A291904, A291905, A343795, A362500, A363718, A364529.

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

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

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])) )}
a(n)={my(R=matid(n), t=(n==0), m=0); while(R, m++; t+=vecsum(R[n,]); R=step(R,n)); t} \\ Andrew Howroyd, Aug 23 2019

a(n) ~ c * d^n, where d=1.23729141259673487395949649334678514763130846902468..., c=1.134796087242490181499736234755111281606636700030106.... - Vaclav Kotesovec, May 01 2014

G.f.: 1 + Sum_{k>0} G(x,k) where G(x,k) = x^k*(1 + G(x,k+1) + G(x,k-1)) for k > 0 and G(x,0) = 0. - John Tyler Rascoe, Sep 16 2023

A309931 Triangle read by rows: T(n,k) is the number of compositions of n with k parts and circular 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, 1, 6, 5, 1, 1, 2, 3, 4, 10, 6, 1, 1, 1, 3, 5, 10, 15, 7, 1, 1, 2, 1, 4, 10, 20, 21, 8, 1, 1, 1, 3, 6, 11, 21, 35, 28, 9, 1, 1, 2, 3, 4, 10, 24, 42, 56, 36, 10, 1, 1, 1, 1, 5, 10, 25, 49, 78, 84, 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, 1, 6,  5,  1;
  1, 2, 3, 4, 10,  6,  1;
  1, 1, 3, 5, 10, 15,  7,   1;
  1, 2, 1, 4, 10, 20, 21,   8,   1;
  1, 1, 3, 6, 11, 21, 35,  28,   9,   1;
  1, 2, 3, 4, 10, 24, 42,  56,  36,  10,   1;
  1, 1, 1, 5, 10, 25, 49,  78,  84,  45,  11,  1;
  1, 2, 3, 4, 10, 24, 56,  96, 135, 120,  55, 12,  1;
  1, 1, 3, 6, 10, 21, 57, 116, 180, 220, 165, 66, 13, 1;
  ...
For n = 6 there are a total of 15 compositions:
  k = 1: (6)
  k = 2: (33)
  k = 3: (222)
  k = 4: (1122), (1212), (1221), (2112), (2121), (2211)
  k = 5: (11112), (11121), (11211), (12111), (21111)
  k = 6: (111111)

Row sums are A325591.

Cf. A309937, A309938, A309939.

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)); for(k=1, n, my(R=matrix(n, n, i, j, i==j&&abs(i-k)<=1), m=0); while(R, m++; v[m]+=R[n, k]; 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.
T(n, n - 1) = binomial(n-1, 1) = n - 1.
T(n, n - 2) = binomial(n-2, 2).

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

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

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

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.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

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

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

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

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