A306297 Number T(n,k) of subsets of [n] with k binary carry-connected components; triangle T(n,k), n >= 0, 0 <= k <= A029837(n+1), read by rows.

1, 1, 1, 1, 2, 1, 1, 6, 1, 1, 7, 7, 1, 1, 19, 11, 1, 1, 47, 15, 1, 1, 111, 15, 1, 1, 112, 126, 16, 1, 1, 324, 166, 20, 1, 1, 776, 222, 24, 1, 1, 1736, 286, 24, 1, 1, 3708, 358, 28, 1, 1, 7740, 422, 28, 1, 1, 15868, 486, 28, 1, 1, 32252, 486, 28, 1, 1, 32253, 32738, 514, 29, 1

Offset: 0

Author

Alois P. Heinz, Mar 31 2019

Keywords

• nonn
• look
• tabf

Comments

Two integers are binary carry-connected if their bitwise AND is not zero.

T(n,k) is defined for all n,k >= 0. The triangle contains only the positive terms. T(n,k) = 0 if k > A029837(n+1).

Examples

			T(4,0) = 1: {}.
T(4,1) = 7: 1, 2, 3, 13, 23, 123, 4.
T(4,2) = 7: 1|2, 1|4, 2|4, 3|4, 13|4, 23|4, 123|4.
T(4,3) = 1: 1|2|4.
(The connected components are shown as blocks of a set partition.)
Triangle T(n,k) begins:
  1;
  1,    1;
  1,    2,   1;
  1,    6,   1;
  1,    7,   7,  1;
  1,   19,  11,  1;
  1,   47,  15,  1;
  1,  111,  15,  1;
  1,  112, 126, 16, 1;
  1,  324, 166, 20, 1;
  1,  776, 222, 24, 1;
  1, 1736, 286, 24, 1;
  1, 3708, 358, 28, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..1023
• Wikipedia, Bitwise operation
• Wikipedia, Partition of a set

Crossrefs

Columns k=0-1 give: A000007, -1 + A325105.

Row sums give A000079.

Number of terms in row n gives A070941.

Cf. A029837, A325105.

Programs

Maple

h:= proc(n, s) local i, m; m:= n;
      for i in s do m:= Bits[Or](m, i) od; {m}
    end:
g:= (n, s)-> (w-> `if`(w={}, s union {n}, s minus w union
              h(n, w)))(select(x-> Bits[And](n, x)>0, s)):
b:= proc(n, s) option remember; `if`(n=0, x^nops(s),
      b(n-1, s)+b(n-1, g(n, s)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
seq(T(n), n=0..23);

Mathematica

h[n_, s_List] := Module[{i, m = n}, For[i = 1, i <= Length[s], i++, m = BitOr[m, s[[i]]]]; m];
g[n_, s_List] := Function[w, If[w == {}, s ~Union~ {n}, s ~Complement~ w  ~Union~ {h[n, w]}]][Select[s, BitAnd[n, #] > 0&]];
b[n_, s_List] := b[n, s] = If[n == 0, x^Length[s], b[n - 1, s] + b[n - 1, g[n, s]]];
T[n_] := CoefficientList[b[n, {}], x];
T /@ Range[0, 23] // Flatten (* Jean-François Alcover, Apr 18 2021, after Alois P. Heinz *)

Formula

T(n,0) + T(n,1) = A325105(n).

T(n,A029837(n+1)) = 1.