OFFSET
0,4
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}.
The multisets that have an alternating permutation are those which have no part with multiplicity greater than floor(n/2) except for odd n when either the smallest or largest part can have multiplicity ceiling(n/2). - Andrew Howroyd, Jan 13 2024
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1000
Wikipedia, Alternating permutation
FORMULA
a(n) = 2^(n-1) - (n+2)*2^(n/2-3) for even n > 0; a(n) = 2^(n-1) - (n-1)*2^((n-5)/2) for odd n. - Andrew Howroyd, Jan 13 2024
EXAMPLE
The multiset {1,2,2,3} has alternating permutations (2,1,3,2), (2,3,1,2), so is counted under a(4).
The a(1) = 1 through a(5) = 12 multisets:
{1} {1,2} {1,1,2} {1,1,2,2} {1,1,1,2,2}
{1,2,2} {1,1,2,3} {1,1,1,2,3}
{1,2,3} {1,2,2,3} {1,1,2,2,2}
{1,2,3,3} {1,1,2,2,3}
{1,2,3,4} {1,1,2,3,3}
{1,1,2,3,4}
{1,2,2,3,3}
{1,2,2,3,4}
{1,2,3,3,3}
{1,2,3,3,4}
{1,2,3,4,4}
{1,2,3,4,5}
As compositions:
(1) (1,1) (1,2) (2,2) (2,3)
(2,1) (1,1,2) (3,2)
(1,1,1) (1,2,1) (1,1,3)
(2,1,1) (1,2,2)
(1,1,1,1) (2,1,2)
(2,2,1)
(3,1,1)
(1,1,1,2)
(1,1,2,1)
(1,2,1,1)
(2,1,1,1)
(1,1,1,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, 1, 2^(n-1) - if(n%2==0, (n+2)*2^(n/2-3), (n-1)*2^((n-5)/2))) \\ Andrew Howroyd, Jan 13 2024
CROSSREFS
The strong inseparable case is A025065.
The case of weakly decreasing multiplicities is A336106.
The complement (still covering an initial interval) is counted by A349050.
A049774 counts permutations avoiding the consecutive pattern (1,2,3).
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 12 2021
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Jan 13 2024
STATUS
approved