A364529 -id:A364529 - 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

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.

Original entry on oeis.org

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

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.

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

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

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