cp's OEIS Frontend

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

%I A345163 #20 Jan 31 2024 20:50:25
%S A345163 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,
%T A345163 110,130,153,175,203,239,275,317,365,420,483,553,632,720,825,938,1064,
%U A345163 1211,1370,1550,1755,1982,2235,2517,2830,3182,3576,4006,4487,5027,5619,6275,7007,7812
%N A345163 Number of integer partitions of n with an alternating permutation covering an initial interval of positive integers.
%C A345163 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).
%C A345163 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
%H A345163 Andrew Howroyd, <a href="/A345163/b345163.txt">Table of n, a(n) for n = 0..500</a>
%F A345163 The Heinz numbers of these partitions are A333217 /\ A345172.
%F A345163 a(n) = A000009(n) - A345162(n). - _Andrew Howroyd_, Jan 31 2024
%e A345163 The a(3) = 1 through a(12) = 7 partitions:
%e A345163   21  211  221  321   3211   3221   3321    4321     33221    33321
%e A345163                 2211  22111  22211  32211   33211    43211    43221
%e A345163                              32111  222111  322111   322211   332211
%e A345163                                             2221111  332111   432111
%e A345163                                                      2222111  3222111
%e A345163                                                      3221111  3321111
%e A345163                                                               22221111
%e A345163 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).
%t A345163 normQ[m_]:=m=={}||Union[m]==Range[Max[m]];
%t A345163 wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
%t A345163 Table[Length[Select[IntegerPartitions[n],normQ[#]&&Select[Permutations[#],wigQ]!={}&]],{n,0,15}]
%o A345163 (PARI) \\ See also A345162 for a faster program.
%o A345163 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}
%o A345163 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
%Y A345163 Not requiring an alternating permutation gives A000670, ranked by A333217.
%Y A345163 The complement in covering partitions is counted by A345162.
%Y A345163 Not requiring normality gives A345170, ranked by A345172.
%Y A345163 A000041 counts integer partitions.
%Y A345163 A001250 counts alternating permutations.
%Y A345163 A003242 counts anti-run compositions.
%Y A345163 A005649 counts anti-run patterns.
%Y A345163 A025047 counts alternating or wiggly compositions, also A025048, A025049.
%Y A345163 A325534 counts separable partitions, ranked by A335433.
%Y A345163 A325535 counts inseparable partitions, ranked by A335448.
%Y A345163 A344605 counts alternating patterns with twins.
%Y A345163 A345164 counts alternating permutations of prime indices.
%Y A345163 A345165 counts partitions without a alternating permutation, ranked by A345171.
%Y A345163 A349051 ranks alternating compositions.
%Y A345163 Cf. A000070, A103919, A335126, A344604, A344607, A344615, A344653, A344654, A344740, A345166, A345167, A345168.
%K A345163 nonn
%O A345163 0,7
%A A345163 _Gus Wiseman_, Jun 12 2021
%E A345163 a(26) onwards from _Andrew Howroyd_, Jan 31 2024