A023997 -id:A023997 - cp's OEIS frontend

A023998 Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.

1, 1, 3, 16, 131, 1496, 22482, 426833, 9934563, 277006192, 9085194458, 345322038293, 15024619744202, 740552967629021, 40984758230303149, 2527342803112928081, 172490568947825135203, 12952575262915522547136, 1064521056888312620947794, 95305764621957309071404877

Offset: 0

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

Number of games of simple patience with n cards. Take a shuffled deck of n cards labeled 1..n; as each card is dealt it is placed either on a higher-numbered card or starts a new pile to the right. Cards are not moved once they are placed. Suggested by reading Aldous and Diaconis. - N. J. A. Sloane, Dec 19 1999

Number of set partitions of [2n] such that within each block the numbers of odd and even elements are equal. a(2) = 3: 1234, 12|34, 14|23; a(3) = 16: 123456, 1234|56, 1236|45, 1245|36, 1256|34, 12|3456, 12|34|56, 12|36|45, 1346|25, 1456|23, 14|2356, 14|23|56, 16|2345, 16|23|45, 14|25|36, 16|25|34. - Alois P. Heinz, Jul 14 2016

			For n=3 there are 25 block permutations, of which 9 of the form ({1} maps to {1,2}; {2,3} maps to {3}), are not uniform. Hence a(3) = 25 - 9 = 16.
Alternatively, for n=3 the 6 permutations of 3 cards produce 16 games, as follows: 123 -> {1,2,3}; 132 -> {1,32}, {1,3,2}; 213 -> {21,3}, {2,1,3}; 231 -> {21,3}, {2,31}, {2,3,1}; 312 -> {31,2}, {32,1}, {3,1,2}; 321 -> {321}, {32,1}, {31,2}, {3,21}, {3,2,1}.
G.f.: A(x) = 1 + x + 3*x^2/2!^2 + 16*x^3/3!^2 + 131*x^4/4!^2 + 1496*x^5/5!^2 + ...
log(A(x)) = x + x^2/2!^2 + x^3/3!^2 + x^4/4!^2 + x^5/5!^2 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..300
M. Aguiar and R. C. Orellana, The Hopf algebra of uniform block permutations, J. Algebr. Comb. 28 (2008) 115-138
D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413-432.
H. Cheballah, S. Giraudo, and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
Fabian Faulstich, Bernd Sturmfels, and Svala Sverrisdóttir, Algebraic Varieties in Quantum Chemistry, arXiv:2308.05258 [math.AG], 2023.
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.
Raúl E. González-Torres, A geometric study of cores of idempotent stochastic matrices, Linear Algebra Appl. 527, 87-127 (2017).
Rosa Orellana, Franco Saliola, Anne Schilling, and Mike Zabrocki, The lattice of submonoids of the uniform block permutations containing the symmetric group, arXiv:2405.09710 [math.CO], 2024. See p. 3.
Sebastian Volz, Design and Implementation of Efficient Algorithms for Operations on Partitions of Sets, Bachelor Thesis, Saarland Univ. (Germany, 2023). See p. 45.

Cf. A023997, A002720, A061691.
Cf. A132813.
Column k=2 of A275043.
Main diagonal of A321296 and of A322670.

a023998 n = a023998_list !! n
a023998_list = 1 : f 2 [1] a132813_tabl where
   f x ys (zs:zss) = y : f (x + 1) (ys ++ [y]) zss where
                     y = sum $ zipWith (*) ys zs
-- Reinhard Zumkeller, Apr 04 2014

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-i)*binomial(n-1, i-1)/i!, i=1..n))
    end:
a:= n-> b(n)*n!:
seq(a(n), n=0..25);  # Alois P. Heinz, May 11 2016

a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, k] Binomial[n-1, k] a[k], {k, 0, n-1}];
Array[a, 25, 0] (* Jean-François Alcover, Jul 28 2016 *)
nmax = 20; CoefficientList[Series[E^(-1 + BesselI[0, 2*Sqrt[x]]), {x, 0, nmax}], x]*Range[0, nmax]!^2 (* Vaclav Kotesovec, Jun 09 2019 *)

a(n)=if(n==0,1,sum(k=0,n-1,binomial(n,k)*binomial(n-1,k)*a(k))) \\ Paul D. Hanna, Aug 15 2007

{a(n)=n!^2*polcoeff(exp(sum(m=1, n, x^m/m!^2)+x*O(x^n)), n)} /* Paul D. Hanna */

N=66; x='x+O('x^N); /* that many terms */
Vec(serlaplace(serlaplace(exp(sum(n=1, N, x^n/n!^2))))) /* show terms */
/* Joerg Arndt, Jul 12 2011 */

v=vector(N); v[1]=1;
for (n=1,N-1, v[n+1]=sum(k=0,n-1, binomial(n,k)*binomial(n-1,k)*v[k+1]) );
v /* show terms */
/* Joerg Arndt, Jul 12 2011 */

a(n) = Sum_{k=0..n-1} C(n,k)*C(n-1,k)*a(k) for n>0 with a(0)=1. - Paul D. Hanna, Aug 15 2007
G.f.: Sum_{n>=0} a(n)*x^n/n!^2 = exp( Sum_{n>=1} x^n/n!^2 ). [Paul D. Hanna, Jan 04 2011; merged from duplicate entry A179119]
Row sums of A061691.
Generating function: Let J(z) = Sum_{n>=0} z^n/n!^2. Then exp(J(z)-1) = Sum_{n>=0} a(n)*z^n/n!^2 = 1 + z + 3*z^2/2!^2 + 16*z^3/3!^2 + .... - Peter Bala, Jul 11 2011

More terms from Vladeta Jovovic, Sep 03 2002

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

A227545 The number of idempotents in the Brauer monoid on [1..n].

Original entry on oeis.org

1, 1, 2, 10, 40, 296, 1936, 17872, 164480, 1820800, 21442816, 279255296, 3967316992, 59837670400, 988024924160, 17009993230336, 318566665977856, 6177885274406912, 129053377688043520, 2786107670662021120, 64136976817284448256, 1525720008470138454016, 38350749144768938770432

Offset: 0

James Mitchell, Jul 15 2013

nonn

The Brauer monoid is the set of partitions on [1..2n] with classes of size 2 and multiplication inherited from the partition monoid, which contains the Brauer monoid as a subsemigroup. The multiplication is defined in Halverson & Ram.
These numbers were produced using the Semigroups (2.0) package for GAP 4.7.
No general formula is known for the number of idempotents in the Brauer monoid.

I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, et al., Enumeration of idempotents in diagram semigroups and algebras, arXiv preprint arXiv:1408.2021 [math.GR], 2014.
T. Halverson, A. Ram, Partition algebras, European J. Combin. 26 (6) (2005) 869-921.

Cf. A023997, A225797, A277379.

for i in [1..11] do
  Print(NrIdempotents(BrauerMonoid(i)), "\n");
od;

nn = 44; ee = Table[0, nn+1]; ee[[1]] = 1;
e[n_] := e[n] = ee[[n+1]];
For[n = 1, n <= nn, n++, ee[[n+1]] = Sum[Binomial[n-1, 2i-1] (2i-1)! e[n-2i], {i, 1, n/2}] + Sum[Binomial[n-1, 2i] (2i+1)! e[n-2i-1], {i, 0, (n-1)/2}]
];
ee (* Jean-François Alcover, Jul 21 2018, after Joerg Arndt *)

N=44; E=vector(N+1); E[1]=1;
e(n)=E[n+1];
{ for (n=1, N,
E[n+1]=
     sum(i=1,n\2,binomial(n-1,2*i-1)*(2*i-1)!*e(n-2*i)) +
     sum(i=0,(n-1)\2,binomial(n-1,2*i)*(2*i+1)!*e(n-2*i-1))
); }
print(E);
\\ Joerg Arndt, Oct 12 2016

Terms a(13)-a(17) from James East, Dec 23 2013

More terms from Joerg Arndt, Oct 12 2016

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 *)

A242428 Length of longest chain of nonempty proper subsemigroups of the dual symmetric inverse monoid.

Original entry on oeis.org

0, 2, 17, 180, 3298, 88431, 3064050, 130905678, 6732227475, 409094032964, 28917250469178, 2346562701385648, 216180120430479731, 22397392442055209003, 2588479398843886168171, 331352273262513644199134, 46692196905193286953380160, 7203294536351261350956567853, 1210694223244114528129261255186

Offset: 1

James Mitchell, May 14 2014

nonn

James Mitchell, Table of n, a(n) for n = 1..100
P. J. Cameron, M. Gadouleau, J. D. Mitchell, Y. Peresse, Chains of subsemigroups, arXiv preprint arXiv:1501.06394 [math.GR], 2015.

Cf. A007238, A227914, A023997.

a[n_] := Sum[StirlingS2[n, i] (i! (StirlingS2[n, i] - 1)/2 - DigitCount[i, 2, 1] + Ceiling[3 i/2] + 1), {i, 1, n}] - n - 1;
Array[a, 19] (* Jean-François Alcover, Dec 12 2018, from PARI *)

b(n)=if(n<1, 0, b(n\2)+n%2) /* A000120 */
a(n)=-n-1+sum(i=1, n, stirling(n,i,flag=2)*(ceil(3*i/2)-b(i)+1+(stirling(n,i,flag=2)-1)*i!/2))

A108466 Number of factorizations of (n,n) into pairs (i,j) with i,j>1.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 11, 1, 3, 3, 9, 1, 11, 1, 11, 3, 3, 1, 35, 2, 3, 4, 11, 1, 25, 1, 20, 3, 3, 3, 55, 1, 3, 3, 35, 1, 25, 1, 11, 11, 3, 1, 106, 2, 11, 3, 11, 1, 35, 3, 35, 3, 3, 1, 132, 1, 3, 11, 45, 3, 25, 1, 11, 3, 25, 1, 222, 1, 3, 11, 11, 3, 25, 1, 106, 9, 3, 1, 132, 3, 3

Offset: 1

Christian G. Bower, Jun 03 2005

nonn

(a,b)*(x,y)=(a*x,b*y).

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1).

Cf. A108461. Main diagonal of A108465. a(A025487)=A108467. a(p^k)=A108469(k). a(A002110)=A023997.

A108470 Table read by antidiagonals: T(n,k) = number of labeled partitions of (n,k) into pairs (i,j).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 25, 15, 1, 1, 31, 79, 79, 31, 1, 1, 63, 241, 339, 241, 63, 1, 1, 127, 727, 1351, 1351, 727, 127, 1, 1, 255, 2185, 5235, 6721, 5235, 2185, 255, 1, 1, 511, 6559, 20119, 31831, 31831, 20119, 6559, 511, 1, 1, 1023, 19681, 77379

Offset: 1

Christian G. Bower, Jun 03 2005

Partitions of 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.

			1 1 1 1 1 ...
1 3 7 15 31 ...
1 7 25 79 241 ...
1 15 79 339 1351 ...
1 31 241 1351 6721 ...

Cf. A108461. Columns 1-3: A000012, A000225, A058481. Main diagonal: A023997.

T(n,k):=sum(m!*stirling2(k,m)*stirling2(n-k+1,m),m,1,min(k,n-k+1)); /* Vladimir Kruchinin, Apr 11 2015 */

antidiag(nn) = {for (n=1, nn, for (k=1, n, print1(sum(m=1, min(k, n-k+1), m!*stirling(k, m, 2)*stirling(n-k+1, m, 2)), ", "); ); print(););} \\ Michel Marcus, Apr 11 2015

tabl(nn) = {default(seriesprecision, nn); for (n=1, nn, for (k=1, nn, print1(k!*polcoeff(polcoeff(n!*exp((exp(x)-1)*(exp(y)-1))+O(x^(n+1)), n, x), k, y), ", "); ); print(););} \\ Michel Marcus, Apr 11 2015

Double e.g.f.: exp((exp(x)-1)*(exp(y)-1)).

T(n,k) = Sum{m=1..min(k,n-k+1)} m!*stirling2(k,m)*stirling2(n-k+1,m). - Vladimir Kruchinin, Apr 11 2015

cp's OEIS Frontend

A023998 Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

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

A227545 The number of idempotents in the Brauer monoid on [1..n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A242428 Length of longest chain of nonempty proper subsemigroups of the dual symmetric inverse monoid.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A108466 Number of factorizations of (n,n) into pairs (i,j) with i,j>1.

Views

Author

Keywords

Comments

Crossrefs

A108470 Table read by antidiagonals: T(n,k) = number of labeled partitions of (n,k) into pairs (i,j).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maxima

PARI

PARI

Formula