login
Triangle of falling factorials, read by rows: T(n, k) = n*(n-1)*...*(n-k+1), n > 0, 1 <= k <= n.
25

%I #92 Aug 20 2024 01:57:03

%S 1,2,2,3,6,6,4,12,24,24,5,20,60,120,120,6,30,120,360,720,720,7,42,210,

%T 840,2520,5040,5040,8,56,336,1680,6720,20160,40320,40320,9,72,504,

%U 3024,15120,60480,181440,362880,362880,10,90,720,5040,30240,151200,604800,1814400,3628800,3628800

%N Triangle of falling factorials, read by rows: T(n, k) = n*(n-1)*...*(n-k+1), n > 0, 1 <= k <= n.

%C Triangle in which the n-th row begins with n and the k-th term is obtained by multiplying the (k-1)-th term by (n-k+1) until n-k+1 = 1. - _Amarnath Murthy_, Nov 11 2002

%C Has many diagonals in common with A105725. - _Zerinvary Lajos_, Apr 14 2006

%C Also: the square array of rising factorials A(n,k) = n*(n+1)*(n+2)*...*(n+k-1) read by antidiagonals downwards. There are no perfect squares in T(n,k) for k >= 2 [see Rigge]. T(n,k) is divisible by a prime exceeding k, if n >= 2*k [see Saradha and Shorey]. - _R. J. Mathar_, May 02 2007

%C T(n,k) is the number of injective functions f from {1,...,k} into {1,...,n}, since there are n choices for f(1), then (n-1) choices for f(2), ... and (n-k+1) choices for f(k). E.g., T(3,2)=6 because there are exactly 6 injective functions f:{1,2}->{1,2,3}, namely, f1={(1,1),(2,2)}, f2={(1,1),(2,3)}, f3={(1,2),(2,1)}, f4={(1,2),(2,3)}, f5={(1,3),(2,1)} and f6={(1,3),(2,2)}. - _Dennis P. Walsh_, Oct 18 2007

%C Permuted words defined by the connectivity of regular simplices are related to T by T = A135278 * (1!, 2!, 3!, 4!, ...). E.g., for T(4,k) with k-1 = simplex number, label the vertices of a tetrahedron with a, b, c, d, then the 0-simplex, the points, a,b,c,d gives 4 * 1 = 4 words; the 1-simplex, the edges: (ab or ba), (ac or ca), (ad or da), (bc or cb), (bd or db), (cd or dc) gives 6 * 2 = 12 words; the 2-simplex, the faces: (abc or ...), (acd or ...), (adb or ...), (bcd or ...) gives 4 * 6 = 24 words; the 3-simplex, (abcd or ....) gives 1 * 24 = 24 words. - _Tom Copeland_, Dec 08 2007

%C Reversal of the triangle by rows = (n+1) * n-th row of triangle A094587. - _Gary W. Adamson_, May 03 2009

%C From _Geoffrey Critzer_, May 06 2009: (Start)

%C The rectangular array R(n,k), read by diagonals is the number of ways n people can queue up in k (possibly empty) distinct queues. R(n,k) = (n+k-1)!/(k-1)!; R(n,k) = (n+k-1)*R(n-1,k).

%C Northwest corner:

%C 1, 2, 3, 4, 5, ...;

%C 2, 6, 12, 20, 30, ...;

%C 6, 24, 60, 120, 210, ...;

%C 24, 120, 360, 840, 1680, ...;

%C 120, 720, 2520, 6720, 15120, ...;

%C ...

%C Example: R(2,2)=6 because there are six ways that two people can get in line at a fast food restaurant that has two order windows open. Let 1 and 2 represent the two people and a | will separate the lines. 12|; 21|; |12; |21; 1|2; 2|1. (End)

%C Cf. [Hardy and Wright], Theorem 34.

%C The e.g.f. of the Norlund generalized Bernoulli (Appell) polynomials of order m, NB(n,x;m), is given by exponentiation of the e.g.f. of the Bernoulli numbers, i.e., multiple binomial self-convolutions of the Bernoulli numbers, through the e.g.f. exp[NB(.,x;m)t] = [t/(e^t-1)]^(m+1) * e^(xt). Norlund gave the relation to the factorials (x-1)!/(x-1-k)! = (x-1) ... (x-k) = NB(k,x;k), so T(n,k) = NB(k,n+1;k). - _Tom Copeland_, Oct 01 2015

%C T(n,k) is the number of sequences without repetition (partial permutations) of k elements taken from an n-set. For sequences with repetition (k-tuples) cf. A075363. - _Manfred Boergens_, Jun 18 2023

%D G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Fifth edition, 1979, p. 64.

%D O. Rigge, 9th Congr. Math. Scan., Helsingfors, 1938, Mercator, 1939, pp. 155-160.

%H G. C. Greubel, <a href="/A068424/b068424.txt">Table of n, a(n) for the first 100 rows, flattened</a>

%H Mohammad K. Azarian, <a href="https://doi.org/10.12988/imf.2022.912321">Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions</a>, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141. See Theorem 2.1 (iii), p. 131.

%H N. Saradha and T. N. Shorey, <a href="http://dx.doi.org/10.1023/A:1025480729778">Almost Squares and Factorisations in Consecutive Integers</a>, Compositio Mathematica 138 (1) (2003) 113-124.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FallingFactorial.html">Falling Factorial.</a>

%F As a triangle: T(n,k) = k!*binomial(n,k) = n!/(n-k)!, 1 <= k <= n. - _Michael Somos_, Apr 05 2003

%F E.g.f.: exp(x)*x*y/(1-x*y). - _Michael Somos_, Apr 05 2003

%F As a square: A(n,k) = (n+k-1)!/(k-1)!, 1 <= k <= n. - _Ron L.J. van den Burg_, Nov 28 2021

%e Triangle begins:

%e 1;

%e 2, 2;

%e 3, 6, 6;

%e 4, 12, 24, 24;

%e 5, 20, 60, 120, 120;

%e 6, 30, 120, 360, 720, 720;

%e Square begins:

%e 1, 2, 3, 4, 5, ...

%e 2, 6, 12, 20, 30, ...

%e 6, 24, 60, 120, 210, ...

%e 24, 120, 360, 840, 1680, ...

%e 120, 720, 2520, 6720, 15120, ...

%t Flatten[Table[n!/(n-k)!, {n, 10}, {k, n}]] (* or, from version 7: *)

%t Flatten[Table[FactorialPower[n, k], {n, 10}, {k, n}]] (* _Jean-François Alcover_, Jun 17 2011, updated Sep 29 2016 *)

%o (PARI) T(n,k)=if(k<1 || k>n,0,n!/(n-k)!)

%Y Cf. A007318, A000142, A075363.

%Y Same as A008279 for k>0.

%Y Cf. A094587. - _Gary W. Adamson_, May 03 2009

%Y Appears in A167546. - _Johannes W. Meijer_, Nov 12 2009

%K easy,nonn,tabl

%O 1,2

%A _David Wasserman_, Mar 13 2003