A345163 - OEIS

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

%S 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 110,130,153,175,203,239,275,317,365,420,483,553,632,720,825,938,1064,

%U 1211,1370,1550,1755,1982,2235,2517,2830,3182,3576,4006,4487,5027,5619,6275,7007,7812

%N Number of integer partitions of n with an 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 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 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 Andrew Howroyd, <a href="/A345163/b345163.txt">Table of n, a(n) for n = 0..500</a>

%F The Heinz numbers of these partitions are A333217 /\ A345172.

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

%e The a(3) = 1 through a(12) = 7 partitions:

%e   21  211  221  321   3211   3221   3321    4321     33221    33321

%e                 2211  22111  22211  32211   33211    43211    43221

%e                              32111  222111  322111   322211   332211

%e                                             2221111  332111   432111

%e                                                      2222111  3222111

%e                                                      3221111  3321111

%e                                                               22221111

%e 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 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) \\ See also A345162 for a faster program.

%o 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 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 Not requiring an alternating permutation gives A000670, ranked by A333217.

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

%Y Not requiring normality gives A345170, ranked by A345172.

%Y A000041 counts integer partitions.

%Y A001250 counts alternating permutations.

%Y A003242 counts anti-run compositions.

%Y A005649 counts anti-run patterns.

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

%Y A325534 counts separable partitions, ranked by A335433.

%Y A325535 counts inseparable partitions, ranked by A335448.

%Y A344605 counts alternating patterns with twins.

%Y A345164 counts alternating permutations of prime indices.

%Y A345165 counts partitions without a alternating permutation, ranked by A345171.

%Y A349051 ranks alternating compositions.

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

%K nonn

%O 0,7

%A _Gus Wiseman_, Jun 12 2021

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