A006932 Number of permutations of [n] with at least one strong fixed point (a permutation p of {1,2,...,n} is said to have j as a strong fixed point if p(k) < j for k < j and p(k) > j for k > j). (Formerly M2862)

1, 1, 3, 10, 43, 223, 1364, 9643, 77545, 699954, 7013079, 77261803, 928420028, 12085410927, 169413357149, 2544367949634, 40758600588283, 693684669653911, 12499734669634036, 237734433597317987, 4759174459355303521

Offset

1,3

Comments

a(n) is also the number of permutation graphs with domination number one. See Definition 2.1, Lemma 2.3, and page 16 in the paper provided in the link by Theresa Baren, et al. - Daniel A. McGinnis, Oct 16 2018

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

K. Wayland, personal communication.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..200

Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, and Tony W. H. Wong, On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points, arXiv:1810.03409 [math.CO], 2018.

Todd Feil, Gary Kennedy and David Callan, Problem E3467, Amer. Math. Monthly, 100 (1993), 800-801.

V. Strehl, The average number of splitters in a random permutation [Unpublished; included here with the author's permission.]

Formula

a(n) ~ 2 * (n-1)! * (1 - 1/(2*n) + 1/(2*n^2) + 9/(2*n^3) + 59/(2*n^4) + 237/n^5 + 2280/n^6 + 25182/n^7 + 625385/(2*n^8) + 4311329/n^9 + 65375943/n^10). - Vaclav Kotesovec, Mar 17 2015

a(n) = Sum_{k=1..n} (n-k)!*A145878(k-1,0). See the link by Theresa Baren, et al. - Daniel A. McGinnis, Oct 15 2018

a(n) = A003149(n-1) - Sum_{k=0..n-1} (n-k-1)!*a(k). (This follows immediately from the preceding formula since A145878(k,0) = k! - a(k).) - Pontus von Brömssen, Jul 10 2021

a(n) + A052186(n) = n! - Pontus von Brömssen, Jul 10 2021

Maple

t1 := sum(n!*x^n, n=0..100): F := series(t1/(1+x*t1), x, 100): for i from 1 to 40 do printf(`%d, `, i!-coeff(F, x, i)) od: # James A. Sellers, Mar 13 2000

Mathematica

m = 22; s = Sum[n!*x^n, {n, 0, m}]; Range[0, m-1]! - CoefficientList[ Series[ s/(1+x*s), {x, 0, m}], x][[1;; m]] // Rest (* Jean-François Alcover, Apr 28 2011, after Maple code *)

Crossrefs

Cf. A003149, A052186, A145878.

Sequence in context: A157313 A030971 A248687 * A001040 A181949 A162286

Adjacent sequences: A006929 A006930 A006931 * A006933 A006934 A006935

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Mar 13 2000

Edited by Emeric Deutsch, Oct 29 2008

Status

approved