A280781 -id:A280781 - cp's OEIS frontend

A111111 Number of simple permutations of degree n.

1, 2, 0, 2, 6, 46, 338, 2926, 28146, 298526, 3454434, 43286526, 583835650, 8433987582, 129941213186, 2127349165822, 36889047574274, 675548628690430, 13030733384956418, 264111424634864638, 5612437196153963522, 124789500579376435198, 2897684052921851965442

Offset: 1

N. J. A. Sloane, Oct 14 2005

A permutation is simple if the only intervals that are mapped onto intervals are the singletons and [1..n].
For example, the permutation
  1234567
  2647513
is not simple since it maps [2..5] onto [4..7].
In other words, a permutation [1 ... n] -> [p_1 p_2 ... p_n] is simple if there is no string of consecutive numbers [i_1 ... i_k] which is mapped onto a string of consecutive numbers [p_i_1 ... p_i_k] except for the strings of length k = 1 or n.

			G.f. = x + 2*x^2 + 2*x^4 + 6*x^5 + 46*x^6 + 338*x^7 + 2926*x^8 + ...
The simple permutations of lowest degree are 1, 12, 21, 2413, 3142.

Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals of permutations. in Mathematics and Computer Science. III, 3--14, Trends Math., Birkhuser, Basel, 2004.
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
Bridget Eileen Tenner, Interval posets of permutations, arXiv:2007.06142, Aug 2021.

T. D. Noe, Table of n, a(n) for n = 1..100
M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discr. Math., 300 (2005), 1-15.
M. H. Albert, M. D. Atkinson and M. Klazar, The enumeration of simple permutations, Journal of Integer Sequences 6 (2003), Article 03.4.4, 18 pages.
Joerg Arndt, All simple permutations for n <= 6
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.
M. Bouvel, M. Mishna, and C. Nicaud, Some simple varieties of trees arising in permutation analysis, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 855-866.
Robert Brignall, Sophie Huczynska, and Vincent Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], (2006).
R. Brignall, S. Huczynska, and V. Vatter, Decomposing simple permutations with enumerative consequences, Combinatorica, 28 (2008) 384-400.
Robert Brignall, A Survey of Simple Permutations, arXiv:0801.0963 [math.CO], (18-April-2008)
Sylvie Corteel, Guy Louchard, and Robin Pemantle, Common intervals in permutations, Discrete Math. Theor. Comput. Sci. 8 (2006), no. 1, 189-216.
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
V. Jelínek and P. Valtr, Splittings and Ramsey Properties of Permutation Classes, arXiv preprint arXiv:1307.0027 [math.CO], 2013.
Djamila Oudrar, Sur l'énumération de structures discrètes, une approche par la théorie des relations, Thesis (in French), arXiv:1604.05839 [math.CO], 2016.
Djamila Oudrar and Maurice Pouzet, Profile and hereditary classes of ordered relational structures, arXiv preprint arXiv:1409.1108 [math.CO], 2014.
Djamila Oudrar, Maurice Pouzet, and Imed Zaguia, Minimal prime ages, words and permutation graphs Extended abstract, arXiv:2205.08992 [math.CO], 2022.

Cf. A059372, A280780.

nmax = 20; t[n_, k_] := t[n, k] = Sum[(m + 1)!*t[n - m - 1, k - 1], {m, 0, n - k}]; t[n_, 1] = n!; t[n_, n_] = 1; tnk = Table[t[n, k], {n, 1, nmax}, {k, 1, nmax}]; A111111 = -Inverse[tnk][[All, 1]] + 2*(-1)^Range[0, nmax - 1]; A111111[[2]] = 2;
A111111 (* Jean-François Alcover, Jul 13 2016 *)

simple(v)=for(i=1,#v-1, for(j=i+1,#v, my(u=vecsort(v[i..j]));if(u[#u]-u[1]==#u-1 && #u<#v, return(0)))); 1
a(n)=sum(i=0,n!-1, simple(numtoperm(n,i))) \\ Charles R Greathouse IV, Nov 05 2013
seq(N) = Vec(2 + 2*x^2 - 2/(1+x) - serreverse(x*Ser(vector(N, n, n!))));  \\ Gheorghe Coserea, Jan 22 2017

a(n) = -A059372(n)+2(-1)^(n+1).
a(n) ~ n!*(1-4/n)/e^2. - Jon E. Schoenfield, Aug 05 2006
a(n) ~ n!*exp(-2)*(1 - 4/n + 2/(n*(n-1)) - (40/3)/(n*(n-1)*(n-2)) - ...). Coefficients are given by A280780(n)/A280781(n).- Gheorghe Coserea, Jan 23 2017

Incorrect statement removed by Jay Pantone, Jul 16 2014

Word "fixed" removed by Franklin T. Adams-Watters, Jul 22 2014

A280780 Numerators of coefficients in asymptotic expansion of S_n (number of simple permutations, A111111).

Original entry on oeis.org

1, -4, 2, -40, -182, -7624, -202652, -14115088, -30800534, -16435427656, -1051314228316, -22675483971248, -6980651581556876, -283099764343781072, -163910651754113166328, -43009695328217994139936, -793529010007812171331166, -20144221762701827321778088, -274475989492312981198559876

Offset: 0

N. J. A. Sloane, Jan 19 2017

			Coefficients are 1, -4, 2, -40/3, -182/3, -7624/15, -202652/45, -14115088/315, -30800534/63, -16435427656/2835, ...

Gheorghe Coserea, Table of n, a(n) for n = 0..100
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.

Cf. A000699, A280775, A111111, A280777, A280778, A280779, A280781.

seq(N) = {
  my(f = serreverse(x*Ser(vector(N, n, n!))));
  Vec(x* f'/f * exp(2 + (f-x)/(x*f)));
};
apply(numerator, seq(20))  \\ Gheorghe Coserea, Jan 22 2017

A111111(n) ~ n!*exp(-2)*(1 - 4/n + 2/(n*(n-1)) - (40/3)/(n*(n-1)*(n-2)) - ...). - Gheorghe Coserea, Jan 23 2017

More terms from Gheorghe Coserea, Jan 22 2017

A280777 Denominators of coefficients in asymptotic expansion of C_n (number of connected chord diagrams, A000699).

Original entry on oeis.org

1, 2, 8, 16, 128, 1280, 3072, 215040, 3440640, 2293760, 137625600, 201850880, 72666316800, 1889324236800, 52901078630400, 176336928768000, 135426761293824, 191854578499584000, 1593868805996544000, 787371190162292736000, 31494847606491709440000, 29395191099392262144000

Offset: 0

N. J. A. Sloane, Jan 19 2017

			Coefficients are 1, -5/2, -43/8, -579/16, -44477/128, -5326191/1280, -180306541/3072, ...

Gheorghe Coserea, Table of n, a(n) for n = 0..101
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.

Cf. A000699, A280775, A111111, A280776, A280778, A280779, A280780, A280781.

A000699_seq(N) = {
  my(a = vector(N)); a[1] = 1;
  for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(N) = my(C = 'x*Ser(A000699_seq(N))); Vec(x*exp(1-(2*C+C^2)/(2*x))/C);
apply(denominator, seq(22)) \\ Gheorghe Coserea, Jan 22 2017

More terms from Gheorghe Coserea, Jan 22 2017

A280778 Numerators of coefficients in asymptotic expansion of M_n (number of monolithic chord diagrams, A280775).

Original entry on oeis.org

1, -4, -6, -154, -1610, -34588, -4666292, -553625626, -1158735422, -388434091184, -31268175015478, -2796356409576766, -4624948938397276052, -1691272281281652408568, -2154089954877183990112, -170222948041126582837968646, -5761785676811885455064909606, -55629298859254851627617870836

Offset: 0

N. J. A. Sloane, Jan 19 2017

			Coefficients are 1, -4, -6, -154/3, -1610/3, -34588/5, -4666292/45, -553625626/315, -1158735422/35, ...

Gheorghe Coserea, Table of n, a(n) for n = 0..101
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.

Cf. A000699, A280775, A111111, A280777, A280779, A280780, A280781.

A000699_seq(N) = {
  my(a = vector(N)); a[1] = 1;
  for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(N) = {
  my(M = subst(x*Ser(A000699_seq(N)), x, x/(1-x)^2));
  Vec(x/(1-x)*exp(1-x/2-(1-x)^2/(2*x)*(2*M + M^2))/M);
};
apply(numerator, seq(18))  \\ Gheorghe Coserea, Jan 22 2017

More terms from Gheorghe Coserea, Jan 22 2017

A280779 Denominators of coefficients in asymptotic expansion of M_n (number of monolithic chord diagrams, A280775).

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 45, 315, 35, 567, 2025, 7425, 467775, 6081075, 257985, 638512875, 638512875, 172297125, 13956067125, 74246277105, 3093594879375, 14992036723125, 2143861251406875, 16436269594119375, 4226469324202125, 48028060502296875, 593531957565421875, 56437147443285984375

Offset: 0

N. J. A. Sloane, Jan 19 2017

This has the same start as two other sequences, A241591 and A248592, but appears to be different from both.

			Coefficients are 1, -4,-6, -154/3, -1610/3, -34588/5, -4666292/45, -553625626/315, -1158735422/35, ...

Gheorghe Coserea, Table of n, a(n) for n = 0..101
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.

Cf. A000699, A280775, A111111, A280777, A280778, A280780, A280781.

Cf. also A241591, A248592.

A000699_seq(N) = {
  my(a = vector(N)); a[1] = 1;
  for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(N) = {
  my(M = subst(x*Ser(A000699_seq(N)), x, x/(1-x)^2));
  Vec(x/(1-x)*exp(1-x/2-(1-x)^2/(2*x)*(2*M + M^2))/M);
};
apply(numerator, seq(18))  \\ Gheorghe Coserea, Jan 22 2017

A280776 Numerators of coefficients in asymptotic expansion of C_n (number of connected chord diagrams, A000699).

Original entry on oeis.org

1, -5, -43, -579, -44477, -5326191, -180306541, -203331297947, -58726239094693, -781618285277957, -1025587838964854273, -35763822710356866613, -330773478104531041960421, -237504847171108896327033959, -196526060612842999084524774697, -20633624138373135772483762873819

Offset: 0

N. J. A. Sloane, Jan 19 2017

			Coefficients are 1, -5/2, -43/8, -579/16, -44477/128, -5326191/1280, -180306541/3072, ...

Gheorghe Coserea, Table of n, a(n) for n = 0..101
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.

Cf. A000699, A280775, A111111, A280777, A280778, A280779, A280780, A280781.

A000699_seq(N) = {
  my(a = vector(N)); a[1] = 1;
  for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(N) = my(C = 'x*Ser(A000699_seq(N))); Vec(x*exp(1-(2*C+C^2)/(2*x))/C);
apply(numerator, seq(16))  \\ Gheorghe Coserea, Jan 22 2017

More terms from Gheorghe Coserea, Jan 22 2017

cp's OEIS Frontend

A111111 Number of simple permutations of degree n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A280780 Numerators of coefficients in asymptotic expansion of S_n (number of simple permutations, A111111).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A280777 Denominators of coefficients in asymptotic expansion of C_n (number of connected chord diagrams, A000699).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A280778 Numerators of coefficients in asymptotic expansion of M_n (number of monolithic chord diagrams, A280775).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A280779 Denominators of coefficients in asymptotic expansion of M_n (number of monolithic chord diagrams, A280775).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A280776 Numerators of coefficients in asymptotic expansion of C_n (number of connected chord diagrams, A000699).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions