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

Author

Gus Wiseman, Mar 28 2019

Keywords

• nonn

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.

Examples

			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)
		

Links

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

Crossrefs

Cf. A019565, A247935, A267610, A267700.

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

Programs

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

Extensions

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