A128761 -id:A128761 - cp's OEIS frontend

A129838 Number of up/down (or down/up) compositions of n into distinct parts.

1, 1, 1, 2, 2, 3, 5, 6, 8, 11, 18, 21, 30, 38, 52, 78, 97, 128, 170, 222, 285, 421, 510, 683, 872, 1148, 1440, 1893, 2576, 3209, 4151, 5313, 6784, 8615, 10969, 13755, 18573, 22713, 29173, 36536, 46705, 57899, 73696, 91076, 114777, 148531, 182813, 228938, 287042

Offset: 0

Vladeta Jovovic, May 21 2007

Original name was: Number of alternating compositions of n into distinct parts.

A composition is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. - Gus Wiseman, Jan 15 2022

			From _Gus Wiseman_, Jan 15 2022: (Start)
The a(1) = 1 through a(8) = 8 up/down strict compositions (non-strict A025048):
  (1)  (2)  (3)    (4)    (5)    (6)      (7)      (8)
            (1,2)  (1,3)  (1,4)  (1,5)    (1,6)    (1,7)
                          (2,3)  (2,4)    (2,5)    (2,6)
                                 (1,3,2)  (3,4)    (3,5)
                                 (2,3,1)  (1,4,2)  (1,4,3)
                                          (2,4,1)  (1,5,2)
                                                   (2,5,1)
                                                   (3,4,1)
The a(1) = 1 through a(8) = 8 down/up strict compositions (non-strict A025049):
  (1)  (2)  (3)    (4)    (5)    (6)      (7)      (8)
            (2,1)  (3,1)  (3,2)  (4,2)    (4,3)    (5,3)
                          (4,1)  (5,1)    (5,2)    (6,2)
                                 (2,1,3)  (6,1)    (7,1)
                                 (3,1,2)  (2,1,4)  (2,1,5)
                                          (4,1,2)  (3,1,4)
                                                   (4,1,3)
                                                   (5,1,2)
(End)

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

The case of permutations is A000111.
This is the up/down case of A032020.
This is the strict case of A129852/A129853, strong A025048/A025049.
The undirected version is A349054.
A001250 = alternating permutations, complement A348615.
A003242 = Carlitz compositions, complement A261983.
A011782 = compositions, unordered A000041.
A025047 = alternating compositions, complement A345192.
A349052 = weakly alternating compositions, complement A349053.
Cf. A003056, A008289, A008965, A015723, A072706, A128761, A218074, A345165, A345170, A345195, A349800.

g:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(g(o-1+j, u-j), j=1..u))
    end:
b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), b(n-k, k)+b(n-k, k-1)))
    end:
a:= n-> add(b(n, k)*g(k, 0), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 22 2021

whkQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]y[[m+1]]],{m,1,Length[y]-1}];
Table[Length[Select[Join@@Permutations/@ Select[IntegerPartitions[n],UnsameQ@@#&],whkQ]],{n,0,15}] (* Gus Wiseman, Jan 15 2022 *)

G.f.: Sum_{k>=0} A000111(k)*x^(k*(k+1)/2)/Product_{i=1..k} (1-x^i). - Vladeta Jovovic, May 24 2007
a(n) = Sum_{k=0..A003056(n)} A000111(k) * A008289(n,k). - Alois P. Heinz, Dec 22 2021
a(n) = (A349054(n) + 1)/2. - Gus Wiseman, Jan 15 2022

a(0)=1 prepended by Alois P. Heinz, Dec 22 2021

Name changed from "alternating" to "up/down" by Gus Wiseman, Jan 15 2022

A381981 Number of compositions of n avoiding the patterns (1,2,3) and (3,2,1).

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 30, 56, 100, 173, 293, 482, 779, 1232, 1928, 2972, 4546, 6894, 10435, 15705, 23692, 35679, 53976, 81760, 124611, 190404, 292871, 452070, 702042, 1094034, 1713879, 2693284, 4250165, 6724535, 10673794, 16977795, 27070285, 43232232, 69167372

Offset: 0

John Tyler Rascoe, Mar 11 2025

nonn

A composition matches a pattern P if some subsequence of the composition has the same order relation as P. For example, (2,3,4), (1,2,4), and (4,4,2,1,7,1,8) all match the pattern (1,2,3).

			For n < 6 all compositions are counted.
For n = 6 and 7, the compositions that match either of the forbidden patterns are shown below:
 n=6 2 compositions match: (1,2,3) and (3,2,1), giving a(6) = 2^5 - 2 = 30;
 n=7 8 compositions match: (1,1,2,3), (1,2,1,3), (1,2,3,1), (1,3,2,1), (3,1,2,1), (3,2,1,1), (1,2,4), and (4,2,1), giving a(7) = 2^6 - 8 = 56.

Cf. A011782, A102726, A128761, A335471, A335473.

A(i,j,k) = {2*x^((i+j)*k)/((1-x^i)^k * (1-x^j)^k)}
B(i,j,k) = {x^(((i+j)*k)+i)/((1-x^i)^(k+1) * (1-x^j)^k)}
C(i,j,k) = {x^(((i+j)*k)+j)/((1-x^i)^k * (1-x^j)^(k+1))}
C_x(N) = {my(x='x+O('x^N), h=1+sum(i=1,N,(x^i)/(1-x^i))+sum(i=1,N,sum(j=i+1,N-i,sum(k=1,N-i-j, (A(i,j,k)+B(i,j,k)+C(i,j,k))*(1+sum(u=i+1,j-1,-1+1/(1-x^u)^2+2*sum(v=u+1,j-1, x^(u+v)/((1-x^u)*(1-x^v))))))))); Vec(h)}
C_x(40)

G.f.: 1 + Sum_{i>0} (x^i/(1-x^i)) + Sum_{i>0} ( Sum_{j>i} ( Sum_{k>0} ( (A(i,j,k) + B(i,j,k) + C(i,j,k))*(1 + Sum_{u=i+1..j-1} (-1 + 1/(1-x^u)^2 + 2*Sum_{v=u+1..j-1} ( x^(u+v)/((1-x^u)*(1-x^v)) ) ) ) ) ) ), where A(x,i,j,k) = 2*x^((i+j)*k)/((1-x^i)^k * (1-x^j)^k), B(x,i,j,k) = x^(((i+j)*k)+i)/((1-x^i)^(k+1) * (1-x^j)^k), and C(x,i,j,k) = x^(((j+i)*k)+j)/((1-x^i)^k * (1-x^j)^(k+1)).

cp's OEIS Frontend

A129838 Number of up/down (or down/up) compositions of n into distinct parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions