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,2

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.

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.

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

Example

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
  ...

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

Prog

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

Crossrefs

Cf. A008290, A170942.

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

Row sums give A033312.

Cf. A320582.

Sequence in context: A152812 A246825 A086565 * A261525 A122665 A133066

Adjacent sequences: A008288 A008289 A008290 * A008292 A008293 A008294

Keyword

nonn,tabl,nice,easy

Author

N. J. A. Sloane

Extensions

Comments and more terms from Michael Somos, Apr 26 2000

Status

approved