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
T(n,k) = A181511(n,k) for k=1..n-1. - Reinhard Zumkeller, Nov 18 2012
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
T. D. Noe, Rows n = 0..100 of triangle, flattened
J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013-2014.
V. Buchstaber and T. Panov Toric Topology, arXiv:1210.2368v3 [math.AT], 2014.
R. F. Coleman, On the Galois groups of the exponential Taylor polynomials, L’Enseignement Mathématique 33, 183-189, (1987).
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.
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.
Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires, Mathématiques et Sciences Humaines 3 (1963) 31-41.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers
Yuriy Shablya, Dmitry Kruchinin, Euler-Catalan's Number Triangle and its Application, Proceedings Book of Micropam (The Mediterranean International Conference of Pure & Applied Mathematics and Related Areas 2018), 212-215.
Dennis Walsh, Notes on no-less functions
Eric Weisstein's World of Mathematics, Falling Factorial
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
E.g.f.: Sum T(n,k) x^n/n! y^k/k! = e^{x+xy}. - Franklin T. Adams-Watters, Feb 07 2006
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
From Dennis P. Walsh, Apr 20 2011: (Start)
E.g.f (with k fixed): x^k*exp(x).
G.f. (with k fixed): k!*x^k/(1-x)^(k+1). (End)
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(seq(n!/(n-k)!, k=0..n), n=0..10); # Dennis P. Walsh, Apr 20 2011
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])
-- Reinhard Zumkeller, Dec 15 2013, Nov 18 2012
(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
(Python)
from math import factorial, isqrt, comb
def A008279(n): return factorial(a:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)))//factorial(a-n+comb(a+1, 2)) # Chai Wah Wu, Nov 13 2024
CROSSREFS
KEYWORD
AUTHOR
STATUS
approved