A111420 -id:A111420 - cp's OEIS frontend

A023997 Number of block permutations on an n-set.

1, 1, 3, 25, 339, 6721, 179643, 6166105, 262308819, 13471274401, 818288740923, 57836113793305, 4693153430067699, 432360767273547841, 44794795522199781243, 5176959027946049635225, 662704551840482536170579

Offset: 0

Des FitzGerald (D.FitzGerald(AT)utas.edu.au)

A block permutation of a set X is a bijection between two quotient sets of X (of necessarily equal rank).

Number of labeled partitions of (n,n) into pairs (i,j) where there are n black objects labeled 1..n and n white objects labeled 1..n. Each partition must have at least one black object and at least one white object. - Christian G. Bower, Jun 03 2005

			For n=3, there are the 3! ordinary permutations (of rank 3), 18 block permutations of rank 2 (2! for each pair of partitions of rank 2) and the single rank 1 one.

Vaclav Kotesovec, Table of n, a(n) for n = 0..288 (terms 0..45 from Vincenzo Librandi)
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. 22.
D. G. FitzGerald and Jonathan Leech, Dual symmetric inverse monoids and representation theory, J. Australian Mathematical Society (Series A), Vol. 64 (1998), pp. 345-367.

Cf. A023998, A002720, A014235, A111420.

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

makelist(sum(stirling2(n,k)^2*k!,k,0,n),n,0,24); /* Emanuele Munarini, Jul 04 2011 */

a(n) = if (n==0, 1, sum(k=1, n, k!*stirling(n, k, 2)^2)); \\ Michel Marcus, Jun 18 2019

a(0)=1, a(n) = Sum_{k=1..n} k! * S2(n,k)^2, S2(n,k) are the Stirling numbers of the second kind.

More terms from Christian G. Bower, Jun 03 2005

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

Original entry on oeis.org

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

Offset: 0

Robert Israel

nonn

			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

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.

Cf. A023997, A048163, A111420, A213977.

Row sums of A334689.

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

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

makelist(sum(stirling2(n+1, k+1)^2*k!, k, 0, n), n, 0, 24); /* Emanuele Munarini, Jul 04 2011 */

a(n) = sum(k=0, n, k! * stirling(n+1, k+1, 2)^2); \\ Michel Marcus, Feb 21 2015

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

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

A139784 a(4n+1)=2a(4n), a(4n+2)=2a(4n+1), a(4n+3)=2a(4n+2), a(4n+4)=2a(4n+3)+A007583(n).

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 4, 8, 19, 38, 76, 152, 315, 630, 1260, 2520, 5083, 10166, 20332, 40664, 81499, 162998, 325996, 651992, 1304667, 2609334, 5218668, 10437336, 20877403, 41754806, 83509612, 167019224, 334049371, 668098742, 1336197484, 2672394968

Offset: 0

Paul Curtz, May 16 2008

nonn

a(0), a(4), a(8) and a(12) are the first terms of A111420. - R. J. Mathar, May 18 2008

Index entries for linear recurrences with constant coefficients, signature (2, 0, 0, 5, -10, 0, 0, -4, 8).

Cf. a(0), a(4), a(8), a(12) in A111420.

LinearRecurrence[{2,0,0,5,-10,0,0,-4,8},{0,0,0,0,1,2,4,8,19},40] (* Harvey P. Dale, Jan 21 2013 *)

a(4n+s) = 2^s*(-1/45+7*16^n/90-4^n/18), s=0,1,2,3. - R. J. Mathar, May 18 2008

a(0)=0, a(1)=0, a(2)=0, a(3)=0, a(4)=1, a(5)=2, a(6)=4, a(7)=8, a(8)=19, a(n)=2*a(n-1)+5*a(n-4)-10*a(n-5)-4*a(n-8)+8*a(n-9). - Harvey P. Dale, Jan 21 2013

Edited and extended by R. J. Mathar, May 18 2008

cp's OEIS Frontend

A023997 Number of block permutations on an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A139784 a(4n+1)=2a(4n), a(4n+2)=2a(4n+1), a(4n+3)=2a(4n+2), a(4n+4)=2a(4n+3)+A007583(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions