login
Triangle T(n,k) = n!*binomial(n-1, k-1) for 1 <= k <= n, read by rows.
6

%I #49 Sep 08 2022 08:45:41

%S 1,2,2,6,12,6,24,72,72,24,120,480,720,480,120,720,3600,7200,7200,3600,

%T 720,5040,30240,75600,100800,75600,30240,5040,40320,282240,846720,

%U 1411200,1411200,846720,282240,40320,362880,2903040,10160640,20321280,25401600,20321280,10160640,2903040,362880

%N Triangle T(n,k) = n!*binomial(n-1, k-1) for 1 <= k <= n, read by rows.

%C Partition {1,2,...,n} into m subsets, arrange (linearly order) the elements within each subset, then arrange the subsets. - _Geoffrey Critzer_, Mar 05 2010

%C From _Dennis P. Walsh_, Nov 26 2011: (Start)

%C Number of ways to arrange n different books in a k-shelf bookcase leaving no shelf empty.

%C 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.

%C Equivalently, T(n,k) is the number of ways to stack n different alphabet blocks into k labeled stacks.

%C 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.

%C 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.

%C (End)

%C 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

%C 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

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 98

%H G. C. Greubel, <a href="/A156992/b156992.txt">Rows n = 1..50 of the triangle, flattened</a>

%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>

%F E.g.f. for column k is (x/(1-x))^k. - _Geoffrey Critzer_, Mar 05 2010

%F T(n,k) = A000142(n)*A007318(n-1,k-1). - _Dennis P. Walsh_, Nov 26 2011

%F Coefficient triangle of the polynomials p(n,x) = (n+1)!*hypergeom([-n],[],-x). - _Peter Luschny_, Apr 08 2015

%e The triangle starts:

%e 1;

%e 2, 2;

%e 6, 12, 6;

%e 24, 72, 72, 24;

%e 120, 480, 720, 480, 120;

%e 720, 3600, 7200, 7200, 3600, 720;

%e 5040, 30240, 75600, 100800, 75600, 30240, 5040;

%e 40320, 282240, 846720, 1411200, 1411200, 846720, 282240, 40320;

%e From _Dennis P. Walsh_, Nov 26 2011: (Start)

%e T(3,2) = 12 since there are 12 ways to arrange books b1, b2, and b3 on shelves <shelf1><shelf2>:

%e <b1><b2,b3>, <b1><b3,b2>, <b2><b1,b3>, <b2><b3,b1>,

%e <b3><b1,b2>, <b3><b2,b1>, <b2,b3><b1>, <b3,b2><b1>,

%e <b1,b3><b2>, <b3,b1><b2>, <b1,b2><b3>, <b2,b1><b3>.

%e (End)

%p seq(seq(n!*binomial(n-1,k-1),k=1..n),n=1..10); # _Dennis P. Walsh_, Nov 26 2011

%p with(PolynomialTools): p := (n,x) -> (n+1)!*hypergeom([-n],[],-x);

%p seq(CoefficientList(simplify(p(n,x)),x),n=0..5); # _Peter Luschny_, Apr 08 2015

%t Table[n!*Binomial[n-1, k-1], {n,10}, {k,n}]//Flatten

%o (Magma) [Factorial(n)*Binomial(n-1,k-1): k in [1..n], n in [1..10]]; // _G. C. Greubel_, May 10 2021

%o (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

%Y Cf. A002866 (row sums).

%Y Column 1 = A000142. Column 2 = A001286 * 2! = A062119. Column 3 = A001754 * 3!. Column 4 = A001755 * 4!. Column 5 = A001777 * 5!. Column 6 = A001778 * 6!. Column 7 = A111597 * 7!. Column 8 = A111598 * 8!. Cf. A105278. - _Geoffrey Critzer_, Mar 05 2010

%Y T(2n,n) gives A123072.

%K nonn,tabl

%O 1,2

%A _Roger L. Bagula_, Feb 20 2009