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,5

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).

Links

Alois P. Heinz, Rows n = 0..1023

Wikipedia, Bitwise operation

Wikipedia, Partition of a set

Formula

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

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

Example

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;
  ...

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 *)

Crossrefs

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

Row sums give A000079.

Number of terms in row n gives A070941.

Cf. A029837, A325105.

Sequence in context: A152656 A096162 A333144 * A053383 A181538 A322128

Adjacent sequences: A306294 A306295 A306296 * A306298 A306299 A306300

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Mar 31 2019

Status

approved