|
|
A008279
|
|
Triangle T(n,k) = n!/(n-k)! (0 <= k <= n) read by rows, giving number of permutations of n things k at a time.
|
|
117
|
|
|
1, 1, 1, 1, 2, 2, 1, 3, 6, 6, 1, 4, 12, 24, 24, 1, 5, 20, 60, 120, 120, 1, 6, 30, 120, 360, 720, 720, 1, 7, 42, 210, 840, 2520, 5040, 5040, 1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320, 1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Also called permutation coefficients.
Also falling factorials triangle A068424 with column a(n,0)=1 and row a(0,1)=1 otherwise a(0,k)=0, added. - Wolfdieter Lang, Nov 07 2003
The higher-order exponential integrals E(x,m,n) are defined in A163931; for information about the asymptotic expansion of E(x,m=1,n) see A130534. The asymptotic expansions for n = 1, 2, 3, 4, ..., lead to the right hand columns of the triangle given above. - Johannes W. Meijer, Oct 16 2009
The number of injective functions from a set of size k to a set of size n. - Dennis P. Walsh, Feb 10 2011
The number of functions f from {1,2,...,k} to {1,2,...,n} that satisfy f(x) >= x for all x in {1,2,...,k}. - Dennis P. Walsh, Apr 20 2011
The e.g.f.s enumerating the faces of the permutohedra / permutahedra, Perm(s,t;x) = [e^(sx)-1]/[s-t(e^(sx)-1)], (cf. A090582 and A019538) and the stellahedra / stellohedra, St(s,t;x) = [s e^((s+t)x)]/[s-t(e^(sx)-1)], (cf. A248727) given in Toric Topology satisfy exp[u*d/dt] St(s,t;x) = St(s,u+t;x) = [e^(ux)/(1-u*Perm(s,t;x))]*St(s,t;x), where e^(ux)/(1-uy) is a bivariate e.g.f. for the row polynomials of this entry and A094587. Equivalently, d/dt St = (x+Perm)*St and d/dt Perm = Perm^2, or d/dt log(St) = x + Perm and d/dt log(Perm) = Perm. - Tom Copeland, Nov 14 2016
T(n, k)/n! are the coefficients of the n-th exponential Taylor polynomial, or truncated exponentials, which was proved to be irreducible by Schur. See Coleman link. - Michel Marcus, Feb 24 2020
|
|
REFERENCES
|
CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 176; 31st ed., p. 215, Section 3.3.11.1.
Maple V Reference Manual, p. 490, numbperm(n,k).
|
|
LINKS
|
V. Buchstaber and T. Panov Toric Topology, arXiv:1210.2368v3 [math.AT], 2014.
J. Goldman, J. Haglund, Generalized rook polynomials, J. Combin. Theory A91 (2000), 509-530, 2-rook coefficients for k rooks on the 1xn board, all heights 1.
|
|
FORMULA
|
E.g.f.: Sum T(n,k) x^n/n! y^k = exp(x)/(1-x*y). - Vladeta Jovovic, Aug 19 2002
T(n, k) = n*T(n-1, k-1) = k*T(n-1, k-1)+T(n-1, k) = n*T(n-1, k)/(n-k) = (n-k+1)*T(n, k-1). - Henry Bottomley, Mar 29 2001
T(n, k) = n!/(n-k)! if n >= k >= 0, otherwise 0.
G.f. for k-th column k!*x^k/(1-x)^(k+1), k >= 0.
E.g.f. for n-th row (1+x)^n, n >= 0.
Sum T(n, k)x^k = permanent of n X n matrix a_ij = (x+1 if i=j, x otherwise). - Michael Somos, Mar 05 2004
Ramanujan psi_1(k, x) polynomials evaluated at n+1. - Ralf Stephan, Apr 16 2004
The triangle is the binomial transform of an infinite matrix with (1, 1, 2, 6, 24, ...) in the main diagonal and the rest zeros. - Gary W. Adamson, Nov 20 2006
G.f.: 1/(1-x-xy/(1-xy/(1-x-2xy/(1-2xy/(1-x-3xy/(1-3xy/(1-x-4xy/(1-4xy/(1-... (continued fraction). - Paul Barry, Feb 11 2009
T(n,k) = Sum_{j=0..k} binomial(k,j)*T(x,j)*T(y,k-j) for x+y = n. - Dennis P. Walsh, Feb 10 2011
For n >= 2 and m >= 2, Sum_{k=0..m-2} S2(n, k+2)*T(m-2, k) = Sum_{p=0..n-2} m^p. S2(n,k) are the Stirling numbers of the second kind A008277. - Tony Foster III, Jul 23 2019
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
1, 2, 2;
1, 3, 6, 6;
1, 4, 12, 24, 24;
1, 5, 20, 60, 120, 120;
1, 6, 30, 120, 360, 720, 720;
1, 7, 42, 210, 840, 2520, 5040, 5040;
1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320;
1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880;
1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800;
...
For example, T(4,2)=12 since there are 12 injective functions f:{1,2}->{1,2,3,4}. There are 4 choices for f(1) and then, since f is injective, 3 remaining choices for f(2), giving us 12 ways to construct an injective function. - Dennis P. Walsh, Feb 10 2011
For example, T(5,3)=60 since there are 60 functions f:{1,2,3}->{1,2,3,4,5} with f(x) >= x. There are 5 choices for f(1), 4 choices for f(2), and 3 choices for f(3), giving us 60 ways to construct such a function. - Dennis P. Walsh, Apr 30 2011
|
|
MAPLE
|
with(combstruct): for n from 0 to 10 do seq(count(Permutation(n), size=m), m = 0 .. n) od; # Zerinvary Lajos, Dec 16 2007
seq(print(seq(pochhammer(n-k+1, k), k=0..n)), n=0..6); # Peter Luschny, Mar 26 2015
|
|
MATHEMATICA
|
Table[CoefficientList[Series[(1 + x)^m, {x, 0, 20}], x]* Table[n!, {n, 0, m}], {m, 0, 10}] // Grid - Geoffrey Critzer, Mar 16 2010
Table[ Pochhammer[n - k + 1, k], {n, 0, 9}, {k, 0, n}] // Flatten (* or *)
Table[ FactorialPower[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 18 2013, updated Jan 28 2016 *)
|
|
PROG
|
(PARI) {T(n, k) = if( k<0 || k>n, 0, n!/(n-k)!)}; /* Michael Somos, Nov 14 2002 */
(PARI) {T(n, k) = my(A, p); if( k<0 || k>n, 0, if( n==0, 1, A = matrix(n, n, i, j, x + (i==j)); polcoeff( sum(i=1, n!, if( p = numtoperm(n, i), prod(j=1, n, A[j, p[j]]))), k)))}; /* Michael Somos, Mar 05 2004 */
(Haskell)
a008279 n k = a008279_tabl !! n !! k
a008279_row n = a008279_tabl !! n
a008279_tabl = iterate f [1] where
f xs = zipWith (+) ([0] ++ zipWith (*) xs [1..]) (xs ++ [0])
(Sage)
for n in range(8): [falling_factorial(n, k) for k in (0..n)] # Peter Luschny, Mar 26 2015
(Magma) /* As triangle */ [[Factorial(n)/Factorial(n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 11 2015
|
|
CROSSREFS
|
T(n,0)=A000012, T(n,1)=A000027, T(n+1,2)=A002378, T(n,3)=A007531, T(n,4)=A052762, and T(n,n)=A000142.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|