A186373 -id:A186373 - cp's OEIS frontend

A052186 Number of permutations of [n] with no strong fixed points.

1, 0, 1, 3, 14, 77, 497, 3676, 30677, 285335, 2928846, 32903721, 401739797, 5298600772, 75092880273, 1138261010851, 18378421938366, 314928827507717, 5708689036074089, 109145365739197964, 2195167574579322013, 46331767712354136479, 1023970009016490622478

Offset: 0

N. J. A. Sloane, Feb 04 2000

A strong fixed point is a fixed point (or splitter) p(k)=k such that p(i) < k for i < k and p(j) > k for j > k.

Equals INVERTi transform of the factorials, n starting with 0. Triangle A144108 has row sums = n! with left border = A052186. - Gary W. Adamson, Sep 11 2008

Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49

Alois P. Heinz, Table of n, a(n) for n = 0..450
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Natasha Blitvić and Einar Steingrímsson, Permutations, moments, measures, arXiv:2001.00280 [math.CO], 2020.
Sergey Kitaev and Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Richard J. Martin, and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
V. Strehl, The average number of splitters in a random permutation [Unpublished; included here with the author's permission.]

Cf. A006932, A201684, A256168.
Cf. A144108, A000142. - Gary W. Adamson, Sep 11 2008
Column k=0 of A186373.

t1 := add(n!*x^n, n=0..100): F := series(t1/(1+x*t1), x, 100): for i from 0 to 20 do printf(`%d, `, coeff(F, x, i)) od: # Zerinvary Lajos, Mar 22 2009
# second Maple program:
a:= proc(n) a(n):= -`if`(n<0, 1, add(a(n-i-1)*i!, i=0..n)) end:
seq(a(n), n=0..25);  # Alois P. Heinz, May 21 2013

m = 20; CoefficientList[ Series[ 1 / (x + 1/Sum[ n!*x^n, {n, 0, m}]), {x, 0, m}], x] (* Jean-François Alcover, Aug 30 2011, after Michael Somos *)
nmax = 25; Rest[CoefficientList[Assuming[Element[x, Reals], Series[-1/(ExpIntegralEi[1/x]/E^(1/x) + 1), {x, 0, nmax+1}]], x]] (* Vaclav Kotesovec, Aug 05 2015 *)

{a(n)=if(n<0, 0, polcoeff( 1/ (x+1/sum(k=0, n, k!*x^k, x*O(x^n))), n))} /* Michael Somos, Oct 11 2006 */

G.f.: F(x)/(1 + x*F(x)), F(x) = Sum_{n >= 0} n!*x^n.
a(0)=1, a(1)=0, a(n) = (n-2)*a(n-1) + Sum_{k=0..n-1} a(k)*a(n-1-k) + Sum_{k=0..n-2} a(k)*a(n-2-k) if n > 1. - Michael Somos, Oct 11 2006
G.f.: 1/(1-x^2/(1-3x-4x^2/(1-5x-9x^2/(1-7x-16x^2/(1-9x-25x^2/(1-... (continued fraction). - Paul Barry, Dec 09 2009
If p[i] = Stirling1(i,1) and if A is the Hessenberg matrix of order n defined by A[i,j] = p[j-i+1], (i <= j), A[i,j] = -1, (i=j+1), and A[i,j]=0 otherwise, then, for n >= 1, a(n-1) = (-1)^(n-1) det A. - Milan Janjic, May 08 2010
From Gary W. Adamson, Jul 22 2011: (Start)
a(n) = upper left term in (-1)*M^(n+1), M = an infinite square production matrix in which a column of (-1)'s is prepended to Pascal's triangle as follows:
  -1, 1, 0, 0, 0, 0, ...
  -1, 1, 1, 0, 0, 0, ...
  -1, 1, 2, 1, 0, 0, ...
  -1, 1, 3, 3, 1, 0, ...
  -1, 1, 4, 6, 4, 1, ...
  ... (End)
G.f.: A(x) = 1/(1/G(0) + x); G(k) = 1 + x*(2*k+1)/(1 - 2*x*(k+1)/(2*x*(k+1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 29 2011
G.f.: A(x) = 1/x = 1/(1+x)*(1+x/((1+x)*G(0)-x)); G(k) = 1 + x*(k+1) - x*(k+2)/G(k+1); (continued fraction Euler's kind, 1-step ). - Sergei N. Gladkovskii, Dec 29 2011
G.f.: 1/(G(0) + x) where G(k) = 1  - x*(k+1)/(1 - x*(k+1)/G(k+1) ); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 19 2012
G.f.: 1/(1 - W(0)) where W(k) = x*(2*k+1) - 1 - x^2*(k+1)^2/W(k+1); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 19 2012
G.f.: 1/(G(0) + x), where G(k)= 1 + x*k - x*(k+1)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jul 03 2013
a(n) ~ n! * (1 - 2/n + 1/n^2 - 1/n^3 - 9/n^4 - 59/n^5 - 474/n^6 - 4560/n^7 - 50364/n^8 - 625385/n^9 - 8622658/n^10), for coefficients see A256168. - Vaclav Kotesovec, Mar 16 2015
a(n) = n! - Sum_{k=0..n-1} (n-k-1)!*a(k). - Pontus von Brömssen, Jul 10 2021
a(n) + A006932(n) = n!. - Pontus von Brömssen, Jul 10 2021

Better description from James Sellers, Mar 13 2000

A225960 Number of permutations of [n] having exactly one strong fixed block.

Original entry on oeis.org

0, 1, 1, 3, 9, 38, 198, 1229, 8819, 71825, 654985, 6615932, 73357572, 886078937, 11583028581, 162939646239, 2454350815033, 39415438078466, 672282146765650, 12137067564016917, 231223273420524311, 4635720862911035149, 97565878042828417209, 2150797149322137710488

Offset: 0

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..450 (first 201 and last 2 terms from Alois P. Heinz)

Column k=1 of A186373.

Cf. A052186, A260957.

b:= proc(n) b(n):= -`if`(n<0, 1, add(b(n-i-1)*i!, i=0..n)) end:
a:= n-> add(b(i)*add(b(j), j=0..n-i-1), i=0..n-1):
seq(a(n), n=0..25);

nmax = 25; A052186zero = Rest[CoefficientList[Assuming[Element[x, Reals], Series[-1/(ExpIntegralEi[1/x]/E^(1/x) + 1), {x, 0, nmax+1}]], x]]; suma = ConstantArray[0, nmax+1]; s = 0; Do[s = s + A052186zero[[j+1]]; suma[[j+1]] = s, {j, 0, nmax}]; Flatten[{0, Table[Sum[A052186zero[[i+1]]*suma[[n-i]], {i, 0, n-1}], {n, 1, nmax}]}] (* Vaclav Kotesovec, Aug 05 2015, more efficient program for big nmax *)

a(n) = Sum_{1<=i<=j<=n} A052186(i-1) * A052186(n-j).
a(n) = Sum_{i=0..n-1} A052186(i) * Sum_{j=0..n-i-1} A052186(j).
a(n) ~ 2 * (n-1)! * (1 - 1/n + 2/n^3 + 11/n^4 + 97/n^5 + 1105/n^6 + 13905/n^7 + 189633/n^8 + 2803873/n^9 + 44875599/n^10), for coefficients see A260957. - Vaclav Kotesovec, Aug 29 2014, extended Aug 05 2015

A186374 Number of strong fixed blocks in all the permutations of [n] (see first comment for definition).

Original entry on oeis.org

0, 1, 1, 3, 11, 48, 248, 1500, 10476, 83328, 745344, 7413120, 81187200, 970928640, 12589240320, 175900757760, 2634526944000, 42103369728000, 715107004416000, 12862666543104000, 244249409359872000, 4882687056543744000, 102496533840691200000

Offset: 0

Emeric Deutsch, Apr 18 2011

nonn

A fixed block of a permutation p is a maximal sequence of consecutive fixed points of p. For example, the permutation 213486759 has 3 fixed blocks: 34, 67, and 9. A fixed block f of a permutation p is said to be strong if all the entries to the left (right) of f are smaller (larger) than all the entries of f. In the above example, only 34 and 9 are strong fixed blocks.

			a(3) = 3 because in [123], [1]32, 21[3], 231, 312, 321 we have 1 + 1 + 1 + 0 + 0 + 0 strong fixed blocks (shown between square brackets).

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A186373, A003149.

a:= proc(n) option remember; `if`(n<5, [0, 1, 1, 3, 11][n+1],
      ((3*n^2-12*n+2)*a(n-1) -(n^3-3*n^2-8*n+23)*a(n-2)
       +(n-3)^3*a(n-3)) / (2*n-8))
    end:
seq(a(n), n=0..24);  # Alois P. Heinz, May 22 2013

Flatten[{0, 1, Table[(n-1)! + Sum[k!*(n-2-k)!*(n-2-k), {k,0,n-2}], {n,2,20}]}] (* Vaclav Kotesovec, Aug 04 2015 *)
Flatten[{0, Simplify[Table[Gamma[n] * (1 - (n-2)*(I*Pi/2^n + LerchPhi[2, 1, n])), {n, 1, 20}]]}] (* Vaclav Kotesovec, Aug 04 2015 *)

a(n) = Sum(k*A186373(n,k), k>=0).
Apparently, a(n) = A003149(n-1)-A003149(n-2) or, equivalently, a(n)=(n-1)! + Sum(k!*(n-2-k)!*(n-2-k), k=0..n-2).
a(n) ~ 2 * (n-1)! * ((1 + 1/n^2 + 7/n^3 + 49/n^4 + 391/n^5 + 3601/n^6 + 37927/n^7 + 451249/n^8 + 5995591/n^9 + 88073041/n^10)). - Vaclav Kotesovec, Mar 17 2015
Recurrence (for n>=3): 2*(n^2 - 7*n + 11)*a(n) = (n-2)*(3*n^2 - 17*n + 17)*a(n-1) - (n-2)^2*(n^2 - 5*n + 5)*a(n-2). - Vaclav Kotesovec, Aug 04 2015

a(11)-a(22) from Alois P. Heinz, May 22 2013

A225963 Number of permutations of [n] having exactly 2 strong fixed blocks.

Original entry on oeis.org

1, 5, 25, 134, 815, 5657, 44549, 394266, 3883182, 42174500, 500942458, 6460077110, 89875729761, 1341559805867, 21382747361727, 362402701510514, 6507348542427217, 123394642353693319, 2463866954996239829, 51670868533003154264, 1135456889195715187948

Offset: 4

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 4..450

Column k=2 of A186373.

a(n) ~ n! / n^2. - Vaclav Kotesovec, Aug 29 2014

A225964 Number of permutations of [n] having exactly 3 strong fixed blocks.

Original entry on oeis.org

1, 9, 63, 419, 2868, 20932, 165662, 1432746, 13578086, 140951642, 1598792812, 19739303596, 264041415799, 3807692229035, 58907522237037, 973166134330293, 17094936849558000, 318092941562300736, 6248389843759774380, 129180041710223480596, 2803277432655658573548

Offset: 7

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 7..450

Column k=3 of A186373.

a(n) ~ 2 * n! / n^5. - Vaclav Kotesovec, Aug 29 2014

A225965 Number of permutations of [n] having exactly 4 strong fixed blocks.

Original entry on oeis.org

1, 13, 117, 928, 7125, 55527, 451472, 3896347, 36098855, 361638248, 3932908263, 46483325765, 596325240445, 8278698772954, 123863754811374, 1988038987565688, 34070987657660446, 620747700139873322, 11975106447284305656, 243741719070454243530

Offset: 10

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 10..450

Column k=4 of A186373.

a(n) ~ 3 * n! / n^8. - Vaclav Kotesovec, Aug 29 2014

A225966 Number of permutations of [n] having exactly 5 strong fixed blocks.

Original entry on oeis.org

1, 17, 187, 1725, 14770, 123810, 1049683, 9201893, 84765839, 830632443, 8737884632, 99283914256, 1222304625766, 16308650537598, 235329993989098, 3658770788460622, 61010416134839892, 1085940325012439060, 20537758641146194266, 410995800089222969774

Offset: 13

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 13..450

Column k=5 of A186373.

a(n) ~ 4 * n! / n^11. - Vaclav Kotesovec, Aug 29 2014

A225967 Number of permutations of [n] having exactly 6 strong fixed blocks.

Original entry on oeis.org

1, 21, 273, 2874, 27243, 246037, 2192863, 19766016, 183564396, 1782944112, 18338911012, 201770228316, 2392011321782, 30683876823738, 426312246308898, 6403885291569540, 103619141358704966, 1797448899803758010, 33259985875540203746, 653383741590779444772

Offset: 16

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 16..460

Column k=6 of A186373.

a(n) ~ 5 * n! / n^14. - Vaclav Kotesovec, Aug 29 2014

A225968 Number of permutations of [n] having exactly 7 strong fixed blocks.

Original entry on oeis.org

1, 25, 375, 4439, 46240, 449376, 4226604, 39474916, 373382588, 3635491860, 36957484104, 397181210056, 4560293779650, 56383382731802, 754184534296262, 10926207562498862, 171119131459887864, 2885501334257214456, 52124282589435604908, 1003403354618592544692

Offset: 19

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 19..460

Column k=7 of A186373.

a(n) ~ 6 * n! / n^17. - Vaclav Kotesovec, Aug 29 2014

A225969 Number of permutations of [n] having exactly 8 strong fixed blocks.

Original entry on oeis.org

1, 29, 493, 6484, 73713, 768931, 7641778, 74285193, 720732077, 7097087844, 71988257273, 762506830931, 8539944840752, 102230338451871, 1318698786618219, 18414090830686692, 278579895011969895, 4555101560023980405, 80136465741614450118, 1508615434533451340535

Offset: 22

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz, Table of n, a(n) for n = 22..460

Column k=8 of A186373.

a(n) ~ 7 * n! / n^20. - Vaclav Kotesovec, Aug 29 2014

cp's OEIS Frontend

A052186 Number of permutations of [n] with no strong fixed points.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A225960 Number of permutations of [n] having exactly one strong fixed block.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A186374 Number of strong fixed blocks in all the permutations of [n] (see first comment for definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A225963 Number of permutations of [n] having exactly 2 strong fixed blocks.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A225964 Number of permutations of [n] having exactly 3 strong fixed blocks.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A225965 Number of permutations of [n] having exactly 4 strong fixed blocks.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A225966 Number of permutations of [n] having exactly 5 strong fixed blocks.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A225967 Number of permutations of [n] having exactly 6 strong fixed blocks.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A225968 Number of permutations of [n] having exactly 7 strong fixed blocks.