OFFSET
0,5
COMMENTS
A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). Alternating permutations of multisets are a generalization of alternating or up-down permutations of {1..n}.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1000
Frankie Mennicucci, On the Number of Strong Dominating Sets in a Graph, Master's Thesis, Montclair State Univ. (2024). See p. 32.
Wikipedia, Alternating permutation
FORMULA
a(n) = (n+2)*2^(n/2-3) for even n > 0; a(n) = (n-1)*2^((n-5)/2) for odd n. - Andrew Howroyd, Jan 13 2024
EXAMPLE
The multiset {1,2,2,2,2,3,3} has no alternating permutations, even though it does have the three anti-run permutations (2,1,2,3,2,3,2), (2,3,2,1,2,3,2), (2,3,2,3,2,1,2), so is counted under a(7).
The a(2) = 1 through a(7) = 12 multisets:
{11} {111} {1111} {11111} {111111} {1111111}
{1112} {11112} {111112} {1111112}
{1222} {12222} {111122} {1111122}
{12223} {111123} {1111123}
{112222} {1122222}
{122222} {1122223}
{122223} {1222222}
{123333} {1222223}
{1222233}
{1222234}
{1233333}
{1233334}
As compositions:
(2) (3) (4) (5) (6) (7)
(1,3) (1,4) (1,5) (1,6)
(3,1) (4,1) (2,4) (2,5)
(1,3,1) (4,2) (5,2)
(5,1) (6,1)
(1,1,4) (1,1,5)
(1,4,1) (1,4,2)
(4,1,1) (1,5,1)
(2,4,1)
(5,1,1)
(1,1,4,1)
(1,4,1,1)
MATHEMATICA
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[allnorm[n], Select[Permutations[#], wigQ]=={}&]], {n, 0, 7}]
PROG
(PARI) a(n) = if(n==0, 0, if(n%2==0, (n+2)*2^(n/2-3), (n-1)*2^((n-1)/2-2))) \\ Andrew Howroyd, Jan 13 2024
CROSSREFS
The case of weakly decreasing multiplicities is A025065.
The inseparable case is A336102.
A separable instead of alternating version is A336103.
The version for partitions is A345165.
The complement (still covering an initial interval) is counted by A349055.
A049774 counts permutations avoiding the consecutive pattern (1,2,3).
KEYWORD
nonn,changed
AUTHOR
Gus Wiseman, Dec 12 2021
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Jan 13 2024
STATUS
approved