|
%I #194 Jul 06 2023 06:21:01
%S 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 1854,1855,924,315,70,21,0,1,14833,14832,7420,2464,630,112,28,0,1,
%U 133496,133497,66744,22260,5544,1134,168,36,0,1,1334961,1334960,667485,222480,55650,11088,1890,240,45,0,1
%N Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points).
%C 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
%C 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
%C 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
%C 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
%C A refinement of this triangle is given by A036039. - _Tom Copeland_, Nov 06 2012
%C This triangle equals (A211229(2*n,2*k)) n,k >= 0. - _Peter Bala_, Dec 17 2014
%D 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).
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.
%D Arnold Kaufmann, Introduction à la combinatorique en vue des applications, Dunod, Paris, 1968. See p. 92.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
%H Alois P. Heinz, <a href="/A008290/b008290.txt">Rows n = 0..150, flattened</a> (first 51 rows from T. D. Noe)
%H Taha Akbari, <a href="http://math.stackexchange.com/q/2311800">Prove using combinatorics Sum_{k=0..n} (k-1)^2 D_n(k)=n!</a>, Mathematics Stack Exchange, Jun 06 2017
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Barry4/barry271.html">General Eulerian Polynomials as Moments Using Exponential Riordan Arrays</a>, Journal of Integer Sequences, 16 (2013), #13.9.6.
%H Stefano Capparelli, Margherita Maria Ferrari, Emanuele Munarini, and Norma Zagaglia Salvi, <a href="https://www.emis.de/journals/JIS/VOL21/Munarini/muna8.html">A Generalization of the "Problème des Rencontres"</a>, J. Int. Seq. 21 (2018), #18.2.8.
%H Bhadrachalam Chitturi and Krishnaveni K S, <a href="https://arxiv.org/abs/1601.04469">Adjacencies in Permutations</a>, arXiv preprint arXiv:1601.04469 [cs.DM], 2016. See Table 1.
%H S. K. Das and N. Deo, <a href="http://www.fq.math.ca/Scanned/25-3/das.pdf">Rencontres graphs: a family of bipartite graphs</a>, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
%H Robert W. Donley Jr, <a href="https://arxiv.org/abs/1905.01525">Binomial arrays and generalized Vandermonde identities</a>, arXiv:1905.01525 [math.CO], 2019.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000215/">The number of adjacencies of a permutation, 0 appended</a>, <a href="http://www.findstat.org/St000022">The number of fixed points of a permutation</a>
%H I. Kaplansky, <a href="http://dx.doi.org/10.1090/S0002-9904-1944-08261-X">Symbolic solution of certain problems in permutations</a>, Bull. Amer. Math. Soc., 50 (1944), 906-914.
%H J. Liese and J. Remmel, <a href="http://puma.dimai.unifi.it/21_2/10_Liese_Remmel.pdf">Q-analogues of the number of permutations with k-excedances</a>, PU. M. A. Vol. 21 (2010), No. 2, pp. 285-320 (see E_{n,0}(x) in Table 1 p. 291).
%H L. Takacs, <a href="http://dx.doi.org/10.1016/S0012-365X(81)80024-6">On the "problème des ménages"</a>, Discr. Math. 36 (3) (1981) 289-297, Table 2.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Rencontres_numbers">Rencontres numbers</a>.
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for sequences related to permutations with fixed points</a>
%F 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.
%F 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
%F From _Vladeta Jovovic_, Aug 12 2002: (Start)
%F O.g.f. for k-th column: (1/k!)*Sum_{i>=k} i!*x^i/(1+x)^(i+1).
%F O.g.f. for k-th row: k!*Sum_{i=0..k} (-1)^i/i!*(1-x)^i. (End)
%F E.g.f.: exp((y-1)*x)/(1-x). - _Vladeta Jovovic_, Aug 18 2002
%F 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
%F 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
%F 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
%F T(n,k) = Sum_{j=0..n} (-1)^(j-k)*binomial(j,k)*n!/j!. - _Paul Barry_, May 25 2006
%F 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.
%F 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
%F 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
%F From _Henk P. J. van Wijk_, Oct 29 2012: (Start)
%F T(n,k) = T(n-1,k)*(n-1-k) + T(n-1,k+1)*(k+1) for k=0 and
%F 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.
%F (End)
%F T(n,k) = A098825(n,n-k). - _Reinhard Zumkeller_, Dec 16 2013
%F Sum_{k=0..n} k^2 * T(n, k) = 2*n! if n > 1. - _Michael Somos_, Jun 06 2017
%F From _Tom Copeland_, Jul 26 2017: (Start)
%F 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).
%F 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!.
%F The formalism of A133314 applies to the pair of entries A008290 and A055137.
%F 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).
%F For more on the infinitesimal generator, noted by Bala below, see A238385. (End)
%F Sum_{k=0..n} k^m * T(n,k) = A000110(m)*n! if n >= m. - _Zhujun Zhang_, May 24 2019
%F Sum_{k=0..n} (k+1) * T(n,k) = A098558(n). - _Alois P. Heinz_, Mar 11 2022
%F From _Alois P. Heinz_, May 20 2023: (Start)
%F Sum_{k=0..n} (-1)^k * T(n,k) = A000023(n).
%F Sum_{k=0..n} (-1)^k * k * T(n,k) = A335111(n). (End)
%F T(n,k) = A145224(n,k)+A145225(n,k), refined by even and odd perms. - _R. J. Mathar_, Jul 06 2023
%e 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 Triangle begins:
%e 1
%e 0 1
%e 1 0 1
%e 2 3 0 1
%e 9 8 6 0 1
%e 44 45 20 10 0 1
%e 265 264 135 40 15 0 1
%e 1854 1855 924 315 70 21 0 1
%e 14833 14832 7420 2464 630 112 28 0 1
%e 133496 133497 66744 22260 5544 1134 168 36 0 1
%e ...
%e From _Peter Bala_, Feb 13 2017: (Start)
%e The infinitesimal generator has integer entries given by binomial(n,k)*(n-k-1)! for n >= 2 and 0 <= k <= n-2 and begins
%e 0
%e 0 0
%e 1 0 0
%e 2 3 0 0
%e 6 8 6 0 0
%e 24 30 20 10 0 0
%e ...
%e 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)
%p T:= proc(n,k) T(n, k):= `if`(k=0, `if`(n<2, 1-n, (n-1)*
%p (T(n-1, 0)+T(n-2, 0))), binomial(n, k)*T(n-k, 0))
%p end:
%p seq(seq(T(n, k), k=0..n), n=0..12); # _Alois P. Heinz_, Mar 15 2013
%t 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 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 *)
%o (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 */
%o (Haskell)
%o a008290 n k = a008290_tabl !! n !! k
%o a008290_row n = a008290_tabl !! n
%o a008290_tabl = map reverse a098825_tabl
%o -- _Reinhard Zumkeller_, Dec 16 2013
%Y Mirror of triangle A098825.
%Y Columns give A000166, A000240, A000387, A000449, A000475, A129135, A129136, A129149, A129153, A129217, A129218, A129238, A129255.
%Y Cf. A055137, A008291, A098558.
%Y Cf. A080955.
%Y Cf. A000012, A000142 (row sums), A000354.
%Y Cf. A170942. Sub-triangle of A211229.
%Y Cf. A092271, A111492, A211603, A238363.
%Y T(2n,n) gives A281262.
%Y Cf. A000023, A133314, A238385, A320582, A335111.
%K nonn,tabl,nice
%O 0,7
%A _N. J. A. Sloane_
%E Comments and more terms from _Michael Somos_, Apr 26 2000 and _Christian G. Bower_, Apr 26 2000
|
