|
%I #125 Jan 29 2022 12:18:31
%S 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,
%T 720,720,1,7,42,210,840,2520,5040,5040,1,8,56,336,1680,6720,20160,
%U 40320,40320,1,9,72,504,3024,15120,60480,181440,362880,362880
%N Triangle T(n,k) = n!/(n-k)! (0 <= k <= n) read by rows, giving number of permutations of n things k at a time.
%C Also called permutation coefficients.
%C 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
%C 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
%C The number of injective functions from a set of size k to a set of size n. - _Dennis P. Walsh_, Feb 10 2011
%C 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
%C T(n,k) = A181511(n,k) for k=1..n-1. - _Reinhard Zumkeller_, Nov 18 2012
%C 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
%C 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
%D CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 176; 31st ed., p. 215, Section 3.3.11.1.
%D Maple V Reference Manual, p. 490, numbperm(n,k).
%H T. D. Noe, <a href="/A008279/b008279.txt">Rows n = 0..100 of triangle, flattened</a>
%H J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.2010">Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure</a>, arXiv:1307.2010 [math.CO], 2013-2014.
%H V. Buchstaber and T. Panov <a href="https://arxiv.org/abs/1210.2368">Toric Topology</a>, arXiv:1210.2368v3 [math.AT], 2014.
%H R. F. Coleman, <a href="http://dx.doi.org/10.5169/seals-87891">On the Galois groups of the exponential Taylor polynomials</a>, L’Enseignement Mathématique 33, 183-189, (1987).
%H J. Goldman, J. Haglund, <a href="http://dx.doi.org/10.1006/jcta.2000.3113">Generalized rook polynomials</a>, J. Combin. Theory A91 (2000), 509-530, 2-rook coefficients for k rooks on the 1xn board, all heights 1.
%H R. L. Graham, D. E. Knuth, and O. Patashnik, <a href="https://notendur.hi.is/pgg/%28ebook-pdf%29%20-%20Mathematics%20-%20Concrete%20Mathematics.pdf">Concrete Mathematics: A Foundation for Computer Science, 2nd ed.</a> Reading, MA: Addison-Wesley, 1994.
%H Germain Kreweras, <a href="http://www.numdam.org/item?id=MSH_1963__3__31_0">Une dualité élémentaire souvent utile dans les problèmes combinatoires</a>, Mathématiques et Sciences Humaines 3 (1963) 31-41.
%H Wolfdieter Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LANG/lang.html">On generalizations of Stirling number triangles</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
%H OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>
%H Yuriy Shablya, Dmitry Kruchinin, <a href="http://elibrary.matf.bg.ac.rs/bitstream/handle/123456789/4699/Proceedings_Book_of_MICOPAM2018_11_11_2018.pdf?sequence=3#page=233">Euler-Catalan's Number Triangle and its Application</a>, Proceedings Book of Micropam (The Mediterranean International Conference of Pure & Applied Mathematics and Related Areas 2018), 212-215.
%H Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/NOLESSFN.pdf">Notes on no-less functions</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FallingFactorial.html">Falling Factorial</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F E.g.f.: Sum T(n,k) x^n/n! y^k = exp(x)/(1-x*y). - _Vladeta Jovovic_, Aug 19 2002
%F Equals A007318 * A136572. - _Gary W. Adamson_, Jan 07 2008
%F 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
%F T(n, k) = n!/(n-k)! if n >= k >= 0, otherwise 0.
%F G.f. for k-th column k!*x^k/(1-x)^(k+1), k >= 0.
%F E.g.f. for n-th row (1+x)^n, n >= 0.
%F 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
%F Ramanujan psi_1(k, x) polynomials evaluated at n+1. - _Ralf Stephan_, Apr 16 2004
%F E.g.f.: Sum T(n,k) x^n/n! y^k/k! = e^{x+xy}. - _Franklin T. Adams-Watters_, Feb 07 2006
%F 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
%F 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
%F 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
%F E.g.f (with k fixed): x^k*exp(x). - _Dennis P. Walsh_, Apr 20 2011
%F G.f. (with k fixed): k!*x^k/(1-x)^(k+1). - _Dennis P. Walsh_, Apr 20 2011
%F 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
%e Triangle begins:
%e 1;
%e 1, 1;
%e 1, 2, 2;
%e 1, 3, 6, 6;
%e 1, 4, 12, 24, 24;
%e 1, 5, 20, 60, 120, 120;
%e 1, 6, 30, 120, 360, 720, 720;
%e 1, 7, 42, 210, 840, 2520, 5040, 5040;
%e 1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320;
%e 1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880;
%e 1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800;
%e ...
%e 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
%e 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
%p with(combstruct): for n from 0 to 10 do seq(count(Permutation(n),size=m), m = 0 .. n) od; # _Zerinvary Lajos_, Dec 16 2007
%p seq(seq(n!/(n-k)!,k=0..n),n=0..10); # _Dennis P. Walsh_, Apr 20 2011
%p seq(print(seq(pochhammer(n-k+1,k),k=0..n)),n=0..6); # _Peter Luschny_, Mar 26 2015
%t Table[CoefficientList[Series[(1 + x)^m, {x, 0, 20}], x]* Table[n!, {n, 0, m}], {m, 0, 10}] // Grid - _Geoffrey Critzer_, Mar 16 2010
%t Table[ Pochhammer[n - k + 1, k], {n, 0, 9}, {k, 0, n}] // Flatten (* or *)
%t Table[ FactorialPower[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 18 2013, updated Jan 28 2016 *)
%o (PARI) {T(n, k) = if( k<0 || k>n, 0, n!/(n-k)!)}; /* _Michael Somos_, Nov 14 2002 */
%o (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 */
%o (Haskell)
%o a008279 n k = a008279_tabl !! n !! k
%o a008279_row n = a008279_tabl !! n
%o a008279_tabl = iterate f [1] where
%o f xs = zipWith (+) ([0] ++ zipWith (*) xs [1..]) (xs ++ [0])
%o -- _Reinhard Zumkeller_, Dec 15 2013, Nov 18 2012
%o (Sage)
%o for n in range(8): [falling_factorial(n,k) for k in (0..n)] # _Peter Luschny_, Mar 26 2015
%o (Magma) /* As triangle */ [[Factorial(n)/Factorial(n-k): k in [0..n]]: n in [0.. 15]]; // _Vincenzo Librandi_, Oct 11 2015
%Y Row sums give A000522.
%Y Cf. A001497, A001498, A136572.
%Y 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.
%Y Cf. A019538, A090582, A094587, A248727.
%K nonn,tabl,nice,easy,core
%O 0,5
%A _N. J. A. Sloane_
|
