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
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
KEYWORD
AUTHOR
Alois P. Heinz, Mar 31 2019
STATUS
approved