A058347 - OEIS

%I #12 Aug 04 2022 05:23:07

%S 0,0,0,0,2,0,0,8,8,0,0,24,54,24,0,0,64,302,302,64,0,0,160,1566,3094,

%T 1566,160,0,0,384,7742,30502,30502,7742,384,0,0,896,36990,294470,

%U 565110,294470,36990,896,0,0,2048,172286,2784390,10482454,10482454,2784390

%N Array T(n,k), n,k nonnegative: the total number of checks required by a "double-support" algorithm to find out which rows and columns of each of the n by k zero-one matrices are nonzero.

%C I.e., T(n,k) = Sum_{m in M(n,k)} checks(m), where M(n,k) contains all n by k matrices and checks(M) is the number of checks to find all nonzero rows and columns of m.

%C Conjecture: T(n,k) = T(k,n).

%C max(n,k) (2-2^(-min(n,k))) <= T(n,k)/2^(n*k) if n > 0 and k > 0.

%C T(n,k)/2^(n*k) <= 2*max(n,k)+2 -( min(n,k)+2*max(n,k))*2^(-min(n,k)) -(2*min(n,k)+3*max(n,k))*2^(-max(n,k)). The lower bound is a lower bound for any algorithm to carry out the same task.

%H M. R. C. van Dongen, <a href="http://csweb.ucc.ie/~dongen/papers/UCC/00/TR0004.pdf">A Theoretical Analysis of Domain-Heuristics for Arc-Consistency Algorithms</a>, Technical Report: TR0004, CS Dept, UCC, College Road, Cork, Ireland.

%F T(0, k) = 0, T(n, 0) = 0, T(n, k) = (2^(k+1) - 2)2^((n-1) k) + 2^((n-1)(k-1))((k-2)2^(k)+2) + (n-1)(2^(k) - 1)2^((n-2)k + 1) + T(n-1, k) + 2^(n-1)(2^(k)-1) T(n-1, k-1), if n > 0 and k > 0

%e Triangle begins:

%e   {0};

%e   {0,0};

%e   {0,2,0};

%e   {0,8,8,0};

%e   {0,24,54,24,0};

%e   ...

%t T[n_, 0] := 0 T[0, n_] := 0 T[n_, k_] := ( (2^(k+1) - 2)2^((n-1) k) + 2^((n-1)(k-1))((k-2)2^(k)+2) + (n-1)(2^(k) - 1)2^((n-2)k + 1) + T[n-1, k] + 2^(n-1)(2^(k)-1) T[n-1, k-1]) For[c=0, c<=10, c++, For[n=0, n<=c, n++, Print[T[n, c-n]]]]

%Y Cf. A058547.

%K nonn,tabl,easy

%O 0,5

%A M.R.C. van Dongen (dongen(AT)cs.ucc.ie), Dec 15 2000

%E a(39) corrected by _Sean A. Irvine_, Aug 04 2022