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

1, 2, 2, 3, 6, 6, 4, 12, 24, 24, 5, 20, 60, 120, 120, 6, 30, 120, 360, 720, 720, 7, 42, 210, 840, 2520, 5040, 5040, 8, 56, 336, 1680, 6720, 20160, 40320, 40320, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800

Offset: 1

Author

David Wasserman, Mar 13 2003

Keywords

• easy
• nonn
• tabl

Comments

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

Has many diagonals in common with A105725. - Zerinvary Lajos, Apr 14 2006

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

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

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

Reversal of the triangle by rows = (n+1) * n-th row of triangle A094587. - Gary W. Adamson, May 03 2009

From Geoffrey Critzer, May 06 2009: (Start)

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).

Northwest corner:

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

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

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

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

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

...

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)

Cf. [Hardy and Wright], Theorem 34.

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

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

Examples

			Triangle begins:
  1;
  2,  2;
  3,  6,   6;
  4, 12,  24,  24;
  5, 20,  60, 120, 120;
  6, 30, 120, 360, 720, 720;
Square begins:
    1,   2,    3,    4,     5, ...
    2,   6,   12,   20,    30, ...
    6,  24,   60,  120,   210, ...
   24, 120,  360,  840,  1680, ...
  120, 720, 2520, 6720, 15120, ...
		

References

• G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Fifth edition, 1979, p. 64.
• O. Rigge, 9th Congr. Math. Scan., Helsingfors, 1938, Mercator, 1939, pp. 155-160.

Links

• G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened
• Mohammad K. Azarian, Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141. See Theorem 2.1 (iii), p. 131.
• N. Saradha and T. N. Shorey, Almost Squares and Factorisations in Consecutive Integers, Compositio Mathematica 138 (1) (2003) 113-124.
• Eric Weisstein's World of Mathematics, Falling Factorial.

Crossrefs

Cf. A007318, A000142, A075363.

Same as A008279 for k>0.

Cf. A094587. - Gary W. Adamson, May 03 2009

Appears in A167546. - Johannes W. Meijer, Nov 12 2009

Programs

Mathematica

Flatten[Table[n!/(n-k)!, {n, 10}, {k, n}]] (* or, from version 7: *)
Flatten[Table[FactorialPower[n, k], {n, 10}, {k, n}]]  (* Jean-François Alcover, Jun 17 2011, updated Sep 29 2016 *)

PARI

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

Formula

As a triangle: T(n,k) = k!*binomial(n,k) = n!/(n-k)!, 1 <= k <= n. - Michael Somos, Apr 05 2003

E.g.f.: exp(x)*x*y/(1-x*y). - Michael Somos, Apr 05 2003

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