OFFSET
1,2
COMMENTS
Partition {1,2,...,n} into m subsets, arrange (linearly order) the elements within each subset, then arrange the subsets. - Geoffrey Critzer, Mar 05 2010
From Dennis P. Walsh, Nov 26 2011: (Start)
Number of ways to arrange n different books in a k-shelf bookcase leaving no shelf empty.
There are n! ways to arrange the books in one long line. With ni denoting the number of books for shelf i, we have n = n1 + n2 + ... + nk. Since the number of compositions of n with k summands is binomial(n-1,k-1), we obtain T(n,k) = n!*binomial(n-1,k-1) for the number of ways to arrange the n books on the k shelves.
Equivalently, T(n,k) is the number of ways to stack n different alphabet blocks into k labeled stacks.
Also, T(n,k) is the number of injective functions f:[n]->[n+k] such that (i) the pre-image of (n+j) exists for j=1..k and (ii) f has no fixed points, that is, for all x, f(x) does not equal x.
T(n,k) is the number of labeled, rooted forests that have (i) exactly k roots, (ii) each root labeled larger than any nonroot, (iii) each root with exactly one child node, (iv) n non-root nodes, and (v) at most one child node for each node in the forest.
(End)
Essentially, the triangle given by (2,1,3,2,4,3,5,4,6,5,7,6,8,7,9,8,...) DELTA (2,1,3,2,4,3,5,4,6,5,7,6,8,7,9,8,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 29 2011
T(n,j+k) = Sum_{i=j..n-k} binomial(n,i)*T(i,j)*T(n-i,k). - Dennis P. Walsh, Nov 29 2011
REFERENCES
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 98
LINKS
G. C. Greubel, Rows n = 1..50 of the triangle, flattened
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
FORMULA
E.g.f. for column k is (x/(1-x))^k. - Geoffrey Critzer, Mar 05 2010
Coefficient triangle of the polynomials p(n,x) = (n+1)!*hypergeom([-n],[],-x). - Peter Luschny, Apr 08 2015
EXAMPLE
The triangle starts:
1;
2, 2;
6, 12, 6;
24, 72, 72, 24;
120, 480, 720, 480, 120;
720, 3600, 7200, 7200, 3600, 720;
5040, 30240, 75600, 100800, 75600, 30240, 5040;
40320, 282240, 846720, 1411200, 1411200, 846720, 282240, 40320;
From Dennis P. Walsh, Nov 26 2011: (Start)
T(3,2) = 12 since there are 12 ways to arrange books b1, b2, and b3 on shelves <shelf1><shelf2>:
<b1><b2,b3>, <b1><b3,b2>, <b2><b1,b3>, <b2><b3,b1>,
<b3><b1,b2>, <b3><b2,b1>, <b2,b3><b1>, <b3,b2><b1>,
<b1,b3><b2>, <b3,b1><b2>, <b1,b2><b3>, <b2,b1><b3>.
(End)
MAPLE
seq(seq(n!*binomial(n-1, k-1), k=1..n), n=1..10); # Dennis P. Walsh, Nov 26 2011
with(PolynomialTools): p := (n, x) -> (n+1)!*hypergeom([-n], [], -x);
seq(CoefficientList(simplify(p(n, x)), x), n=0..5); # Peter Luschny, Apr 08 2015
MATHEMATICA
Table[n!*Binomial[n-1, k-1], {n, 10}, {k, n}]//Flatten
PROG
(Magma) [Factorial(n)*Binomial(n-1, k-1): k in [1..n], n in [1..10]]; // G. C. Greubel, May 10 2021
(Sage) flatten([[factorial(n)*binomial(n-1, k-1) for k in (1..n)] for n in (1..10)]) # G. C. Greubel, May 10 2021
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Roger L. Bagula, Feb 20 2009
STATUS
approved