|
%I #14 Jan 13 2024 13:58:43
%S 1,1,1,3,5,12,24,52,108,224,464,944,1936,3904,7936,15936,32192,64512,
%T 129792,259840,521472,1043456,2091008,4183040,8375296,16752640,
%U 33525760,67055616,134156288,268320768,536739840,1073496064,2147205120,4294443008,8589344768
%N Number of multisets of size n that have an alternating permutation and cover an initial interval of positive integers.
%C 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}.
%C 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
%H Andrew Howroyd, <a href="/A349055/b349055.txt">Table of n, a(n) for n = 0..1000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Alternating_permutation">Alternating permutation</a>
%F a(n) = A011782(n) - A349050(n).
%F 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
%e The multiset {1,2,2,3} has alternating permutations (2,1,3,2), (2,3,1,2), so is counted under a(4).
%e The a(1) = 1 through a(5) = 12 multisets:
%e {1} {1,2} {1,1,2} {1,1,2,2} {1,1,1,2,2}
%e {1,2,2} {1,1,2,3} {1,1,1,2,3}
%e {1,2,3} {1,2,2,3} {1,1,2,2,2}
%e {1,2,3,3} {1,1,2,2,3}
%e {1,2,3,4} {1,1,2,3,3}
%e {1,1,2,3,4}
%e {1,2,2,3,3}
%e {1,2,2,3,4}
%e {1,2,3,3,3}
%e {1,2,3,3,4}
%e {1,2,3,4,4}
%e {1,2,3,4,5}
%e As compositions:
%e (1) (1,1) (1,2) (2,2) (2,3)
%e (2,1) (1,1,2) (3,2)
%e (1,1,1) (1,2,1) (1,1,3)
%e (2,1,1) (1,2,2)
%e (1,1,1,1) (2,1,2)
%e (2,2,1)
%e (3,1,1)
%e (1,1,1,2)
%e (1,1,2,1)
%e (1,2,1,1)
%e (2,1,1,1)
%e (1,1,1,1,1)
%t allnorm[n_]:=If[n<=0,{{}},Function[s, Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
%t Table[Length[Select[allnorm[n], Select[Permutations[#],wigQ]!={}&]],{n,0,7}]
%o (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
%Y The strong inseparable case is A025065.
%Y A separable instead of alternating version is A336103, complement A336102.
%Y The case of weakly decreasing multiplicities is A336106.
%Y The version for non-twin partitions is A344654, ranked by A344653.
%Y The complement for non-twin partitions is A344740, ranked by A344742.
%Y The complement for partitions is A345165, ranked by A345171.
%Y The version for partitions is A345170, ranked by A345172.
%Y The version for factorizations is A348379, complement A348380.
%Y The complement (still covering an initial interval) is counted by A349050.
%Y A000670 counts sequences covering an initial interval, anti-run A005649.
%Y A001250 counts alternating permutations, complement A348615.
%Y A003242 counts Carlitz (anti-run) compositions, ranked by A333489.
%Y A025047 = alternating compositions, ranked by A345167, also A025048/A025049.
%Y A049774 counts permutations avoiding the consecutive pattern (1,2,3).
%Y A325534 counts separable partitions, ranked by A335433.
%Y A325535 counts inseparable partitions, ranked by A335448.
%Y Cf. A019472, A052841, A096441, A106351, A106356, A335125, A335127, A344614, A347050, A347706, A348610, A348613, A349054.
%K nonn
%O 0,4
%A _Gus Wiseman_, Dec 12 2021
%E Terms a(10) and beyond from _Andrew Howroyd_, Jan 13 2024
|
