James Mitchell - cp's OEIS frontend

A371698 Number of partial order-preserving or -reversing transformations of a chain of length n.

2, 9, 54, 323, 1848, 10293, 56738, 312327, 1723692, 9549785, 53121654, 296593547, 1661423104, 9333552509, 52565738570, 296696569871, 1677887732820, 9505147063713, 53928737011358, 306393222740883, 1742919983985192, 9925790283119429, 56584658970159474, 322879453747840023

Offset: 1

James Mitchell, Apr 03 2024

nonn

V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus, Presentations for some monoids of partial transformations on a finite chain, Communications in Algebra, 33 (2005), 587-604, 2005.

Cf. A002003.

List([1..40], n -> 4 * Sum([0 .. n - 1], k ->  Binomial(n - 1, k) * Binomial(n + k, k)) - (1 + n * (2 ^ n - 1)));

a(n) = 4 * sum(k=0, n-1, binomial(n -1, k)*binomial(n + k, k)) - (1 + n * (2 ^ n - 1)); \\ Michel Marcus, Apr 03 2024

a(n) = 4*Sum_{k=0..n-1} binomial(n-1, k)*binomial(n+k, k) - (1 + n*(2 ^ n - 1)).

a(n) = 2*A002003(n) - (1 + n*(2^n - 1)).

A346686 Minimal number of generators of the monoid of n X n Boolean matrices.

Original entry on oeis.org

2, 3, 5, 7, 13, 68, 2142, 459153

Offset: 1

James Mitchell, Jul 29 2021

F. Hivert, J. D. Mitchell, F. L. Smith, and W. A. Wilson, Minimal generating sets for matrix monoids, arXiv:2012.10323 [math.RA], 2020, p. 7.
Tomáš Masopust and Petr Osička, On the Complexity of Initial-and-Final-State Opacity for Discrete Event Systems, arXiv:2402.17000 [cs.FL], 2024. See p. 4.
Tomáš Masopust and Petr Osička, On Algorithms verifying Initial-and-Final-State Opacity: Complexity, Special Cases, and Comparison, Palacky Univ. Olomouc (Czechia, 2024). See p. 3.
Yaroslav Shitov, Almost all boolean matrices are prime, ResearchGate (2024).

Cf. A346687.

A346687 Minimal number of generators of the monoid of n X n reflexive Boolean matrices.

Original entry on oeis.org

1, 2, 9, 39, 1415, 482430, 1034972230

Offset: 1

James Mitchell, Jul 29 2021

A Boolean matrix is reflexive if all entries on the main diagonal are 1.

F. Hivert, J. D. Mitchell, F. L. Smith, and W. A. Wilson, Minimal generating sets for matrix monoids, arXiv:2012.10323 [math.RA], 2020, p. 7.

Cf. A346686.

A290289 The number of maximal subsemigroups of the monoid of partial orientation-preserving and reversing injective mappings on the set [1..n].

Original entry on oeis.org

2, 2, 5, 4, 7, 7, 10, 4, 5, 9, 14, 7, 16, 11, 11, 5, 19, 7, 22, 9, 13, 16, 26, 7, 8, 17, 6, 11, 32, 12, 35, 4, 16, 22, 15, 8, 40, 23, 19, 10, 44, 14, 47, 15, 11, 28, 50, 7, 10, 9, 23, 18, 56, 7, 19, 12, 25, 34, 62, 12, 65, 35, 13, 5

Offset: 1

James Mitchell and Wilf A. Wilson, Jul 26 2017

nonn

Wilf A. Wilson, Table of n, a(n) for n = 1..1000
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017.

Cf. A001221, A008472.

a[1] = a[2] = 2; a[n_] := PrimeNu[n-1] + DivisorSum[n, Identity, PrimeQ]+1; Array[a, 64] (* Jean-François Alcover, Feb 18 2019 *)

a(n)= A001221(n -1) + A008472(n) + 1, n > 2.

A290140 The number of maximal subsemigroups of the Jones monoid on the set [1..n].

Original entry on oeis.org

1, 2, 5, 9, 13, 19, 27, 39, 57, 85, 129, 199, 311, 491, 781, 1249, 2005, 3227, 5203, 8399, 13569, 21933, 35465, 57359, 92783, 150099, 242837, 392889, 635677, 1028515, 1664139, 2692599, 4356681, 7049221, 11405841, 18454999, 29860775, 48315707, 78176413

Offset: 1

James Mitchell and Wilf A. Wilson, Jul 21 2017

a(2n) is the number of maximal subsemigroups of the planar partition monoid of degree n.

Wilf A. Wilson, Table of n, a(n) for n = 1..1000
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A000045.

{1, 2}~Join~Table[2 Fibonacci[n - 1] + 2 n - 3, {n, 3, 39}] (* Michael De Vlieger, Jul 21 2017 *)

Vec(x*(1 + x)*(1 - 2*x + 3*x^2 - 4*x^3 + x^4) / ((1 - x)^2*(1 - x - x^2)) + O(x^50)) \\ Colin Barker, Jul 21 2017

a(n) = 2 * A000045(n - 1) + 2n - 3, n > 2.
From Colin Barker, Jul 21 2017: (Start)
G.f.: x*(1 + x)*(1 - 2*x + 3*x^2 - 4*x^3 + x^4) / ((1 - x)^2*(1 - x - x^2)).
a(n) = -5 + (2^(-n)*((1-sqrt(5))^n*(1+sqrt(5)) + (-1+sqrt(5))*(1+sqrt(5))^n)) / sqrt(5) + 2*(1+n) for n>2.
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>6.
(End)

A290138 Number of maximal subgroups of the symmetric group S_n.

Original entry on oeis.org

0, 1, 4, 8, 22, 53, 184, 353, 1376, 3977, 363904, 396498, 39920896, 40060127, 1543910, 4687418, 1307674433536, 1307902407753, 355687428358144, 355691118382364, 162615882312376736, 1267150213999727, 51090942171713634304, 51090956256672365547

Offset: 1

James Mitchell and Wilf A. Wilson, Jul 21 2017

nonn

a(n) + 1, n > 1, is the number of maximal subsemigroups of each of the following monoids of degree n: the full transformation monoid, the symmetric inverse monoid, the dual symmetric inverse monoid, the uniform block bijection monoid, and the Brauer monoid.
a(n) + 2 is the number of maximal subsemigroups of the partial transformation monoid of degree n.
a(n) + 3, n > 1, is the number of maximal subsemigroups of the partial Brauer monoid of degree n.
a(n) + 4, n > 1, is the number of maximal subsemigroups of the partition monoid of degree n.

Wilf A. Wilson, Table of n, a(n) for n = 1..84
Utsithon Chaichompoo and Kritsada Sangkhanan, Transformation Semigroups Which Are Disjoint Union of Symmetric Groups, arXiv:2411.15081 [math.RA], 2024. See p. 10.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017.

Cf. A066115.

Sum(List(ConjugacyClassesMaximalSubgroups(SymmetricGroup(n)), Size));

A245686 Number of nonisomorphic synchronizing strongly connected binary n-state automata without output under input permutations.

Original entry on oeis.org

2, 21, 395, 10180, 322095, 12194323, 536197356, 26904958363, 1516697994964

Offset: 2

James Mitchell, Jul 29 2014

Number of 2-sets of transformations, up to conjugation, generating a transitive semigroup on n points that contains a constant transformation.

Jakub Kowalski and Marek Szykuła, The Černý conjecture for small automata: experimental report, arXiv:1301.2092 [cs.FL], January 2013.
James Mitchell, Semigroups data (contains links to files containing the 2-element sets of transformations on n points (up to conjugation) which generate a transitive semigroup containing a constant transformation).

A242432 Length of longest chain of nonempty proper subsemigroups of the monoid of partial injective orientation-preserving functions of a chain with n elements.

Original entry on oeis.org

1, 6, 24, 92, 363, 1483, 6191, 26077, 109987, 462900, 1941613, 8115138, 33805905, 140413073, 581694265, 2404314784, 9917782935, 40837958578, 167889571658, 689231516287, 2825851058202, 11572537702747, 47342211484912, 193485587828057, 790066214186999, 3223470297388819, 13141840760544209, 53540833421980514

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. A001222, A227914, A242428, A242429.

b[n_] := If[n < 1, 0, PrimeOmega[n]];
a[n_] := -2 - n + Sum[Binomial[n, i]*(b[i] + (Binomial[n, i] - 1)*i/2 + 2), {i, 0, n}];
Array[a, 28] (* Jean-François Alcover, Feb 19 2019, from PARI *)

b(n)=if(n<1, 0, bigomega(n)) /* A001222 */
a(n)=-2-n+sum(i=0, n, binomial(n,i)*(b(i)+(binomial(n,i)-1)*i/2+2))

A242429 Length of longest chain of nonempty proper subsemigroups of the monoid of partial injective order-preserving functions of a chain with n elements.

Original entry on oeis.org

1, 5, 17, 53, 167, 550, 1899, 6809, 25067, 93902, 355775, 1358208, 5212573, 20082860, 77607895, 300638481, 1166999699, 4537960846, 17673418311, 68924837252, 269132082925, 1052055773292, 4116727946687, 16123827007348, 63205353550497, 247959367137320, 973469914150619, 3824345703033374, 15033634055076857

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. A227914, A242428.

a[n_] := Binomial[2n, n]/2 + 3*2^(n-1) - n - 2; Array[a, 30] (* Jean-François Alcover, Dec 15 2018, from PARI *)

a(n)=-2-n+sum(i=0, n, binomial(n,i)*(binomial(n,i)+3)/2);

Conjecture: n*(131*n-376)*a(n) +2*(-563*n^2+1993*n-1185)*a(n-1) +3*(1099*n^2-4678*n+4684)*a(n-2) +2*(-1987*n^2+9803*n-12021)*a(n-3) +4*(209*n-387)*(2*n-7)*a(n-4)=0. - R. J. Mathar, Oct 20 2015

a(n) = binomial(2*n,n)/2 + 3*2^(n-1) - n - 2. - Gheorghe Coserea, May 16 2016

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

cp's OEIS Frontend

User: James Mitchell

A371698 Number of partial order-preserving or -reversing transformations of a chain of length n.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

PARI

Formula

A346686 Minimal number of generators of the monoid of n X n Boolean matrices.

Views

Author

Keywords

Links

Crossrefs

A346687 Minimal number of generators of the monoid of n X n reflexive Boolean matrices.

Views

Author

Keywords

Comments

Links

Crossrefs

A290289 The number of maximal subsemigroups of the monoid of partial orientation-preserving and reversing injective mappings on the set [1..n].

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A290140 The number of maximal subsemigroups of the Jones monoid on the set [1..n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A290138 Number of maximal subgroups of the symmetric group S_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

A245686 Number of nonisomorphic synchronizing strongly connected binary n-state automata without output under input permutations.

Views

Author

Keywords

Comments

Links

A242432 Length of longest chain of nonempty proper subsemigroups of the monoid of partial injective orientation-preserving functions of a chain with n elements.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A242429 Length of longest chain of nonempty proper subsemigroups of the monoid of partial injective order-preserving functions of a chain with n elements.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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