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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008290 Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points). 76
1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 9, 8, 6, 0, 1, 44, 45, 20, 10, 0, 1, 265, 264, 135, 40, 15, 0, 1, 1854, 1855, 924, 315, 70, 21, 0, 1, 14833, 14832, 7420, 2464, 630, 112, 28, 0, 1, 133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1, 1334961, 1334960, 667485, 222480, 55650, 11088, 1890, 240, 45, 0, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

This is a binomial convolution triangle (Sheffer triangle) of the Appell type: (exp(-x)/(1-x),x), i.e. the e.g.f. of column k is (exp(-x)/(1-x))*(x^k/k!). See the e.g.f. given by V. Jovovic below. - Wolfdieter Lang, Jan 21 2008.

The formula T(n,k)=binomial(n,k)*A000166(n-k), with the derangements numbers (subfactorials) A000166 (see also the Charalambides reference) shows the Appell type of this triangle. - Wolfdieter Lang, Jan 21 2008.

T(n,k) is the number of permutations of {1,2,...,n} having k pairs of consecutive right-to-left minima (0 is considered a right-to-left minimum for each permutation). Example: T(4,2)=6 because we have 1243, 1423, 4123, 1324, 3124 and 2134; for example, 1324 has right-to-left minima in positions 0-1,3-4 and 2134 has right-to-left minima in positions 0,2-3-4, the consecutive ones being joined by -. - Emeric Deutsch, Mar 29 2008

T is an example of the group of matrices outlined in the table in A132382--the associated matrix for the sequence aC(0,1). [Tom Copeland, Sep 10 2008]

A refinement of this triangle is given by A036039. - Tom Copeland, Nov 06 2012

REFERENCES

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 173, Table 5.2 (without row n=0 and column k=0).

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.

LINKS

T. D. Noe, Rows n=0..50 of triangle, flattened

P. Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.9.6.

S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.

FindStat - Combinatorial Statistic Finder, The number of adjacencies of a permutation, 0 appended, 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.

Wikipedia, Rencontres numbers.

FORMULA

T(n, k) = T(n-1, k)*n+C(n, k)*(-1)^(n-k) = T(n, k-1)/k+C(n, k)*(-1)^(n-k)/(n-k+1) = T(n-1, k-1)*n/k = T(n-k, 0)*C(n, k) [with T(0, 0) = 1]; so T(n, n) = 1, T(n, n-1) = 0, T(n, n-2) = n*(n-1)/2 for n >= 0.

Sum[ T[n, k], {k, 0, n}] ==Sum[ k T[n, k], {k, 0, n}] == n! for all n>0, n, k integers. - Wouter Meeussen, May 29 2001

O.g.f. for k-th column is 1/k!*Sum_{i>=k} i!*x^i/(1+x)^(i+1). O.g.f. for k-th row is k!*Sum_{i=0..k} (-1)^i/i!*(1-x)^i. - Vladeta Jovovic, Aug 12 2002

E.g.f.: exp((y-1)*x)/(1-x). - Vladeta Jovovic, Aug 18 2002

Sum(k=0..n, T(n, k)*x^k ) is the permanent of the n X n matrix with x's on the diagonal and 1's elsewhere; for x = 0, 1, 2, 3, 4, 5, 6 see A000166, A000142, A000522, A010842, A053486, A053487, A080954. - Philippe Deléham, Dec 12 2003; for x = 1+i see A009551 and A009102. [John M. Campbell, Oct 11 2011]

T(n, k)= Sum(j=0..n, A008290(n, j)*k^(n-j)) is the permanent of the n X n matrix with 1's on the diagonal and k's elsewhere; for k = 0, 1, 2 see A000012 A000142 A000354 . - Philippe Deléham, Dec 13 2003

T(n,k)=sum{j=0..n, (-1)^(j-k)*binomial(j,k)*n!/j!}. - Paul Barry, May 25 2006

T(n,k)=(n!/k!)*sum(((-1)^j)/j!,j=0..n-k), n>=k>=0. From the Appell type of the triangle and the subfactorial formula.

T(n,0)=n*sum((j/(j+1))*T(n-1,j),j=0..n-1), T(0,0)=1. From the z-sequence of this Sheffer triangle z(j)=j/(j+1) with e.g.f. (1-exp(x)*(1-x))/x. See the W. Lang link under A006232 for Sheffer a- and z-sequences. - Wolfdieter Lang. Jan 21 2008

T(n,k)= (n/k)*T(n-1,k-1) for k>=1. See above. From the a-sequence of this Sheffer triangle a(0)=1, a(n)=0, n>=1 with e.g.f. 1. See the W. Lang link under A006232 for Sheffer a- and z-sequences. - Wolfdieter Lang. Jan 21 2008

From Henk P. J. van Wijk, Oct 29 2012: (Start)

T(n,k) =              T(n-1,k)*(n-1-k) + T(n-1,k+1)*(k+1) for k=0 and

T(n,k) = T(n-1,k-1) + T(n-1,k)*(n-1-k) + T(n-1,k+1)*(k+1) for k>=1. (end)

T(n,k) = A098825(n,n-k). - Reinhard Zumkeller, Dec 16 2013

EXAMPLE

exp((y-1)*x)/(1-x) = 1+y*x+1/2!*(1+y^2)*x^2+1/3!*(2+3*y+y^3)*x^3+1/4!*(9+8*y+6*y^2+y^4)*x^4+1/5!*(44+45*y+20*y^2+10*y^3+y^5)*x^5+...

Triangle begins:

1

0      1

1      0      1

2      3      0     1

9      8      6     0     1

44     45     20    10    0    1

265    264    135   40    15   0    1

1854   1855   924   315   70   21   0   1

14833  14832  7420  2464  630  112  28  0  1

133496 133497 66744 22260 5544 1134 168 36 0 1

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), n=0..12);  # Alois P. Heinz, Mar 15 2013

MATHEMATICA

a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 size = 8; Table[Binomial[n, k]a[n - k], {n, 0, size}, {k, 0, n}] // TableForm (* Harlan J. Brothers, Mar 19 2007 *)

PROG

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

(Haskell)

a008290 n k = a008290_tabl !! n !! k

a008290_row n = a008290_tabl !! n

a008290_tabl = map reverse a098825_tabl

-- Reinhard Zumkeller, Dec 16 2013

CROSSREFS

Columns give A000166, A000240, A000387, A000449, A000475, A129135, A129136, A129149, A129153, A129217, A129218, A129238, A129255.

Cf. A055137, A008291.

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

Cf. A080955.

Cf. A000012, A000142, A000354.

Cf. A170942.

Sequence in context: A163465 A004443 A171616 * A059066 A059067 A065861

Adjacent sequences:  A008287 A008288 A008289 * A008291 A008292 A008293

KEYWORD

nonn,tabl,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Comments and more terms from Michael Somos, Apr 26 2000 and Christian G. Bower, Apr 26 2000

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified November 24 10:51 EST 2014. Contains 249895 sequences.