OFFSET
0,7
COMMENTS
A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,3,2,2,2,2,1) has no alternating permutations, even though it has the anti-run permutations (2,3,2,3,2,1,2), (2,3,2,1,2,3,2), and (2,1,2,3,2,3,2).
A partition with k parts is alternating if and only every part has a multiplicity no greater than k/2, except either the smallest or largest part may have a multiplicity of (k+1)/2 when k is odd. - Andrew Howroyd, Jan 31 2024
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
FORMULA
EXAMPLE
The a(3) = 1 through a(12) = 7 partitions:
21 211 221 321 3211 3221 3321 4321 33221 33321
2211 22111 22211 32211 33211 43211 43221
32111 222111 322111 322211 332211
2221111 332111 432111
2222111 3222111
3221111 3321111
22221111
For example, the partition (3,3,2,1,1,1,1) has the alternating permutations (1,3,1,3,1,2,1), (1,3,1,2,1,3,1), and (1,2,1,3,1,3,1), so is counted under a(12).
MATHEMATICA
normQ[m_]:=m=={}||Union[m]==Range[Max[m]];
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[IntegerPartitions[n], normQ[#]&&Select[Permutations[#], wigQ]!={}&]], {n, 0, 15}]
PROG
(PARI) \\ See also A345162 for a faster program.
ok(k, p)={my(S=Set(p)); foreach(S, t, my(c=k+#p-2*(1+#select(x->x==t, p))); if(c<0, return(c==-1 && (t==1||t==k)))); 1}
a(n)={sum(k=1, (sqrtint(8*n+1)-1)\2, s=0; forpart(p=n-binomial(k+1, 2), s+=ok(k, Vec(p)), k); s)} \\ Andrew Howroyd, Jan 31 2024
CROSSREFS
The complement in covering partitions is counted by A345162.
A000041 counts integer partitions.
A001250 counts alternating permutations.
A003242 counts anti-run compositions.
A005649 counts anti-run patterns.
A344605 counts alternating patterns with twins.
A345164 counts alternating permutations of prime indices.
A349051 ranks alternating compositions.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 12 2021
EXTENSIONS
a(26) onwards from Andrew Howroyd, Jan 31 2024
STATUS
approved