login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008291 Triangle of rencontres numbers. 23
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 (list; table; graph; refs; listen; history; text; internal format)
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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 18 14:27 EDT 2017. Contains 290720 sequences.