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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

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

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