A336102 Number of inseparable multisets of size n covering an initial interval of positive integers.

0, 0, 1, 1, 3, 3, 8, 8, 20, 20, 48, 48, 112, 112, 256, 256, 576, 576, 1280, 1280, 2816, 2816, 6144, 6144, 13312, 13312, 28672, 28672, 61440, 61440, 131072, 131072, 278528, 278528, 589824, 589824, 1245184, 1245184, 2621440, 2621440, 5505024, 5505024, 11534336

Offset: 0

Author

Gus Wiseman, Jul 08 2020

Keywords

• nonn

Comments

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one.

Also the number of compositions of n whose greatest part is greater than the sum of its remaining parts plus one. For example, the a(2) = 1 through a(7) = 8 compositions are:

(2) (3) (4) (5) (6) (7)

(1,3) (1,4) (1,5) (1,6)

(3,1) (4,1) (2,4) (2,5)

(4,2) (5,2)

(5,1) (6,1)

(1,1,4) (1,1,5)

(1,4,1) (1,5,1)

(4,1,1) (5,1,1)

Examples

			The a(2) = 1 through a(7) = 8 multisets:
  {11}  {111}  {1111}  {11111}  {111111}  {1111111}
               {1112}  {11112}  {111112}  {1111112}
               {1222}  {12222}  {111122}  {1111122}
                                {111123}  {1111123}
                                {112222}  {1122222}
                                {122222}  {1222222}
                                {122223}  {1222223}
                                {123333}  {1233333}
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..6625
• Index entries for linear recurrences with constant coefficients, signature (0,4,0,-4).

Crossrefs

The strong (weakly decreasing multiplicities) case is A025065.

The bisection is A049610.

The separable version is A336103.

Sequences covering an initial interval are A000670.

Anti-run compositions are A003242.

Anti-run patterns are A005649.

Separable partitions are A325534.

Inseparable partitions are A325535.

Inseparable factorizations are A333487.

Anti-run compositions are ranked by A333489.

Heinz numbers of inseparable partitions are A335448.

Cf. A001792, A019472, A052841, A106351, A124767, A269134, A292884, A335433, A335126, A335452, A335548.

Programs

Mathematica

Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],With[{mx=Max@@#},mx>1+Total[DeleteCases[#,mx,{1},1]]]&]],{n,0,15}]
(* Second program: *)
CoefficientList[Series[x^2*(1 - x) (x + 1)^2/(2 x^2 - 1)^2, {x, 0, 43}], x] (* Michael De Vlieger, Apr 07 2021 *)

Formula

a(2*n) = a(2*n + 1) = A049610(n + 1).

a(n) = 2^(n-1) - A336103(n).

A001792 repeated for n > 1. David A. Corneth, Jul 09 2020

From Chai Wah Wu, Apr 07 2021: (Start)

a(n) = 4*a(n-2) - 4*a(n-4) for n > 5.

G.f.: x^2*(1 - x)*(x + 1)^2/(2*x^2 - 1)^2. (End)