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,5

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)

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

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)

Example

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}

Mathematica

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

Prog

(PARI) a(n)=if(n>1, ([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; -4, 0, 4, 0]^(n-2)*[1; 1; 3; 3])[1, 1], 0) \\ Charles R Greathouse IV, Apr 09 2026

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.

Sequence in context: A138135 A113166 A126872 * A094966 A095068 A248696

Adjacent sequences: A336099 A336100 A336101 * A336103 A336104 A336105

Keyword

nonn,easy

Author

Gus Wiseman, Jul 08 2020

Status

approved