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).
1, 1, 3, 10, 43, 223, 1364, 9643, 77545, 699954, 7013079, 77261803, 928420028, 12085410927, 169413357149, 2544367949634, 40758600588283, 693684669653911, 12499734669634036, 237734433597317987, 4759174459355303521
Offset: 1
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.]
Programs
-
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 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 *)
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
Extensions
More terms from James Sellers, Mar 13 2000
Edited by Emeric Deutsch, Oct 29 2008
Comments