|
%I M2862 #70 Jul 13 2021 19:47:34
%S 1,1,3,10,43,223,1364,9643,77545,699954,7013079,77261803,928420028,
%T 12085410927,169413357149,2544367949634,40758600588283,
%U 693684669653911,12499734669634036,237734433597317987,4759174459355303521
%N 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).
%C 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
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49.
%D K. Wayland, personal communication.
%H Vincenzo Librandi, <a href="/A006932/b006932.txt">Table of n, a(n) for n = 1..200</a>
%H Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, and Tony W. H. Wong, <a href="https://arxiv.org/abs/1810.03409">On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points</a>, arXiv:1810.03409 [math.CO], 2018.
%H Todd Feil, Gary Kennedy and David Callan, <a href="http://www.jstor.org/stable/2324797">Problem E3467</a>, Amer. Math. Monthly, 100 (1993), 800-801.
%H V. Strehl, <a href="/A003149/a003149.pdf">The average number of splitters in a random permutation</a> [Unpublished; included here with the author's permission.]
%F 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
%F 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
%F 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
%F a(n) + A052186(n) = n! - _Pontus von Brömssen_, Jul 10 2021
%p 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
%t 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 *)
%Y Cf. A003149, A052186, A145878.
%K nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_
%E More terms from _James A. Sellers_, Mar 13 2000
%E Edited by _Emeric Deutsch_, Oct 29 2008
|
