A008290 Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points).

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• nice

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

Examples

			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), A211603 (with different offset) and appears to be A092271, again without the main diagonal. (End)
		

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

• Alois P. Heinz, Rows n = 0..150, flattened (first 51 rows from T. D. Noe)
• Taha Akbari, Prove using combinatorics Sum_{k=0..n} (k-1)^2 D_n(k)=n!, Mathematics Stack Exchange, Jun 06 2017
• Paul 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, and 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.
• Index entries for sequences related to permutations with fixed points

Crossrefs

Mirror of triangle A098825.

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

Cf. A055137, A008291, A098558.

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. A000023, A133314, A238385, A320582, A335111.

Programs

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

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 *)
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 *)
T[n_, k_] := If[n<1, Boole[n==0 && k==0], T[n, k] = T[n-1, k-1] + T[n-1, k]*(n-1-k) + T[n-1, k+1]*(k+1)]; (* Michael Somos, Sep 13 2024 *)
T[0, 0]:=1; T[n_, 0]:=T[n, 0]=n  T[n-1, 0]+(-1)^n; T[n_, k_]:=T[n, k]=n/k T[n-1, k-1];
Flatten@Table[T[n, k], {n, 0, 9}, {k, 0, n}] (* Oliver Seipel, Nov 26 2024 *)

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

Formula

T(n, k) = T(n-1, k)*n + binomial(n, k)*(-1)^(n-k) = T(n, k-1)/k + binomial(n, k)*(-1)^(n-k)/(n-k+1) = T(n-1, k-1)*n/k = T(n-k, 0)*binomial(n, k) = A000166(n-k)*binomial(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

E.g.f. for number of permutations with exactly k fixed points is x^k/(k!*exp(x)*(1-x)). - Vladeta Jovovic, Aug 25 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!, 0 <= k <= n. 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

Sum_{k=0..n} (k+1) * T(n,k) = A098558(n). - Alois P. Heinz, Mar 11 2022

From Alois P. Heinz, May 20 2023: (Start)

Sum_{k=0..n} (-1)^k * T(n,k) = A000023(n).

Sum_{k=0..n} (-1)^k * k * T(n,k) = A335111(n). (End)

T(n,k) = A145224(n,k)+A145225(n,k), refined by even and odd perms. - R. J. Mathar, Jul 06 2023

Extensions

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