A014235 -id:A014235 - 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

A265417 Rectangular array T(n,m), read by upward antidiagonals: T(n,m) is the number of difunctional (regular) binary relations between an n-element set and an m-element set.

Original entry on oeis.org

2, 4, 4, 8, 12, 8, 16, 34, 34, 16, 32, 96, 128, 96, 32, 64, 274, 466, 466, 274, 64, 128, 792, 1688, 2100, 1688, 792, 128, 256, 2314, 6154, 9226, 9226, 6154, 2314, 256, 512, 6816, 22688, 40356, 48032, 40356, 22688, 6816, 512, 1024, 20194, 84706, 177466, 245554, 245554, 177466, 84706, 20194, 1024, 2048, 60072, 320168

Offset: 1

Jasha Gurevich, Dec 08 2015

T(n,m) is the number of difunctional (regular) binary relations between an n-element set and an m-element set.
From Petros Hadjicostas, Feb 09 2021: (Start)
From Knopfmacher and Mays (2001): "Let G be a labeled graph, with edge set E(G) and vertex set V(G). A composition of G is a partition of V(G) into vertex sets of connected induced subgraphs of G." "We will denote by C(G) the number of distinct compositions that exist for a given graph G."
By Theorem 10 in Knofmacher and Mays (2001), T(n,m) = C(K_{n,m}) = Sum_{i=1..n+1} A341287(n,i)*i^m, where K_{n,m} is the complete bipartite graph with n+m vertices and n*m edges. For values of T(n,m), see the table on p. 10 of the paper.
Huq (2007) reproved the result using different methodology and derived the bivariate e.g.f. of T(n,m). (End)

			Array T(n,m) (with rows n >= 1 and columns m >= 1) begins:
    2      4      8      16       32        64        128         256 ...
    4     12     34      96      274       792       2314        6816 ...
    8     34    128     466     1688      6154      22688       84706 ...
   16     96    466    2100     9226     40356     177466      788100 ...
   32    274   1688    9226    48032    245554    1251128     6402586 ...
   64    792   6154   40356   245554   1444212    8380114    48510036 ...
  128   2314  22688  177466  1251128   8380114   54763088   354298186 ...
  256   6816  84706  788100  6402586  48510036  354298186  2540607060 ...
  512  20194 320168 3541066 33044432 281910994 2288754728 18082589146 ...
  ...

Jasha Gurevich, Table of n, a(n) for n = 1..300
Chris Brink, Wolfram Kahl, and Gunther Schmidt, Relational Methods in Computer Science, Springer Science & Business Media, 1997, p. 200.
Jasha Gurevich, Full list of formulas for correspondences (binary relations).
Amiqul Huq, Compositions of graphs revisited, Vol. 14 (2007), Article N15.
A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumerations, Integers, Vol. 1 (2001), Article A4. (See p. 10 for the table and p. 8 for a formula.)
J. Riguet, Relations binaires, fermetures, correspondances de Galois, Bulletin de la Société Mathématique de France, Vol. 76 (1948), 114-155.
Wikipedia, Binary relation.

Cf. A005056 (1st line or column ?), A014235 (diagonal ?), A341287.

sum((Stirling2(m, i-1)*factorial(i)+Stirling2(m, i)*factorial(i+1)+Stirling2(m, i+1)*factorial(i+1))*Stirling2(n, i), i = 1 .. n)

T(n, m) = sum(i=1,n, (stirling(m, i-1,2)*i! + stirling(m, i,2)*(i+1)! + stirling(m, i+1,2)*(i+1)!)*stirling(n, i,2)); \\ Michel Marcus, Dec 10 2015

T(n, m) = Sum_{i=1..n} (Stirling2(m, i-1)*i! + Stirling2(m, i)*(i+1)! + Stirling2(m, i+1)*(i+1)!)*Stirling2(n, i).
From Petros Hadjicostas, Feb 09 2021: (Start)
T(n,m) = Sum_{i=1..n+1} A341287(n,i)*i^m = Sum_{i=1..m+1} A341287(m,i)*i^n. (See Knopfmacher and Mays (2001) and Huq (2007).)
Bivariate e.g.f.: Sum_{n,m >= 1} T(n,m)*(x^n/n!)*(y^m/m!) = exp((exp(x) - 1)*(exp(y) - 1) + x + y) - exp(x) - exp(y) + 1. (This is a modification of Eq. (7) in Huq (2007), p. 4.) (End)

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

Original entry on oeis.org

0, 1, 19, 315, 6601, 178923, 6161065, 262268499, 13470911521, 818285112123, 57836073876505, 4693152951066099, 432360761046527041, 44794795435021490043, 5176959026638375267225, 662704551819559746282579, 93384393940399990403502241, 14406589076081640590750974203

Offset: 0

N. J. A. Sloane, Nov 14 2005

nonn

Cf. A023997, A014235.

a:= n-> add(Stirling2(n+1,q)^2*q!, q=0..n):
seq(a(n), n=0..19);  # Alois P. Heinz, May 11 2020

Table[Sum[StirlingS2[n+1, k]^2 * k!, {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jul 12 2018 *)

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

Original entry on oeis.org

1, 2, 14, 200, 3536, 67472, 1423168, 34048352, 927156224, 28490354432, 976839578624, 36983803914752, 1532587515049984, 68997562105014272, 3353462146559209472, 175003916852177604608, 9760034505494167420928, 579311442062239341412352, 36462558160899681920745472, 2425761875540844266778656768

Offset: 0

N. J. A. Sloane, Jul 05 2012

nonn

Joerg Arndt, Table of n, a(n) for n = 0..100
Hyeong-Kwan Ju, Seunghyun Seo, Enumeration of 0/1-matrices avoiding some 2x2 matrices, arXiv:1107.1299 [math.CO], 2011.
H.-K. Ju and S. Seo, Enumeration of (0,1)-matrices avoiding some 2 X 2 matrices, Discrete Math., 312 (2012), 2473-2481.

Cf. A048163, A014235.

terms = 20; w = ProductLog[-x E^x]; CoefficientList[-2w/(x(w+1)) + (x^2-1) E^(2x) - 2x(x+1) E^(4x) + O[x]^terms, x]*Range[0, terms-1]! (* Jean-François Alcover, Jul 22 2018, after Joerg Arndt *)

N=66; x='x+O('x^N);
W(x)=sum(n=1,N, (-n)^(n-1)*x^n/n! );
w=W(-x*exp(x));
egf=-2*w/(x*(1+w)) + (x^2-1)*exp(2*x)-2*x*(x+1)*exp(4*x);
Vec(serlaplace(egf))
/* Joerg Arndt, Jul 19 2012 */

Ju and Seo give an e.g.f. (see PARI code).

More terms from Joerg Arndt, Jul 19 2012

A334689 Triangle read by rows: T(n,k) (0 <= k <= n) = k!(Stirling2(n,k)+(k+1)Stirling2(n,k+1))^2.

Original entry on oeis.org

1, 1, 1, 1, 9, 2, 1, 49, 72, 6, 1, 225, 1250, 600, 24, 1, 961, 16200, 25350, 5400, 120, 1, 3969, 181202, 735000, 470400, 52920, 720, 1, 16129, 1866312, 17360406, 26460000, 8490720, 564480, 5040, 1, 65025, 18301250, 362237400, 1159593624, 840157920, 153679680, 6531840, 40320

Offset: 0

N. J. A. Sloane, May 11 2020

This is the number of Boolean matrices of dimension n and rank k having a Moore-Penrose inverse (Kim-Roush, Th. 10).

Theorem 8 of the same Kim-Roush paper gives a formula for the number of Boolean matrices of dimension n and rank k having a minimum-norm g-inverse. Unfortunately the formula appears to produce negative numbers.

			Triangle begins:
1,
1, 1,
1, 9, 2,
1, 49, 72, 6,
1, 225, 1250, 600, 24,
1, 961, 16200, 25350, 5400, 120,
1, 3969, 181202, 735000, 470400, 52920, 720,
1, 16129, 1866312, 17360406, 26460000, 8490720, 564480, 5040,
...

Ki Hang Kim, and Fred W. Roush, Inverses of Boolean matrices, Linear Algebra and its Applications 22 (1978): 247-262. See Th. 10.

Columns k=0-2 give: A000012, A060867, 2*A129839(n+1).

Row sums give A014235.

T := (n,k) -> k!*(Stirling2(n,k)+(k+1)*Stirling2(n,k+1))^2;
r:=n->[seq(T(n,k),k=0..n)];
for n from 0 to 12 do lprint(r(n)); od:

A383255 Number of n X n {0,1,2,3} matrices having no 1's to the right of any 0's and no 3's above any 2's.

Original entry on oeis.org

1, 4, 194, 107080, 672498596, 48104236145168, 39202958861329453384, 364022757339778569993689888, 38513979937284562006371342202842000, 46429021191757554279412904483559912259714112, 637737721080296383894709847744103523361428384973270816

Offset: 0

John Tyler Rascoe, Apr 20 2025

nonn

These are matrices with no [0,1] or [3] submatrices.

[2]

			The 3 X 3 matrices below are counted under a(3) = 107080:
 [0,0,0] [1,0,2] [2,3,2]
 [0,0,0] [1,0,3] [3,3,3]
 [0,0,0],[0,2,3],[3,3,3].

John Tyler Rascoe, Python program.

Cf. A002416, A006506, A014235, A060757, A181213, A213977, A381857.

Python
```
# see links
```

a(n) <= A060757(n).

a(5)-a(10) from Bert Dobbelaere, Apr 23 2025

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

A265417 Rectangular array T(n,m), read by upward antidiagonals: T(n,m) is the number of difunctional (regular) binary relations between an n-element set and an m-element set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A334689 Triangle read by rows: T(n,k) (0 <= k <= n) = k!*(Stirling2(n,k)+(k+1)*Stirling2(n,k+1))^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A383255 Number of n X n {0,1,2,3} matrices having no 1's to the right of any 0's and no 3's above any 2's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A334689 Triangle read by rows: T(n,k) (0 <= k <= n) = k!(Stirling2(n,k)+(k+1)Stirling2(n,k+1))^2.