|
|
A247935
|
|
Number of integer partitions of n whose distinct parts have no binary carries.
|
|
19
|
|
|
1, 1, 2, 3, 4, 5, 8, 10, 11, 14, 18, 21, 26, 30, 38, 49, 47, 55, 66, 74, 84, 96, 110, 126, 134, 151, 171, 195, 209, 235, 272, 318, 307, 349, 377, 422, 448, 491, 534, 595, 617, 674, 734, 801, 841, 925, 998, 1098, 1118, 1219, 1299, 1418, 1476, 1591, 1711, 1865
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the reversed binary expansions of 2, 5, and 8 are
{0,1}
{1,0,1}
{0,0,0,1}
and since there are no columns with more than one 1, the partition (8,5,2) is counted under a(15). The Heinz numbers of these partitions are given by A325097.
(End)
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(8) = 11 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (21) (22) (41) (33) (43) (44)
(111) (211) (221) (42) (52) (422)
(1111) (2111) (222) (61) (611)
(11111) (411) (421) (2222)
(2211) (2221) (4211)
(21111) (4111) (22211)
(111111) (22111) (41111)
(211111) (221111)
(1111111) (2111111)
(11111111)
(End)
|
|
MAPLE
|
with(Bits):
b:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(i<1, 0,
b(n, i-1, t) +`if`(i>n or And(t, i)>0, 0,
add(b(n-i*j, i-1, Or(t, i)), j=1..n/i))))
end:
a:= n-> b(n$2, 0):
|
|
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[#, Intersection[binpos[#1], binpos[#2]]!={}&]&]], {n, 0, 20}] (* Gus Wiseman, Mar 30 2019 *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1, t] + If[i > n || BitAnd[t, i] > 0, 0, Sum[b[n - i*j, i - 1, BitOr[t, i]], {j, 1, n/i}]]]];
a[n_] := b[n, n, 0];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|