

A005019


The number of n X n (0,1)matrices with a 1width 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 1widths of (0, 1)matrices. Discrete Math. 20 (1977/78), no. 2, 109122.
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 (1width 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



