cp's OEIS Frontend

A061018 Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions.

%I A061018 #25 Aug 17 2024 20:41:10
%S A061018 1,1,1,2,3,4,6,10,13,15,24,42,56,67,76,120,216,294,358,411,455,720,
%T A061018 1320,1824,2250,2612,2921,3186,5040,9360,13080,16296,19086,21514,
%U A061018 23633,25487,40320,75600,106560,133800,157824,179058,197864,214551,229384
%N A061018 Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions.
%C A061018 Row sums of n are the number of derangements (permutations without fixed point) of n+1, i.e. A000166(n+1).
%F A061018 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).
%F A061018 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
%e A061018 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}
%e A061018 {1},
%e A061018 {1, 1},
%e A061018 {2, 3, 4},
%e A061018 {6, 10, 13, 15},
%e A061018 {24, 42, 56, 67, 76},
%e A061018 {120, 216, 294, 358, 411, 455},
%e A061018 {720, 1320, 1824, 2250, 2612, 2921, 3186}, ...
%p A061018 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
%p A061018 T := (n, k) -> `if`(n=k,n!-GAMMA(n+1,-1)/exp(1),n!*(1-hypergeom([-k],[-n],-1))):
%p A061018 for n from 1 to 9 do seq(simplify(T(n,k)), k=1..n) od; # _Peter Luschny_, Oct 03 2017
%t A061018 Table[Count[Permutations[Range[n]], p_/;( Times@@Take[(p-Range[n]), k]===0)], {n, 7}, {k, n}]
%Y A061018 Columns: A000142, A007680, A002467, A180191.
%K A061018 nonn,tabl,easy
%O A061018 1,4
%A A061018 _Wouter Meeussen_, May 23 2001
%E A061018 Edited and information added by _Johannes W. Meijer_, Jul 27 2011