login
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.
2
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
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.
Sequence in context: A152656 A096162 A333144 * A053383 A181538 A322128
KEYWORD
nonn,look,tabf
AUTHOR
Alois P. Heinz, Mar 31 2019
STATUS
approved