cp's OEIS Frontend

A349050 Number of multisets of size n that have no alternating permutations and cover an initial interval of positive integers.

%I A349050 #20 Oct 21 2024 13:14:53
%S A349050 0,0,1,1,3,4,8,12,20,32,48,80,112,192,256,448,576,1024,1280,2304,2816,
%T A349050 5120,6144,11264,13312,24576,28672,53248,61440,114688,131072,245760,
%U A349050 278528,524288,589824,1114112,1245184,2359296,2621440,4980736,5505024
%N A349050 Number of multisets of size n that have no alternating permutations and cover an initial interval of positive integers.
%C A349050 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}.
%H A349050 Andrew Howroyd, <a href="/A349050/b349050.txt">Table of n, a(n) for n = 0..1000</a>
%H A349050 Frankie Mennicucci, <a href="https://digitalcommons.montclair.edu/etd/1406/">On the Number of Strong Dominating Sets in a Graph</a>, Master's Thesis, Montclair State Univ. (2024). See p. 32.
%H A349050 Wikipedia, <a href="https://en.wikipedia.org/wiki/Alternating_permutation">Alternating permutation</a>
%F A349050 a(n) = A011782(n) - A349055(n).
%F A349050 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
%e A349050 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).
%e A349050 The a(2) = 1 through a(7) = 12 multisets:
%e A349050   {11}  {111}  {1111}  {11111}  {111111}  {1111111}
%e A349050                {1112}  {11112}  {111112}  {1111112}
%e A349050                {1222}  {12222}  {111122}  {1111122}
%e A349050                        {12223}  {111123}  {1111123}
%e A349050                                 {112222}  {1122222}
%e A349050                                 {122222}  {1122223}
%e A349050                                 {122223}  {1222222}
%e A349050                                 {123333}  {1222223}
%e A349050                                           {1222233}
%e A349050                                           {1222234}
%e A349050                                           {1233333}
%e A349050                                           {1233334}
%e A349050 As compositions:
%e A349050   (2)  (3)  (4)    (5)      (6)      (7)
%e A349050             (1,3)  (1,4)    (1,5)    (1,6)
%e A349050             (3,1)  (4,1)    (2,4)    (2,5)
%e A349050                    (1,3,1)  (4,2)    (5,2)
%e A349050                             (5,1)    (6,1)
%e A349050                             (1,1,4)  (1,1,5)
%e A349050                             (1,4,1)  (1,4,2)
%e A349050                             (4,1,1)  (1,5,1)
%e A349050                                      (2,4,1)
%e A349050                                      (5,1,1)
%e A349050                                      (1,1,4,1)
%e A349050                                      (1,4,1,1)
%t A349050 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A349050 wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
%t A349050 Table[Length[Select[allnorm[n],Select[Permutations[#],wigQ]=={}&]],{n,0,7}]
%o A349050 (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
%Y A349050 The case of weakly decreasing multiplicities is A025065.
%Y A349050 The inseparable case is A336102.
%Y A349050 A separable instead of alternating version is A336103.
%Y A349050 The version for partitions is A345165.
%Y A349050 The version for factorizations is A348380, complement A348379.
%Y A349050 The complement (still covering an initial interval) is counted by A349055.
%Y A349050 A000670 counts sequences covering an initial interval, anti-run A005649.
%Y A349050 A001250 counts alternating permutations, complement A348615.
%Y A349050 A003242 counts Carlitz (anti-run) compositions, ranked by A333489.
%Y A349050 A025047 = alternating compositions, ranked by A345167, also A025048/A025049.
%Y A349050 A049774 counts permutations avoiding the consecutive pattern (1,2,3).
%Y A349050 A325534 counts separable partitions, ranked by A335433.
%Y A349050 A325535 counts inseparable partitions, ranked by A335448.
%Y A349050 A345170 counts partitions w/ an alternating permutation, ranked by A345172.
%Y A349050 A344654 counts partitions w/o an alternating permutation, ranked by A344653.
%Y A349050 Cf. A019472, A052841, A096441, A106351, A106356, A335125, A335126, A344614, A347050, A347706, A348377, A349054.
%K A349050 nonn
%O A349050 0,5
%A A349050 _Gus Wiseman_, Dec 12 2021
%E A349050 Terms a(10) and beyond from _Andrew Howroyd_, Jan 13 2024