The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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). 90
 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 This triangle equals (A211229(2*n,2*k)) n,k >= 0. - Peter Bala, Dec 17 2014 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. Arnold Kaufmann, Introduction à 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=0..50 of triangle, flattened Taha Akbari, Prove using combinatorics Sum_{k=0..n} (k-1)^2 D_n(k)=n!, Math StackExchange Jun 06 2017 P. Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.9.6. Stefano Capparelli, Margherita Maria Ferrari, Emanuele Munarini, Norma Zagaglia Salvi, A Generalization of the "Problème des Rencontres", J. Int. Seq. 21 (2018), #18.2.8. Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016. See Table 1. S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262. Robert W. Donley Jr, Binomial arrays and generalized Vandermonde identities, arXiv:1905.01525 [math.CO], 2019. 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. J. Liese and J. Remmel, Q-analogues of the number of permutations with k-excedances, PU. M. A. Vol. 21 (2010), No. 2, pp. 285-320 (see E_{n,0}(x) in Table 1 p. 291). L. Takacs, On the "problème des ménages", Discr. Math. 36 (3) (1981) 289-297, Table 2. 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_{k=0..n} T(n, k) = Sum_{k=0..n} k * T(n, k) = n! for all n>0, n, k integers. - Wouter Meeussen, May 29 2001 From Vladeta Jovovic, Aug 12 2002: (Start) O.g.f. for k-th column: 1/k!*Sum_{i>=k} i!*x^i/(1+x)^(i+1). O.g.f. for k-th row: k!*Sum_{i=0..k} (-1)^i/i!*(1-x)^i. (End) 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_{j=0..n-k} ((-1)^j)/j!, n >= k >= 0. From the Appell type of the triangle and the subfactorial formula. T(n,0) = n*Sum_{j=0..n-1} (j/(j+1))*T(n-1,j), 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 Sum_{k=0..n} k^2 * T(n, k) = 2*n! if n > 1. - Michael Somos, Jun 06 2017 From Tom Copeland, Jul 26 2017: (Start) The lowering and raising operators of this Appell sequence of polynomials P(n,x) are L = d/dx and R = x + d/dL log[exp(-L)/(1-L)] = x-1 + 1/(1-L) = x + L + L^2 - ... such that L P(n,x) = n P(n-1,x) and R P(n,x) = P(n+1,x). P(n,x) = (1-L)^(-1) exp(-L) x^n = (1+L+L^2+...)(x-1)^n = n! Sum_{k=0..n} (x-1)^k / k!. The formalism of A133314 applies to the pair of entries A008290 and A055137. The polynomials of this pair P_n(x) and Q_n(x) are umbral compositional inverses; i.e., P_n(Q.(x)) = x^n = Q_n(P.(x)), where, e.g., (Q.(x))^n = Q_n(x). For more on the infinitesimal generator, noted by Bala below, see A238385. (End) Sum_{k=0..n} k^m * T(n, k) = A000110(m)*n! if n >= m. - Zhujun Zhang, May 24 2019 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 ... From Peter Bala, Feb 13 2017: (Start) The infinitesimal generator has integer entries given by binomial(n,k)*(n-k-1)! for n >= 2 and 0 <= k <= n-2 and begins    0    0  0    1  0  0    2  3  0  0    6  8  6  0 0   24 30 20 10 0 0 ... It is essentially A238363 (unsigned and omitting the main diagonal), A216603 (with different offset) and appears to be A092271, again without the main diagonal. (End) 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 = 1; a = 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 *) T[n_, k_] := Subfactorial[n-k]*Binomial[n, k]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 12 2017 *) PROG (PARI) {T(n, k) = if(k<0 || k>n, 0, n!/k! * sum(i=0, n-k, (-1)^i/i!))}; /* Michael Somos, Apr 26 2000 */ (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 (row sums), A000354. Cf. A170942. Sub-triangle of A211229. Cf. A092271, A111492, A211603, A238363. T(2n,n) gives A281262. Cf. A133314, A238385, A320582. Sequence in context: A004443 A171616 A323883 * A322147 A059066 A059067 Adjacent sequences:  A008287 A008288 A008289 * A008291 A008292 A008293 KEYWORD nonn,tabl,nice AUTHOR 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 | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 1 22:36 EDT 2021. Contains 346408 sequences. (Running on oeis4.)