A309939 -id:A309939 - cp's OEIS frontend

A034297 Number of ordered positive integer solutions (m_1, m_2, ..., m_k) (for some k) to Sum_{i=1..k} m_i=n with |m_i-m_{i-1}| <= 1 for i = 2 ... k.

1, 1, 2, 4, 6, 11, 17, 29, 47, 78, 130, 215, 357, 595, 990, 1651, 2748, 4584, 7643, 12744, 21256, 35451, 59133, 98636, 164531, 274463, 457837, 763746, 1274060, 2125356, 3545491, 5914545, 9866602, 16459421, 27457549, 45804648, 76411272, 127469285, 212644336

Offset: 0

Erich Friedman

nonn

Compositions of n where successive parts differ by at most 1, see example. [Joerg Arndt, Dec 10 2012]

			From _Joerg Arndt_, Dec 10 2012: (Start)
The a(6) = 17 such compositions of 6 are
[ #]     composition
[ 1]    [ 1 1 1 1 1 1 ]
[ 2]    [ 1 1 1 1 2 ]
[ 3]    [ 1 1 1 2 1 ]
[ 4]    [ 1 1 2 1 1 ]
[ 5]    [ 1 1 2 2 ]
[ 6]    [ 1 2 1 1 1 ]
[ 7]    [ 1 2 1 2 ]
[ 8]    [ 1 2 2 1 ]
[ 9]    [ 1 2 3 ]
[10]    [ 2 1 1 1 1 ]
[11]    [ 2 1 1 2 ]
[12]    [ 2 1 2 1 ]
[13]    [ 2 2 1 1 ]
[14]    [ 2 2 2 ]
[15]    [ 3 2 1 ]
[16]    [ 3 3 ]
[17]    [ 6 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..4500
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.

Cf. A003116, A034296.
Column k=1 of A214246, A214248.
Row sums of A309939.

b:= proc(n, i) option remember;
      `if`(n=i, 1, `if`(n<0 or i<1, 0, add(b(n-i, i+j), j=-1..1)))
    end:
a:= n-> add(b(n, k), k=0..n):
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 06 2012

b[n_, i_] := b[n, i] = If[n == i, 1, If[n<0 || i<1, 0, Sum[b[n-i, i+j], {j, -1, 1}] ]]; a[n_] := Sum[b[n, k], {k, 1, n}]; Array[a, 50] (* Jean-François Alcover, Mar 13 2015, after Alois P. Heinz *)

N=70;  nil=-1;
T = matrix(N, N, i, j, nil);
doIt(last, left) = my(c); c = T[last, left]; if (c == nil, c = 0; for (i = max(1, last - 1), last + 1, c += b(i, left - i)); T[last, left] = c); c;
b(last, left) = if (left == 0, return(1)); if (left < 0, return(0)); doIt(last, left);
a(n) = sum (i = 1, n, b(i, n - i));
vector(N,n,a(n))  \\ David Wasserman, Feb 02 2006

from sympy.core.cache import cacheit
@cacheit
def b(n, i): return 1 if n==i else 0 if n<0 or i<1 else sum(b(n - i, i + j) for j in range(-1, 2))
def a(n): return sum(b(n, k) for k in range(n + 1))
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 14 2017, after Maple code

a(n) ~ c * d^n, where d = 1.668202067018461116361070469945501401879811945303435230637248..., c = 0.762436680050402638439806786781869262562176911054246754543346... . - Vaclav Kotesovec, Sep 02 2014

More terms from David Wasserman, Feb 02 2006

a(0)=1 prepended by Alois P. Heinz, Aug 14 2017

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

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

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

A034297 Number of ordered positive integer solutions (m_1, m_2, ..., m_k) (for some k) to Sum_{i=1..k} m_i=n with |m_i-m_{i-1}| <= 1 for i = 2 ... k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

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

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

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