A345163 Number of integer partitions of n with an alternating permutation covering an initial interval of positive integers.

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

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

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.

Cf. A000070, A103919, A335126, A344604, A344607, A344615, A344653, A344654, A344740, A345166, A345167, A345168.

Sequence in context: A210715 A072926 A080087 * A369728 A369986 A035657

Adjacent sequences: A345160 A345161 A345162 * A345164 A345165 A345166

Keyword

nonn

Author

Gus Wiseman, Jun 12 2021

Extensions

a(26) onwards from Andrew Howroyd, Jan 31 2024

Status

approved