login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A156992 Triangle T(n,k) = n!*binomial(n-1,k-1) read by rows, 1 <= k <= n. 5
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, 362880, 2903040, 10160640, 20321280 (list; table; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..40.

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

T(n,k) = A000142(n)*A007318(n-1,k-1). - Dennis P. Walsh, Nov 26 2011

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;

362880, 2903040, 10160640, 20321280, 25401600, 20321280, 10160640, 2903040, 362880;

3628800, 32659200, 130636800, 304819200, 457228800, 457228800, 304819200, 130636800, 32659200, 3628800; ...

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

Clear[t, n, m]; t[n_, m_] = n!*Binomial[n - 1, m - 1];

Table[Table[t[n, m], {m, 1, n}], {n, 1, 10}]; Flatten[%]

CROSSREFS

Cf. A002866 (row sums).

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

T(2n,n) gives A123072.

Sequence in context: A281351 A241669 A178802 * A285529 A219694 A054481

Adjacent sequences:  A156989 A156990 A156991 * A156993 A156994 A156995

KEYWORD

nonn,tabl

AUTHOR

Roger L. Bagula, Feb 20 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 17 14:12 EST 2018. Contains 299296 sequences. (Running on oeis4.)