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,4

Comments

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

Links

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

Formula

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

Example

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)

Maple

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

Mathematica

whkQ[y_]:=And@@Table[If[EvenQ[m], y[[m]]<y[[m+1]], 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 *)

Crossrefs

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.

Sequence in context: A084783 A265853 A376263 * A032153 A309223 A116465

Adjacent sequences: A129835 A129836 A129837 * A129839 A129840 A129841

Keyword

easy,nonn

Author

Vladeta Jovovic, May 21 2007

Extensions

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

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

Status

approved