login
A345163
Number of integer partitions of n with an alternating permutation covering an initial interval of positive integers.
27
1, 1, 0, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 11, 12, 16, 20, 23, 27, 34, 41, 48, 57, 68, 80, 94, 110, 130, 153, 175, 203, 239, 275, 317, 365, 420, 483, 553, 632, 720, 825, 938, 1064, 1211, 1370, 1550, 1755, 1982, 2235, 2517, 2830, 3182, 3576, 4006, 4487, 5027, 5619, 6275, 7007, 7812
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
FORMULA
The Heinz numbers of these partitions are A333217 /\ A345172.
a(n) = A000009(n) - A345162(n). - Andrew Howroyd, Jan 31 2024
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
Not requiring an alternating permutation gives A000670, ranked by A333217.
The complement in covering partitions is counted by A345162.
Not requiring normality gives A345170, ranked by A345172.
A000041 counts integer partitions.
A001250 counts alternating permutations.
A003242 counts anti-run compositions.
A005649 counts anti-run patterns.
A025047 counts alternating or wiggly compositions, also A025048, A025049.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344605 counts alternating patterns with twins.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions without a alternating permutation, ranked by A345171.
A349051 ranks alternating compositions.
Sequence in context: A210715 A072926 A080087 * A369728 A369986 A035657
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 12 2021
EXTENSIONS
a(26) onwards from Andrew Howroyd, Jan 31 2024
STATUS
approved