A349052 Number of weakly alternating compositions of n.

1, 1, 2, 4, 8, 16, 28, 52, 91, 161, 280, 491, 850, 1483, 2573, 4469, 7757, 13472, 23378, 40586, 70438, 122267, 212210, 368336, 639296, 1109620, 1925916, 3342755, 5801880, 10070133, 17478330, 30336518, 52653939, 91389518, 158621355, 275313226, 477850887, 829388075

Offset

0,3

Comments

We define a sequence to be weakly alternating if it is alternately weakly increasing and weakly decreasing, starting with either. A sequence is alternating iff it is a weakly alternating anti-run.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000 (Terms 0..55 from Martin Ehrenstein)

Example

The a(5) = 16 compositions:
  (1,1,1,1,1)  (1,1,1,2)  (1,1,3)  (1,4)  (5)
               (1,1,2,1)  (1,2,2)  (2,3)
               (1,2,1,1)  (1,3,1)  (3,2)
               (2,1,1,1)  (2,1,2)  (4,1)
                          (2,2,1)
                          (3,1,1)
The a(6) = 28 compositions:
  (111111)  (11112)  (1113)  (114)  (15)  (6)
            (11121)  (1122)  (132)  (24)
            (11211)  (1131)  (141)  (33)
            (12111)  (1212)  (213)  (42)
            (21111)  (1311)  (222)  (51)
                     (2121)  (231)
                     (2211)  (312)
                     (3111)  (411)

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/@IntegerPartitions[n], whkQ[#]||whkQ[-#]&]], {n, 0, 10}]

Prog

(PARI)
C(n, f)={my(M=matrix(n, n, j, k, k>=j), s=M[, n]); for(b=1, n, f=!f; M=matrix(n, n, j, k, if(k<j, if(f, M[j-k, k], M[j-k, n]-if(k>1, M[j-k, k-1]) ))); for(k=2, n, M[, k]+=M[, k-1]); s+=M[, n]); s~}
seq(n) = concat([1], C(n, 0) + C(n, 1) - vector(n, j, numdiv(j))) \\ Andrew Howroyd, Jan 31 2024

Crossrefs

The strong case is A025047, ranked by A345167.

The directed versions are A129852 and A129853, strong A025048 and A025049.

The complement is counted by A349053, strong A345192.

The version for permutations of prime indices is A349056, strong A345164.

The complement is ranked by A349057, strong A345168.

The version for patterns is A349058, strong A345194.

The multiplicative version is A349059, strong A348610.

An unordered version (partitions) is A349060, complement A349061.

The non-alternating case is A349800, ranked by A349799.

A001250 counts alternating permutations, complement A348615.

A001700 counts compositions of 2n with alternating sum 0.

A003242 counts Carlitz (anti-run) compositions.

A011782 counts compositions.

A106356 counts compositions by number of maximal anti-runs.

A344604 counts alternating compositions with twins.

A345170 counts partitions w/ an alternating permutation, ranked by A345172.

A349054 counts strict alternating compositions.

Cf. A000041, A008965, A102726, A114901, A128761, A261983, A333213, A333755, A344614, A344615, A345165, A345195.

Sequence in context: A228733 A318767 A208531 * A355969 A308542 A326116

Adjacent sequences: A349049 A349050 A349051 * A349053 A349054 A349055

Keyword

nonn

Author

Gus Wiseman, Nov 29 2021

Extensions

a(21)-a(37) from Martin Ehrenstein, Jan 08 2022

Status

approved