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.

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

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

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

M. R. C. van Dongen, A Theoretical Analysis of Domain-Heuristics for Arc-Consistency Algorithms, Technical Report: TR0004, CS Dept, UCC, College Road, Cork, Ireland.

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

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

Extensions

a(39) corrected by Sean A. Irvine, Aug 04 2022

Status

approved