A349054 - OEIS

%I #21 Dec 23 2021 05:23:12

%S 1,1,1,3,3,5,9,11,15,21,35,41,59,75,103,155,193,255,339,443,569,841,

%T 1019,1365,1743,2295,2879,3785,5151,6417,8301,10625,13567,17229,21937,

%U 27509,37145,45425,58345,73071,93409,115797,147391,182151,229553,297061,365625

%N Number of alternating strict compositions of n. Number of alternating (up/down or down/up) permutations of strict integer partitions of n.

%C A strict composition of n is a finite sequence of distinct positive integers summing to n.

%C A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either.

%C The case starting with an increase (or decrease, it doesn't matter in the enumeration) is counted by A129838.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Alternating_permutation">Alternating permutation</a>

%F a(n) = 2 * A129838(n) - 1.

%F G.f.: Sum_{n>0} A001250(n)*x^(n*(n+1)/2)/Product_{k=1..n}(1-x^k).

%e The a(1) = 1 through a(7) = 11 compositions:

%e   (1)  (2)  (3)    (4)    (5)    (6)      (7)

%e             (1,2)  (1,3)  (1,4)  (1,5)    (1,6)

%e             (2,1)  (3,1)  (2,3)  (2,4)    (2,5)

%e                           (3,2)  (4,2)    (3,4)

%e                           (4,1)  (5,1)    (4,3)

%e                                  (1,3,2)  (5,2)

%e                                  (2,1,3)  (6,1)

%e                                  (2,3,1)  (1,4,2)

%e                                  (3,1,2)  (2,1,4)

%e                                           (2,4,1)

%e                                           (4,1,2)

%p g:= proc(u, o) option remember;

%p       `if`(u+o=0, 1, add(g(o-1+j, u-j), j=1..u))

%p     end:

%p b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,

%p       `if`(k=0, `if`(n=0, 2, 0), b(n-k, k)+b(n-k, k-1)))

%p     end:

%p a:= n-> add(b(n, k)*g(k, 0), k=0..floor((sqrt(8*n+1)-1)/2))-1:

%p seq(a(n), n=0..46);  # _Alois P. Heinz_, Dec 22 2021

%t wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];

%t Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],wigQ]],{n,0,15}]

%Y Ranking sequences are put in parentheses below.

%Y This is the strict case of A025047/A025048/A025049 (A345167).

%Y This is the alternating case of A032020 (A233564).

%Y The unordered case (partitions) is A065033.

%Y The directed case is A129838.

%Y A001250 = alternating permutations (A349051), complement A348615 (A350250).

%Y A003242 = Carlitz (anti-run) compositions, complement A261983.

%Y A011782 = compositions, unordered A000041.

%Y A345165 = partitions without an alternating permutation (A345171).

%Y A345170 = partitions with an alternating permutation (A345172).

%Y A345192 = non-alternating compositions (A345168).

%Y A345195 = non-alternating anti-run compositions (A345169).

%Y A349800 = weakly but not strongly alternating compositions (A349799).

%Y A349052 = weakly alternating compositions, complement A349053 (A349057).

%Y Cf. A000111, A008965, A015723, A114901, A128761, A129852, A129853, A218074, A333213, A344614, A345164, A345194, A349060, A349795.

%K nonn

%O 0,4

%A _Gus Wiseman_, Dec 21 2021