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

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

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Wikipedia, Alternating permutation

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.

Cf. A019472, A052841, A096441, A106351, A106356, A335125, A335126, A344614, A347050, A347706, A348377, A349054.

Sequence in context: A195746 A088953 A281612 * A025034 A145722 A147622

Adjacent sequences: A349047 A349048 A349049 * A349051 A349052 A349053

Keyword

nonn

Author

Gus Wiseman, Dec 12 2021

Extensions

Terms a(10) and beyond from Andrew Howroyd, Jan 13 2024

Status

approved