A005019 The number of n X n (0,1)-matrices with a 1-width of 1. (Formerly M4461)

1, 7, 169, 14911, 4925281, 6195974527, 30074093255809, 568640725896660991, 42170765737391337500161, 12325140160135610565932361727, 14244006984657003076298588475598849

Offset

1,2

Comments

a(n) is the number of ways to linearly order (with repetition allowed) n subsets of {1,2,...n} so that the generalized intersection of the subsets is not empty. - Geoffrey Critzer, Mar 01 2009

a(n) is the number of n X n binary matrices with at least one row of 0's. - Geoffrey Critzer, Dec 03 2009

References

Lam, Clement W. H., The distribution of 1-widths of (0, 1)-matrices. Discrete Math. 20 (1977/78), no. 2, 109-122.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Stanley, Enumerative Combinatorics, Volume I, Example 1.1.16 [From Geoffrey Critzer, Dec 03 2009]

Links

Table of n, a(n) for n=1..11.

Index entries for sequences related to binary matrices

Formula

a(n) = 2^(n^2) - ((2^n)-1)^n. - Geoffrey Critzer, Mar 01 2009

Example

a(2)=7 because there are seven ways to order two subsets of {1,2} so that the intersection of the subsets contains at least one element: {1}{1};{1}{1,2};{2}{2};{2}{1,2};{1,2}{1};{1,2}{2};{1,2}{1,2}. - Geoffrey Critzer, Mar 01 2009

Mathematica

Table[2^(n^2) - (2^n - 1)^n, {n, 1, 15}] (* Geoffrey Critzer, Dec 03 2009 *)

Crossrefs

a(n) = 2^(n^2)- A055601. - Geoffrey Critzer, Dec 03 2009

Cf. A005020 (1-width of 2).

Sequence in context: A012145 A368839 A351154 * A172027 A113562 A157203

Adjacent sequences: A005016 A005017 A005018 * A005020 A005021 A005022

Keyword

nonn

Author

N. J. A. Sloane

Extensions

a(7) from Geoffrey Critzer, Mar 01 2009

More terms from Geoffrey Critzer, Dec 03 2009

Title improved by Sean A. Irvine, Mar 06 2020

Status

approved