A008291 Triangle of rencontres numbers.

1, 2, 3, 9, 8, 6, 44, 45, 20, 10, 265, 264, 135, 40, 15, 1854, 1855, 924, 315, 70, 21, 14833, 14832, 7420, 2464, 630, 112, 28, 133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 1334961, 1334960, 667485, 222480, 55650, 11088, 1890, 240, 45, 14684570

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• nice
• easy

Comments

T(n,k) = number of permutations of n elements with k fixed points.

T(n,n-1)=0 and T(n,n)=1 are omitted from the array. - Geoffrey Critzer, Nov 28 2011.

Examples

			Triangle begins:
       1
       2      3
       9      8     6
      44     45    20    10
     265    264   135    40   15
    1854   1855   924   315   70   21
   14833  14832  7420  2464  630  112  28
  133496 133497 66744 22260 5544 1134 168 36
  ...
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.
• Kaufmann, Arnold. "Introduction a la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.

Links

• T. D. Noe, Rows n=2..50, flattened
• 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.

Crossrefs

Cf. A008290, A170942.

Diagonals give A000217, A007290, A060008, A060836, A000166, A000240, A000387, A000449, A000475.

Row sums give A033312.

Cf. A320582.

Programs

Maple

T:= proc(n, k) T(n, k):= `if`(k=0, `if`(n<2, 1-n, (n-1)*
      (T(n-1, 0)+T(n-2, 0))), binomial(n, k)*T(n-k, 0))
    end:
seq(seq(T(n, k), k=0..n-2), n=2..12);  # Alois P. Heinz, Mar 17 2013

Mathematica

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 *)

PARI

T(n, k)= if(k<0 || k>n, 0, n!/k!*sum(i=0, n-k, (-1)^i/i!))

Formula

T(n,k) = binomial(n,k)*A000166(n-k) = A008290(n,k).

E.g.f. for column k: (x^k/k!)(exp(-x)/(1-x)). - Geoffrey Critzer, Nov 28 2011

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

Extensions

Comments and more terms from Michael Somos, Apr 26 2000