login
A336102
Number of inseparable multisets of size n covering an initial interval of positive integers.
7
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)
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}]
(* 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 *)
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.
Sequence in context: A138135 A113166 A126872 * A094966 A095068 A248696
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 08 2020
STATUS
approved