login
Number of inseparable partitions of n; see Comments.
105

%I #31 Jan 31 2024 22:23:23

%S 0,0,1,1,2,2,5,5,8,11,16,19,28,35,48,60,79,99,131,161,205,256,324,397,

%T 498,609,755,921,1131,1372,1677,2022,2452,2952,3561,4260,5116,6102,

%U 7291,8667,10309,12210,14477,17087,20177,23752,27957,32804,38496,45049,52704

%N Number of inseparable partitions of n; see Comments.

%C Definition: a partition is separable if there is an ordering of its parts in which no consecutive parts are identical; otherwise the partition is inseparable.

%C A partition with k parts is inseparable if and only if there is a part whose multiplicity is greater than ceiling(k/2). - _Andrew Howroyd_, Jan 17 2024

%H Andrew Howroyd, <a href="/A325535/b325535.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) + A325534(n) = A000041(n) = number of partitions of n.

%F a(n) = Sum_{k>=1} x^(2*k-1)*(1 + x - x^(k-1))/((1-x^(k+1))*Product_{j=1..k-1} (1 - x^j)). - _Andrew Howroyd_, Jan 17 2024

%e For n=5, the partition 1+2+2 is separable as 2+1+2, and 2+1+1+1 is inseparable.

%e From _Gus Wiseman_, Jun 27 2020: (Start)

%e The a(2) = 2 through a(9) = 11 inseparable partitions:

%e 11 111 22 2111 33 2221 44 333

%e 1111 11111 222 4111 2222 3222

%e 3111 31111 5111 6111

%e 21111 211111 41111 22221

%e 111111 1111111 221111 51111

%e 311111 321111

%e 2111111 411111

%e 11111111 2211111

%e 3111111

%e 21111111

%e 111111111

%e (End)

%t u=Table[Length[Select[Map[Quotient[(1 + Length[#]), Max[Map[Length, Split[#]]]] &,

%t IntegerPartitions[nn]], # > 1 &]], {nn, 50}]

%t Table[PartitionsP[n] - u[[n]], {n, 1, Length[u]}]

%t (* _Peter J. C. Moses_, May 07 2019 *)

%t Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!MatchQ[#,{___,x_,x_,___}]&]=={}&]],{n,10}] (* _Gus Wiseman_, Jun 27 2020 *)

%o (PARI) seq(n) = {Vec(sum(k=1, (n+1)\2, x^(2*k-1)*(1 + x - x^(k-1))/((1-x^(k+1))*prod(j=1, k-1, 1 - x^j, 1 + O(x^(n-2*k+2)))), O(x*x^n)), -(n+1))} \\ _Andrew Howroyd_, Jan 17 2024

%Y The Heinz numbers of these partitions are given by A335448.

%Y Strict partitions are counted by A000009 and are all separable.

%Y Anti-run compositions are counted by A003242.

%Y Anti-run patterns are counted by A005649.

%Y Partitions whose differences are an anti-run are A238424.

%Y Separable partitions are counted by A325534.

%Y Anti-run compositions are ranked by A333489.

%Y Anti-run permutations of prime indices are counted by A335452.

%Y Cf. A000041, A106356, A238594, A261962, A292884, A332668, A333175.

%K nonn,easy

%O 0,5

%A _Clark Kimberling_, May 08 2019

%E a(0)=0 prepended by _Andrew Howroyd_, Jan 31 2024