A061018 Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions.
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
Offset: 1
Examples
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}, ...
Programs
-
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}]
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
Extensions
Edited and information added by Johannes W. Meijer, Jul 27 2011
Comments