|
|
A068424
|
|
Triangle of falling factorials, read by rows: T(n, k) = n*(n-1)*...*(n-k+1), n > 0, 1 <= k <= n.
|
|
25
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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
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
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
|
|
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
|
|
|
FORMULA
|
As a triangle: T(n,k) = k!*binomial(n,k) = n!/(n-k)!, 1 <= k <= n. - Michael Somos, Apr 05 2003
|
|
EXAMPLE
|
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, ...
|
|
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 *)
|
|
PROG
|
(PARI) T(n, k)=if(k<1 || k>n, 0, n!/(n-k)!)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|