%I A008290
%S A008290 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,
%T A008290 1854,1855,924,315,70,21,0,1,14833,14832,7420,2464,630,112,28,0,1,
%U A008290 133496,133497,66744,22260,5544,1134,168,36,0,1,1334961,1334960,667485
%N A008290 Triangle T(n,k) of rencontres numbers (number of permutations of n elements 
               with k fixed points).
%C A008290 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. W. Lang, 
               Jan 21 2008.
%C A008290 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. W. Lang, Jan 21 2008.
%C A008290 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 (deutsch(AT)duke.poly.edu), Mar 29 2008
%C A008290 T is an example of the group of matrices outlined in the table in A132382--the 
               associated matrix for the sequence aC(0,1). [From Tom Copeland (tcjpn(AT)msn.com), 
               Sep 10 2008]
%D A008290 S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, 
               Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
%D A008290 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 
               Reading, MA, 1990, p. 194.
%D A008290 I. Kaplansky, Symbolic solution of certain problems in permutations, 
               Bull. Amer. Math. Soc., 50 (1944), 906-914.
%D A008290 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 
               65.
%D A008290 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).
%H A008290 T. D. Noe, <a href="b008290.txt">Rows n=0..50 of triangle, flattened</
               a>
%F A008290 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.
%F A008290 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(AT)pandora.be, May 29 2001
%F A008290 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 
               (vladeta(AT)eunet.rs), Aug 12 2002
%F A008290 E.g.f.: exp((y-1)*x)/(1-x). - Vladeta Jovovic (vladeta(AT)eunet.rs), 
               Aug 18 2002
%F A008290 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. - 
               DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 12 2003
%F A008290 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 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), 
               Dec 13 2003
%F A008290 T(n,k)=sum{j=0..n, (-1)^(j-k)*binomial(j,k)*n!/j!}; - Paul Barry (pbarry(AT)wit.ie), 
               May 25 2006
%F A008290 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.
%F A008290 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. 
               W. Lang. Jan 21 2008.
%F A008290 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. W. Lang. 
               Jan 21 2008.
%e A008290 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+...
%e A008290 Triangle begins:
%e A008290 1
%e A008290 0 1
%e A008290 1 0 1
%e A008290 2 3 0 1
%e A008290 9 8 6 0 1
%e A008290 44 45 20 10 0 1
%e A008290 265 264 135 40 15 0 1
%e A008290 1854 1855 924 315 70 21 0 1
%e A008290 14833 14832 7420 2464 630 112 28 0 1
%e A008290 133496 133497 66744 22260 5544 1134 168 36 0 1
%t A008290 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 (from Harlan J. 
               Brothers, Mar 19 2007)
%o A008290 (PARI) {T(n, k)= if(k<0|k>n, 0, n!/k!*sum(i=0, n-k, (-1)^i/i!))}
%Y A008290 Columns give A000166, A000240, A000387, A000449, A000475. Cf. A055137, 
               A008291.
%Y A008290 T(n, k)=binomial(n, k)*A000166(n-k)
%Y A008290 Cf. A080955.
%Y A008290 Cf. A000012 A000142 A000354.
%Y A008290 Sequence in context: A163575 A163465 A004443 this_sequence A059066 A059067 
               A065861
%Y A008290 Adjacent sequences: A008287 A008288 A008289 this_sequence A008291 A008292 
               A008293
%K A008290 nonn,tabl,nice
%O A008290 0,7
%A A008290 N. J. A. Sloane (njas(AT)research.att.com).
%E A008290 Comments and more terms from Michael Somos, Apr 26 2000 and Christian 
               G. Bower (bowerc(AT)usa.net), Apr 26 2000