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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061018 Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions. 3
1, 1, 1, 2, 3, 4, 6, 10, 13, 15, 24, 42, 56, 67, 76, 120, 216, 294, 358, 411, 455, 720, 1320, 1824, 2250, 2612, 2921, 3186, 5040, 9360, 13080, 16296, 19086, 21514, 23633, 25487, 40320, 75600, 106560, 133800, 157824, 179058, 197864, 214551, 229384 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Row sums of n are the number of derangements (permutations without fixed point) of n+1, i.e. A000166(n+1).

LINKS

Table of n, a(n) for n=1..45.

FORMULA

a(n,m) = (n-1)! + Sum_{k=0..m-2} T(n-2, k) where T(n,-1) = 0, T(0,0) = 0, T(n,0) = A001563(n) = n*n!, T(n,m) = T(n,m-1) - T(n-1,m-1) (see A061312).

T(n, k) = n!*(1 - hypergeom([-k], [-n], -1) for 1 <= k < n and T(n, n) = n! -Gamma(n+1, -1)/exp(1). - Peter Luschny, Oct 03 2017

EXAMPLE

For n=3, the permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1); and (x, 2, 3), (x, 3, 2) have a fixed point x in position 1, (x, x, 3), (x, 3, 2), (3, x, 1) have a fixed point x in positions 1 or 2 and (x, x, x), (2, 1, x), (x, 3, 2), (3, x, 1) have a fixed point x in positions 1, 2 or 3, hence {2, 3, 4}

{1},

{1, 1},

{2, 3, 4},

{6, 10, 13, 15},

{24, 42, 56, 67, 76},

{120, 216, 294, 358, 411, 455},

{720, 1320, 1824, 2250, 2612, 2921, 3186}, ...

MAPLE

A061018 := proc(n, m): (n-1)! + add(A061312(n-2, k), k=0..m-2) end: A061312:= proc(n, m): if m=-1 then 0 elif m=0 then n*n! else procname(n, m-1) - procname(n-1, m-1) fi: end: seq(seq(A061018(n, m), m=1..n), n=1..8); # Johannes W. Meijer, Jul 27 2011

T := (n, k) -> `if`(n=k, n!-GAMMA(n+1, -1)/exp(1), n!*(1-hypergeom([-k], [-n], -1))):

for n from 1 to 9 do seq(simplify(T(n, k)), k=1..n) od; # Peter Luschny, Oct 03 2017

MATHEMATICA

Table[Count[Permutations[Range[n]], p_/; ( Times@@Take[(p-Range[n]), k]===0)], {n, 7}, {k, n}]

CROSSREFS

Columns: A000142, A007680, A002467, A180191.

Sequence in context: A237823 A241547 A273542 * A130126 A288338 A121152

Adjacent sequences:  A061015 A061016 A061017 * A061019 A061020 A061021

KEYWORD

nonn,tabl,easy

AUTHOR

Wouter Meeussen, May 23 2001

EXTENSIONS

Edited and information added by Johannes W. Meijer, Jul 27 2011

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 18 01:04 EDT 2019. Contains 326059 sequences. (Running on oeis4.)