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