|
| |
|
|
A008290
|
|
Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points).
|
|
59
|
|
|
|
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). [From 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).
S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.
I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
|
|
|
LINKS
|
T. D. Noe, Rows n=0..50 of triangle, flattened
|
|
|
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. [From 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.
Contribution 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)
|
|
|
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!))}
|
|
|
CROSSREFS
|
Columns give A000166, A000240, A000387, A000449, A000475. Cf. A055137, A008291.
T(n,k) = binomial(n,k)*A000166(n-k).
Cf. A080955.
Cf. A000012, A000142, A000354.
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
|
| |
|
|
