A325109 Number of integer partitions of n whose distinct parts have no binary containments.

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

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

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..400, (terms up to a(200) from Alois P. Heinz)

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, {}):
seq(a(n), n=0..55);  # Alois P. Heinz, Mar 29 2019

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}]
(* Alternative: *)
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, {}];
a /@ Range[0, 55] (* Jean-François Alcover, Jun 03 2021, after Alois P. Heinz *)

Crossrefs

Cf. A019565, A247935, A267610, A267700.

Cf. A325098, A325101, A325106, A325107, A325108, A325110.

Sequence in context: A223539 A332520 A211544 * A080713 A058664 A238479

Adjacent sequences: A325106 A325107 A325108 * A325110 A325111 A325112

Keyword

nonn

Author

Gus Wiseman, Mar 28 2019

Extensions

a(31)-a(54) from Alois P. Heinz, Mar 29 2019

Status

approved