A345162 - OEIS

%I #20 Jan 31 2024 20:50:30

%S 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,

%T 82,92,103,121,137,151,173,195,220,248,277,311,350,393,435,488,546,

%U 605,678,754,835,928,1029,1141,1267,1400,1544,1712,1891,2081,2298,2533,2785,3068

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

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

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

%H Andrew Howroyd, <a href="/A345162/b345162.txt">Table of n, a(n) for n = 0..500</a>

%F a(n) = A000009(n) - A345163(n). - _Andrew Howroyd_, Jan 31 2024

%e The a(2) = 1 through a(10) = 6 partitions:

%e   11  111  1111  2111   21111   2221     221111    22221      32221

%e                  11111  111111  211111   2111111   321111     222211

%e                                 1111111  11111111  2211111    3211111

%e                                                    21111111   22111111

%e                                                    111111111  211111111

%e                                                               1111111111

%t normQ[m_]:=m=={}||Union[m]==Range[Max[m]];

%t wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];

%t Table[Length[Select[IntegerPartitions[n],normQ[#]&&Select[Permutations[#],wigQ[#]&]=={}&]],{n,0,15}]

%o (PARI) P(n,m)={Vec(1/prod(k=1, m, 1-y*x^k, 1+O(x*x^n)))}

%o 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

%Y The complement in covering partitions is counted by A345163.

%Y Not requiring normality gives A345165, ranked by A345171.

%Y The separable case is A345166.

%Y A000041 counts integer partitions.

%Y A000670 counts patterns, ranked by A333217.

%Y A001250 counts alternating permutations.

%Y A003242 counts anti-run compositions.

%Y A005649 counts anti-run patterns.

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

%Y A325534 counts separable partitions, ranked by A335433.

%Y A325535 counts inseparable partitions, ranked by A335448.

%Y A344604 counts alternating compositions with twins.

%Y A344605 counts alternating patterns with twins.

%Y A345164 counts alternating permutations of prime indices.

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

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

%K nonn

%O 0,6

%A _Gus Wiseman_, Jun 12 2021

%E a(26) onwards from _Andrew Howroyd_, Jan 31 2024