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}]
(* 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.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 08 2020
STATUS
approved