A034297 -id:A034297 - cp's OEIS frontend

A325591 Number of compositions of n with circular differences all equal to 1, 0, or -1.

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

A238872 Number of strongly unimodal compositions of n with absolute difference of successive parts = 1.

Original entry on oeis.org

1, 1, 1, 3, 2, 3, 3, 4, 3, 6, 4, 3, 5, 6, 4, 9, 5, 3, 7, 7, 5, 9, 6, 6, 8, 9, 5, 9, 8, 6, 10, 6, 5, 15, 8, 9, 10, 7, 7, 12, 10, 3, 11, 15, 7, 15, 8, 6, 13, 12, 9, 12, 9, 9, 14, 12, 7, 15, 12, 6, 15, 13, 6, 21, 12, 12, 13, 6, 11, 15, 15, 9, 14, 12, 8, 24, 10, 9

Offset: 0

Joerg Arndt, Mar 21 2014

nonn

			The a(33) = 15 such compositions of 33 are:
01:  [ 1 2 3 4 5 6 5 4 3 ]
02:  [ 2 3 4 5 6 7 6 ]
03:  [ 3 4 5 6 5 4 3 2 1 ]
04:  [ 3 4 5 6 7 8 ]
05:  [ 4 5 6 7 6 5 ]
06:  [ 5 6 7 6 5 4 ]
07:  [ 5 6 7 8 7 ]
08:  [ 6 7 6 5 4 3 2 ]
09:  [ 7 8 7 6 5 ]
10:  [ 8 7 6 5 4 3 ]
11:  [ 10 11 12 ]
12:  [ 12 11 10 ]
13:  [ 16 17 ]
14:  [ 17 16 ]
15:  [ 33 ]
G.f. = 1 + x + x^2 + 3*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 4*x^7 + 3*x^8 + 6*x^9 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Dandan Chen and Rong Chen, Generating Functions of the Hurwitz Class Numbers Associated with Certain Mock Theta Functions, arXiv:2107.04809 [math.NT], 2021.

Cf. A001522, A001523, A005169, A034297, A059618, A238870, A238871, A130695.

a[ n_] := If[ n < 1, Boole[n == 0], If[ OddQ[n], 1, 1/3] Length @ FindInstance[ {x >= 0, y >= 0, z >= 0, x y + y z + z x + x + y + z + 1 == n}, {x, y, z}, Integers, 10^9]]; (* Michael Somos, Jul 04 2015 *)
a[ n_] := If[ n < 1, Boole[n == 0], Length @ FindInstance[ {1 <= y <= n, 1 <= x <= y, 1 <= z <= y, y^2 + (x - x^2 + z - z^2) / 2 == n}, {x, y, z}, Integers, 10^9]]; (* Michael Somos, Jul 04 2015 *)

\\ generate the compositions
a(n)=
{
    if ( n==0, return(1) );
    my( ret=0 );
    my( as, ts );
    for (f=1, n,  \\ first part
        as = 0;
        for (p=f, n, \\ numper of parts in rising half
            as += p; \\ ascending sum
            if ( as > n, break() );
            if ( as == n,  ret+=1;  break() );
            ts = as;  \\ total sum
            forstep (q=p-1, 1, -1,
                ts += q;  \\ descending sum
                if ( ts > n, break() );
                if ( ts == n,  ret+=1;  break() );
            );
        );
    );
    return( ret );
}
v=vector(100,n,a(n-1))

a(2*n) = A130695(2*n) / 3 if n>0. a(2*n + 1) = A130695(2*n + 1) = 3 * H(8*n + 3), where H is the Hurwitz class number, if n>0. - Michael Somos, Jul 04 2015

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

A238871 Number of weakly unimodal compositions of n with absolute difference of successive parts <= 1.

Original entry on oeis.org

1, 1, 2, 4, 6, 10, 14, 21, 27, 40, 52, 70, 92, 124, 156, 206, 264, 335, 425, 539, 673, 847, 1052, 1300, 1611, 1990, 2433, 2977, 3638, 4420, 5367, 6496, 7829, 9439, 11341, 13590, 16270, 19425, 23135, 27525, 32697, 38745, 45844, 54168, 63875, 75247, 88493, 103892

Offset: 0

Joerg Arndt, Mar 21 2014

nonn

			The a(8) = 27 such compositions are:
01:  [ 1 1 1 1 1 1 1 1 ]
02:  [ 1 1 1 1 1 1 2 ]
03:  [ 1 1 1 1 1 2 1 ]
04:  [ 1 1 1 1 2 1 1 ]
05:  [ 1 1 1 1 2 2 ]
06:  [ 1 1 1 2 1 1 1 ]
07:  [ 1 1 1 2 2 1 ]
08:  [ 1 1 1 2 3 ]
09:  [ 1 1 2 1 1 1 1 ]
10:  [ 1 1 2 2 1 1 ]
11:  [ 1 1 2 2 2 ]
12:  [ 1 2 1 1 1 1 1 ]
13:  [ 1 2 2 1 1 1 ]
14:  [ 1 2 2 2 1 ]
15:  [ 1 2 2 3 ]
16:  [ 1 2 3 2 ]
17:  [ 2 1 1 1 1 1 1 ]
18:  [ 2 2 1 1 1 1 ]
19:  [ 2 2 2 1 1 ]
20:  [ 2 2 2 2 ]
21:  [ 2 3 2 1 ]
22:  [ 2 3 3 ]
23:  [ 3 2 1 1 1 ]
24:  [ 3 2 2 1 ]
25:  [ 3 3 2 ]
26:  [ 4 4 ]
27:  [ 8 ]

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A001522, A001523, A005169, A034297, A238870, A238872.

A090752 Number of compositions (ordered partitions) of n whereby at most 1 increase is allowed and this increase must be by 1.

Original entry on oeis.org

1, 2, 4, 7, 13, 21, 36, 56, 89, 134, 204, 296, 435, 618, 879, 1223, 1702, 2323, 3171, 4263, 5720, 7589, 10043, 13158, 17202, 22305, 28839, 37038, 47437, 60391, 76686, 96872, 122047, 153081, 191513, 238625, 296620, 367379, 453948, 559112, 687107

Offset: 1

Jon Perry, Feb 06 2004

nonn

The number of compositions of n in which exactly 1 increase is allowed and this increase must be by 1, is a(n)-A000041(n). - Vladeta Jovovic, Feb 09 2004

			a(5)=13, as we have 5, 41, 32, 23, 311, 221, 212, 122, 2111, 1211, 1121, 1112 and 11111.

Cf. A034297, A003116, A000041.

Ta = matrix(70, 70, i, j, -1); Tn = Ta;
doAllowed(last, left) = local(c); c = Ta[last, left]; if (c == -1, c = 0; for (i = 1, min(last, left), c += b(i, left - i, 1)); c += b(last + 1, left - last - 1, 0); Ta[last, left] = c); c;
doNot(last, left) = local(c); c = Tn[last, left]; if (c == -1, c = 0; for (i = 1, min(last, left), c += b(i, left - i, 0)); Tn[last, left] = c); c;
b(last, left, allowed) = if (left == 0, return(1)); if (left < 0, return(0)); if (allowed, doAllowed(last, left), doNot(last, left));
a(n) = sum (i = 1, n, b(i, n - i, 1)); \\ David Wasserman, Feb 02 2006

More terms from Vladeta Jovovic, Feb 13 2004

More terms from David Wasserman, Feb 02 2006

cp's OEIS Frontend

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

A238872 Number of strongly unimodal compositions of n with absolute difference of successive parts = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

A238871 Number of weakly unimodal compositions of n with absolute difference of successive parts <= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

A090752 Number of compositions (ordered partitions) of n whereby at most 1 increase is allowed and this increase must be by 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions