cp's OEIS Frontend

A008291 Triangle of rencontres numbers.

%I A008291 #47 Aug 23 2021 07:37:40
%S A008291 1,2,3,9,8,6,44,45,20,10,265,264,135,40,15,1854,1855,924,315,70,21,
%T A008291 14833,14832,7420,2464,630,112,28,133496,133497,66744,22260,5544,1134,
%U A008291 168,36,1334961,1334960,667485,222480,55650,11088,1890,240,45,14684570
%N A008291 Triangle of rencontres numbers.
%C A008291 T(n,k) = number of permutations of n elements with k fixed points.
%C A008291 T(n,n-1)=0 and T(n,n)=1 are omitted from the array. - _Geoffrey Critzer_, Nov 28 2011.
%D A008291 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.
%D A008291 Kaufmann, Arnold. "Introduction a la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
%D A008291 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
%H A008291 T. D. Noe, <a href="/A008291/b008291.txt">Rows n=2..50, flattened</a>
%H A008291 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000022">The number of fixed points of a permutation</a>
%H A008291 I. Kaplansky, <a href="http://dx.doi.org/10.1090/S0002-9904-1944-08261-X">Symbolic solution of certain problems in permutations</a>, Bull. Amer. Math. Soc., 50 (1944), 906-914.
%F A008291 T(n,k) = binomial(n,k)*A000166(n-k) = A008290(n,k).
%F A008291 E.g.f. for column k: (x^k/k!)(exp(-x)/(1-x)). - _Geoffrey Critzer_, Nov 28 2011
%F A008291 Row generating polynomials appear to be given by -1 + sum {k = 0..n} (-1)^(n+k)*C(n,k)*(1+k*x)^(n-k)*(2+(k-1)*x)^k. - _Peter Bala_, Dec 29 2011
%e A008291 Triangle begins:
%e A008291        1
%e A008291        2      3
%e A008291        9      8     6
%e A008291       44     45    20    10
%e A008291      265    264   135    40   15
%e A008291     1854   1855   924   315   70   21
%e A008291    14833  14832  7420  2464  630  112  28
%e A008291   133496 133497 66744 22260 5544 1134 168 36
%e A008291   ...
%p A008291 T:= proc(n, k) T(n, k):= `if`(k=0, `if`(n<2, 1-n, (n-1)*
%p A008291       (T(n-1, 0)+T(n-2, 0))), binomial(n, k)*T(n-k, 0))
%p A008291     end:
%p A008291 seq(seq(T(n, k), k=0..n-2), n=2..12);  # _Alois P. Heinz_, Mar 17 2013
%t A008291 Prepend[Flatten[f[list_]:=Select[list,#>1&];Map[f,Drop[Transpose[Table[d = Exp[-x]/(1 - x);Range[0, 10]! CoefficientList[Series[d x^k/k!, {x, 0, 10}],x], {k, 0, 8}]], 3]]], 1] (* _Geoffrey Critzer_, Nov 28 2011 *)
%o A008291 (PARI) T(n, k)= if(k<0 || k>n, 0, n!/k!*sum(i=0, n-k, (-1)^i/i!))
%Y A008291 Cf. A008290, A170942.
%Y A008291 Diagonals give A000217, A007290, A060008, A060836, A000166, A000240, A000387, A000449, A000475.
%Y A008291 Row sums give A033312.
%Y A008291 Cf. A320582.
%K A008291 nonn,tabl,nice,easy
%O A008291 2,2
%A A008291 _N. J. A. Sloane_
%E A008291 Comments and more terms from _Michael Somos_, Apr 26 2000