login
Lexicographical-support sequence T(n,k), n,k nonnegative: total number of checks required by a "lexicographical" algorithm to find out which rows and columns of each of the n by k zero-one matrices are nonzero.
1

%I #4 Feb 24 2006 03:00:00

%S 0,0,0,2,0,0,8,8,0,0,24,58,24,0,0,64,330,326,64,0,0,160,1706,3550,

%T 1666,160,0,0,384,8362,35662,35042,8102,384,0,0,896,39594,342830,

%U 686498,331790,38194,896,0,0,2048,182954,3201774,12962082,12725854,3064738,176150,2048,0,0,4608,830122,29284974,238899234,472874238,230983106,27831534,799042,4608,0

%N Lexicographical-support sequence T(n,k), n,k nonnegative: total number of checks required by a "lexicographical" 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.

%D M.R.C. van Dongen, Technical Report: TR0004, CS Dept, UCC, College Road, Cork, Ireland

%F T(0, k) = 0, T(n, 0) = 0, T(n, k) = 2^(n k)( n(2 - 2^(1-k)) + (1-k)2^(1-n) + 2 Sum^k_{c=2} (1-2^(-c))^(n))

%e {0}; {0,0}; {0,2,0}; {0,8,8,0}; {0,24,58,24,0}; ...

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

%Y Cf. A058347.

%K nonn,tabl,easy

%O 0,4

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