|
|
A349055
|
|
Number of multisets of size n that have an alternating permutation and cover an initial interval of positive integers.
|
|
18
|
|
|
1, 1, 1, 3, 5, 12, 24, 52, 108, 224, 464, 944, 1936, 3904, 7936, 15936, 32192, 64512, 129792, 259840, 521472, 1043456, 2091008, 4183040, 8375296, 16752640, 33525760, 67055616, 134156288, 268320768, 536739840, 1073496064, 2147205120, 4294443008, 8589344768
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
A separable instead of alternating version is A336103, complement A336102.
The case of weakly decreasing multiplicities is A336106.
The complement (still covering an initial interval) is counted by A349050.
A000670 counts sequences covering an initial interval, anti-run A005649.
A049774 counts permutations avoiding the consecutive pattern (1,2,3).
Cf. A019472, A052841, A096441, A106351, A106356, A335125, A335127, A344614, A347050, A347706, A348610, A348613, A349054.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|