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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058547 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
0, 0, 0, 2, 0, 0, 8, 8, 0, 0, 24, 58, 24, 0, 0, 64, 330, 326, 64, 0, 0, 160, 1706, 3550, 1666, 160, 0, 0, 384, 8362, 35662, 35042, 8102, 384, 0, 0, 896, 39594, 342830, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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.

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..64.

FORMULA

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

EXAMPLE

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

MATHEMATICA

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

CROSSREFS

Cf. A058347.

Sequence in context: A013667 A091933 A058347 * A230910 A215122 A235789

Adjacent sequences:  A058544 A058545 A058546 * A058548 A058549 A058550

KEYWORD

nonn,tabl,easy

AUTHOR

M.R.C. van Dongen (dongen(AT)cs.ucc.ie), Dec 24 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 July 24 04:08 EDT 2019. Contains 325290 sequences. (Running on oeis4.)