login
A349050
Number of multisets of size n that have no alternating permutations and cover an initial interval of positive integers.
19
0, 0, 1, 1, 3, 4, 8, 12, 20, 32, 48, 80, 112, 192, 256, 448, 576, 1024, 1280, 2304, 2816, 5120, 6144, 11264, 13312, 24576, 28672, 53248, 61440, 114688, 131072, 245760, 278528, 524288, 589824, 1114112, 1245184, 2359296, 2621440, 4980736, 5505024
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
Frankie Mennicucci, On the Number of Strong Dominating Sets in a Graph, Master's Thesis, Montclair State Univ. (2024). See p. 32.
FORMULA
a(n) = A011782(n) - A349055(n).
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 version for factorizations is A348380, complement A348379.
The complement (still covering an initial interval) is counted by A349055.
A000670 counts sequences covering an initial interval, anti-run A005649.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz (anti-run) compositions, ranked by A333489.
A025047 = alternating compositions, ranked by A345167, also A025048/A025049.
A049774 counts permutations avoiding the consecutive pattern (1,2,3).
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A344654 counts partitions w/o an alternating permutation, ranked by A344653.
Sequence in context: A195746 A088953 A281612 * A025034 A145722 A147622
KEYWORD
nonn,changed
AUTHOR
Gus Wiseman, Dec 12 2021
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Jan 13 2024
STATUS
approved