login
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

%I #44 Apr 18 2021 09:04:48

%S 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,

%T 16,1,1,324,166,20,1,1,776,222,24,1,1,1736,286,24,1,1,3708,358,28,1,1,

%U 7740,422,28,1,1,15868,486,28,1,1,32252,486,28,1,1,32253,32738,514,29,1

%N 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.

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

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

%H Alois P. Heinz, <a href="/A306297/b306297.txt">Rows n = 0..1023</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Bitwise operation">Bitwise operation</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

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

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

%e T(4,0) = 1: {}.

%e T(4,1) = 7: 1, 2, 3, 13, 23, 123, 4.

%e T(4,2) = 7: 1|2, 1|4, 2|4, 3|4, 13|4, 23|4, 123|4.

%e T(4,3) = 1: 1|2|4.

%e (The connected components are shown as blocks of a set partition.)

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 6, 1;

%e 1, 7, 7, 1;

%e 1, 19, 11, 1;

%e 1, 47, 15, 1;

%e 1, 111, 15, 1;

%e 1, 112, 126, 16, 1;

%e 1, 324, 166, 20, 1;

%e 1, 776, 222, 24, 1;

%e 1, 1736, 286, 24, 1;

%e 1, 3708, 358, 28, 1;

%e ...

%p h:= proc(n, s) local i, m; m:= n;

%p for i in s do m:= Bits[Or](m, i) od; {m}

%p end:

%p g:= (n, s)-> (w-> `if`(w={}, s union {n}, s minus w union

%p h(n, w)))(select(x-> Bits[And](n, x)>0, s)):

%p b:= proc(n, s) option remember; `if`(n=0, x^nops(s),

%p b(n-1, s)+b(n-1, g(n, s)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):

%p seq(T(n), n=0..23);

%t h[n_, s_List] := Module[{i, m = n}, For[i = 1, i <= Length[s], i++, m = BitOr[m, s[[i]]]]; m];

%t g[n_, s_List] := Function[w, If[w == {}, s ~Union~ {n}, s ~Complement~ w ~Union~ {h[n, w]}]][Select[s, BitAnd[n, #] > 0&]];

%t b[n_, s_List] := b[n, s] = If[n == 0, x^Length[s], b[n - 1, s] + b[n - 1, g[n, s]]];

%t T[n_] := CoefficientList[b[n, {}], x];

%t T /@ Range[0, 23] // Flatten (* _Jean-François Alcover_, Apr 18 2021, after _Alois P. Heinz_ *)

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

%Y Row sums give A000079.

%Y Number of terms in row n gives A070941.

%Y Cf. A029837, A325105.

%K nonn,look,tabf

%O 0,5

%A _Alois P. Heinz_, Mar 31 2019