login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000240 Rencontres numbers: number of permutations of [n] with exactly one fixed point.
(Formerly M2763 N1111)
31
1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840, 2290792933, 32071101048, 481066515735, 7697064251744, 130850092279665, 2355301661033952, 44750731559645107, 895014631192902120, 18795307255050944541, 413496759611120779880 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n) is also the number of permutations of [n] having no circular succession. A circular succession in a permutation p of [n] is either a pair p(i), p(i+1), where p(i+1)=p(i)+1 or the pair p(n), p(1) if p(1)=p(n)+1. a(4)=8 because we have 1324, 1432, 4132, 2143, 2413, 3214, 3241, and 4321. - Emeric Deutsch, Sep 06 2010

a(n) is also the number of permutations of [n] having no substring in {12, 23,...,(n-1)n, n1}. For example, a(4) = 8 since we have 1324, 1432, 4213, 2143, 2431, 3214, 3142, 4321 (different from permutations having no circular succession). - Enrique Navarrete, Oct 07 2016

REFERENCES

Kaufmann, Arnold. "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

LINKS

T. D. Noe, Table of n, a(n) for n=1..100

S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.

FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation

I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.

Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.

S. M. Tanny, Permutations and successions, J. Combinatorial Theory, Series A, 21 (1976), 196-202.

FORMULA

E.g.f.: x*exp(-x)/(1-x). [corrected by Vaclav Kotesovec, Sep 26 2012]

a(n) = sum((-1)^k*n!/k!, k=0..n-1).

a(n) = A180188(n,0). - Emeric Deutsch, Sep 06 2010

E.g.f.: x*A(x) where A(x) is the e.g.f. for A000166. - Geoffrey Critzer, Jan 14 2012

a(n) = n*a(n-1)-(-1)^n*n = A000166(n)-(-1)^n = n*A000166(n-1) = A000387(n+1)*2/(n+1) = A000449(n+2)*6/((n+1)*(n+2)).

a(n) = n*floor(((n-1)!+1)/e), n>1. - Gary Detlefs, Jul 13 2010

lim_{n->infinity} n!/a(n) = e = 2.71828...

a(n) = (n-1) * (a(n-1)+a(n-2)) + (-1)^(n-1), n>=2. - Enrique Navarrete, Oct 07 2016

EXAMPLE

a(3) = 3 because the permutations of (1,2,3) with one fixed point are (1,2), (1,3), (2,3).

MAPLE

G(x):=exp(-x)/(1-x)*x: f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=1..22); # Zerinvary Lajos, Apr 03 2009

A000240 := proc(n)

        n!*add((-1)^k/k!, k=0..n-1) ;

end proc: # R. J. Mathar, Jul 09 2012

MATHEMATICA

Table[Subfactorial[n]-(-1)^n, {n, 1, 25}] (* Zerinvary Lajos, Jul 10 2009, updated for offset 1 by Jean-François Alcover, Jan 10 2014 *)

Table[n!*Sum[(-1)^k/k!, {k, 0, n-1}], {n, 1, 25}] (* Vaclav Kotesovec, Sep 26 2012 *)

Table[n!*SeriesCoefficient[x*E^(-x)/(1-x), {x, 0, n}], {n, 1, 25}] (* Vaclav Kotesovec, Sep 26 2012 *)

PROG

(Python)

a=0

for i in range(1, 51):

. a = (a-(-1)**i)*i

. print a,          # Alex Ratushnyak, Apr 20 2012

(PARI) x='x+O('x^66); Vec( serlaplace(x*exp(-x)/(1-x)) ) \\ Joerg Arndt, Feb 19 2014

CROSSREFS

Cf. A008290, A000166, A000387, A000449, A000475, A129135, etc.

A diagonal of A008291.

Cf. A180188, A170942.

Sequence in context: A074435 A039647 A071533 * A182390 A132103 A180508

Adjacent sequences:  A000237 A000238 A000239 * A000241 A000242 A000243

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Simon Plouffe

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 3 08:48 EST 2016. Contains 278698 sequences.