1,2

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

Indeed, there are 2^n-1 possible nonzero rows of length n, so there are (2^n-1)^n possible n X n (0,1)-matrices with all rows nonzero. The difference with 2^n^2, the total number of (0,1)-matrices of size n X n, is the number of (0,1)-matrices with at least one row of zeros. - M. F. Hasler, Jan 18 2026

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

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

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

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

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

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

(PARI) apply( {A005019(n)=2^n^2-(2^n-1)^n}, [1..13]) \\ M. F. Hasler, Jan 18 2026

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

nonn,easy

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

approved