login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058347 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. 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, 94470, 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) (2-2^(-min(n,k))) <= T(n,k)/2^(n*k) if n > 0 and k > 0.

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

REFERENCES

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

LINKS

Table of n, a(n) for n=0..51.

FORMULA

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

EXAMPLE

{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^((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]]]]

CROSSREFS

Cf. A058547.

Sequence in context: A028698 A013667 A091933 * A058547 A230910 A215122

Adjacent sequences:  A058344 A058345 A058346 * A058348 A058349 A058350

KEYWORD

nonn,tabl,easy

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 08:00 EDT 2019. Contains 328315 sequences. (Running on oeis4.)