A014235 Number of n X n matrices with entries 0 and 1 and no 2 X 2 submatrix of form [ 1 1; 1 0 ].

1, 2, 12, 128, 2100, 48032, 1444212, 54763088, 2540607060, 140893490432, 9170099291892, 690117597121328, 59318536757456340, 5763381455631211232, 627402010180980401652, 75942075645205885599248, 10153054354133705795859540, 1490544499134409408040599232

Offset

0,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See p. 24.

Wenyi Feng, "counting the number of matrix", sci.math article, Feb. 5, 1997.

Robert Israel, "Re: counting the number of matrix", sci.math article, Feb. 5, 1997.

Hyeong-Kwan Ju and Seunghyun Seo, Enumeration of 0/1-matrices avoiding some 2x2 matrices, arXiv:1107.1299 [math.CO], 2011.

Hyeong-Kwan Ju and Seunghyun Seo, Enumeration of (0,1)-matrices avoiding some 2 X 2 matrices, Discrete Math., 312 (2012), 2473-2481.

Susanna E. Rumsey, Stark C. Draper, and Frank R. Kschischang, Information Density in Multi-Layer Resistive Memories, IEEE Transactions on Information Theory (2020) Vol. 67, Issue 3, 1446-1460.

Formula

a(n) = Sum_{k=0..n} k! * Stirling2(n+1, k+1)^2.

Example

For n = 2 the 12 matrices are all the 2 X 2 0-1 matrices except
[1 1]  [1 0]  [0 1]  [1 1]
[1 0], [1 1], [1 1], [0 1]. - Robert Israel, Feb 19 2015

Maple

f:= n -> add(k!*combinat:-stirling2(n+1, k+1)^2, k = 0 .. n):
seq(f(n), n=0..30); # Robert Israel, Feb 19 2015

Mathematica

Table[Sum[StirlingS2[n+1, k+1]^2k!, {k, 0, n}], {n, 0, 100}] (* Emanuele Munarini, Jul 04 2011 *)

Prog

(Maxima) makelist(sum(stirling2(n+1, k+1)^2*k!, k, 0, n), n, 0, 24); /* Emanuele Munarini, Jul 04 2011 */
(PARI) a(n) = sum(k=0, n, k! * stirling(n+1, k+1, 2)^2); \\ Michel Marcus, Feb 21 2015

Crossrefs

Cf. A023997, A048163, A111420, A213977.

Row sums of A334689.

Sequence in context: A228608 A097629 A259267 * A098628 A123553 A354493

Adjacent sequences: A014232 A014233 A014234 * A014236 A014237 A014238

Keyword

nonn

Author

Robert Israel

Extensions

a(0)=1 added by Emanuele Munarini, Jul 04 2011

Status

approved