login
The OEIS is supported by the many generous donors to the OEIS 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
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
KEYWORD
nonn
AUTHOR
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:05 EDT 2024. Contains 370952 sequences. (Running on oeis4.)