

A058347


Array T(n,k), n,k nonnegative: the total number of checks required by a "doublesupport" algorithm to find out which rows and columns of each of the n by k zeroone matrices are nonzero.


1



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, 1566, 160, 0, 0, 384, 7742, 30502, 30502, 7742, 384, 0, 0, 896, 36990, 294470, 565110, 294470, 36990, 896, 0, 0, 2048, 172286, 2784390, 10482454, 10482454, 2784390
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

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.
Conjecture: T(n,k) = T(k,n).
max(n,k) (22^(min(n,k))) <= T(n,k)/2^(n*k) if n > 0 and k > 0.
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.


LINKS



FORMULA

T(0, k) = 0, T(n, 0) = 0, T(n, k) = (2^(k+1)  2)2^((n1) k) + 2^((n1)(k1))((k2)2^(k)+2) + (n1)(2^(k)  1)2^((n2)k + 1) + T(n1, k) + 2^(n1)(2^(k)1) T(n1, k1), if n > 0 and k > 0


EXAMPLE

Triangle begins:
{0};
{0,0};
{0,2,0};
{0,8,8,0};
{0,24,54,24,0};
...


MATHEMATICA

T[n_, 0] := 0 T[0, n_] := 0 T[n_, k_] := ( (2^(k+1)  2)2^((n1) k) + 2^((n1)(k1))((k2)2^(k)+2) + (n1)(2^(k)  1)2^((n2)k + 1) + T[n1, k] + 2^(n1)(2^(k)1) T[n1, k1]) For[c=0, c<=10, c++, For[n=0, n<=c, n++, Print[T[n, cn]]]]


CROSSREFS



KEYWORD



AUTHOR

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


EXTENSIONS



STATUS

approved



