|
| |
|
|
A129838
|
|
Number of up/down (or down/up) compositions of n into distinct parts.
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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: A076571 A084783 A265853 * 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
|
| |
|
|
