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
References
- Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49
Links
- 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.]
Crossrefs
Programs
-
Maple
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
-
Mathematica
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 *) -
PARI
{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 */
Formula
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
Extensions
Better description from James Sellers, Mar 13 2000
Comments