login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005019 The number of n X n (0,1)-matrices with a 1-width of 1.
(Formerly M4461)
0
1, 7, 169, 14911, 4925281, 6195974527, 30074093255809, 568640725896660991, 42170765737391337500161, 12325140160135610565932361727, 14244006984657003076298588475598849 (list; graph; refs; listen; history; text; internal format)
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: A258299 A012067 A012145 * 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

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 May 13 05:02 EDT 2021. Contains 343836 sequences. (Running on oeis4.)