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

0, 0, 1, 1, 1, 2, 2, 3, 3, 5, 6, 6, 8, 10, 11, 15, 16, 18, 23, 27, 30, 35, 41, 47, 54, 62, 71, 82, 92, 103, 121, 137, 151, 173, 195, 220, 248, 277, 311, 350, 393, 435, 488, 546, 605, 678, 754, 835, 928, 1029, 1141, 1267, 1400, 1544, 1712, 1891, 2081, 2298, 2533, 2785, 3068

Offset

0,6

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 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).

Sequences covering an initial interval (patterns) are counted by A000670 and ranked by A333217.

Links

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

Formula

a(n) = A000009(n) - A345163(n). - Andrew Howroyd, Jan 31 2024

Example

The a(2) = 1 through a(10) = 6 partitions:
  11  111  1111  2111   21111   2221     221111    22221      32221
                 11111  111111  211111   2111111   321111     222211
                                1111111  11111111  2211111    3211111
                                                   21111111   22111111
                                                   111111111  211111111
                                                              1111111111

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) P(n, m)={Vec(1/prod(k=1, m, 1-y*x^k, 1+O(x*x^n)))}
a(n) = {(n >= 2) + sum(k=2, (sqrtint(8*n+1)-1)\2, my(r=n-binomial(k+1, 2), v=P(r, k)); sum(i=1, min(k, 2*r\k), sum(j=k-1, (2*r-(k-1)*(i-1))\(i+1), my(p=(j+k+(i==1||i==k))\2); if(p*i<=r, polcoef(v[r-p*i+1], j-p)) )))} \\ Andrew Howroyd, Jan 31 2024

Crossrefs

The complement in covering partitions is counted by A345163.

Not requiring normality gives A345165, ranked by A345171.

The separable case is A345166.

A000041 counts integer partitions.

A000670 counts patterns, ranked by A333217.

A001250 counts alternating permutations.

A003242 counts anti-run compositions.

A005649 counts anti-run patterns.

A025047 counts alternating or wiggly compositions, directed A025048/A025049.

A325534 counts separable partitions, ranked by A335433.

A325535 counts inseparable partitions, ranked by A335448.

A344604 counts alternating compositions with twins.

A344605 counts alternating patterns with twins.

A345164 counts alternating permutations of prime indices.

A345170 counts partitions with a alternating permutation, ranked by A345172.

Cf. A000070, A103919, A335126, A344614, A344615, A344653, A344654, A344740, A344742, A345167, A345168, A345192, A348609.

Sequence in context: A262365 A063988 A198453 * A316313 A325876 A325468

Adjacent sequences: A345159 A345160 A345161 * A345163 A345164 A345165

Keyword

nonn

Author

Gus Wiseman, Jun 12 2021

Extensions

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

Status

approved