|
|
A325109
|
|
Number of integer partitions of n whose distinct parts have no binary containments.
|
|
13
|
|
|
1, 1, 2, 3, 4, 5, 8, 10, 12, 15, 18, 23, 28, 32, 41, 52, 57, 66, 76, 90, 99, 117, 131, 157, 172, 194, 216, 255, 276, 313, 358, 410, 447, 511, 546, 630, 677, 750, 818, 945, 990, 1108, 1200, 1338, 1429, 1606, 1713, 1928, 2062, 2263, 2412, 2725, 2847, 3142, 3389
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(8) = 12 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (21) (22) (41) (33) (43) (44)
(111) (211) (221) (42) (52) (53)
(1111) (2111) (222) (61) (422)
(11111) (411) (421) (611)
(2211) (2221) (2222)
(21111) (4111) (4211)
(111111) (22111) (22211)
(211111) (41111)
(1111111) (221111)
(2111111)
(11111111)
|
|
MAPLE
|
c:= proc() option remember; local i, x, y;
x, y:= map(n-> Bits[Split](n), [args])[];
for i to nops(x) do
if x[i]=1 and y[i]=0 then return false fi
od; true
end:
b:= proc(n, i, s) option remember; `if`(n=0, 1, `if`(i<1, 0,
b(n, i-1, s)+`if`(ormap(j-> c(i, j), s), 0, add(
b(n-i*j, i-1, s union {i}), j=1..n/i))))
end:
a:= n-> b(n$2, {}):
|
|
MATHEMATICA
|
binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Table[Length[Select[IntegerPartitions[n], stableQ[#, SubsetQ[binpos[#1], binpos[#2]]&]&]], {n, 0, 15}]
(* Second program: *)
c[args_List] := c[args] = Module[{i, x, y}, {x, y} = Reverse@IntegerDigits[#, 2]& /@ args; For[i = 1, i <= Length[x], i++, If[x[[i]] == 1 && y[[i]] == 0, Return[False]]]; True];
b[n_, i_, s_List] := b[n, i, s] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1, s] + If[AnyTrue[s, c[{i, #}]&], 0, Sum[b[n - i*j, i-1, s ~Union~ {i}], {j, 1, n/i}]]]];
a[n_] := b[n, n, {}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|