A200472 Triangle T(n,k) is the number of ways to assign n people to k unlabeled groups of equal size.

1, 1, 1, 1, 0, 1, 1, 3, 0, 1, 1, 0, 0, 0, 1, 1, 10, 15, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 35, 0, 105, 0, 0, 0, 1, 1, 0, 280, 0, 0, 0, 0, 0, 1, 1, 126, 0, 0, 945, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 462, 5775, 15400, 0, 10395, 0, 0, 0, 0, 0, 1

Offset: 1

Author

Dennis P. Walsh, Nov 18 2011

Keywords

• nonn
• easy
• tabl

Comments

If k is not a factor of n, T(n,k) = 0. If k is a factor of n, T(n,k) = (n!/k!)/(n/k)!^k. If n is a multiple of k, we may obtain T(n,k) by arranging all n people in an ordered line, which can be done in n! ways. Peel off the first n/k people for "group 1", the next n/k people for "group 2", ..., and the last n/k people for "group k". Since the k groups are actually unlabeled, we must divide n! by k! Also, since the ordering of the n/k people within each of the k groups is not of importance, we must now divide by (n/k)!^k. Therefore, T(n,k) = (n!/k!)/(n/k)!^k.

Also, T(2n,n) provide the sequence consisting of the products of consecutive odd integers.

Examples

			Triangle T(n,k) begins
1;
1,   1;
1,   0,    1;
1,   3,    0,     1;
1,   0,    0,     0,   1;
1,  10,   15,     0,   0,     1;
1,   0,    0,     0,   0,     0,  1;
1,  35,    0,   105,   0,     0,  0,  1;
1,   0,  280,     0,   0,     0,  0,  0,  1;
1, 126,    0,     0, 945,     0,  0,  0,  0,  1;
1,   0,    0,     0,   0,     0,  0,  0,  0,  0,  1;
1, 462, 5775, 15400,   0, 10395,  0,  0,  0,  0,  0,  1;
...
T(6,2) = 10 since there are 10 ways to assign 6 people (A,B,C,D,E,F) into 2 groups of size 3. The assignments are {A,B,C}|{D,E,F}, {A,B,D}|{C,E,F}, {A,B,E}|{C,D,F}, {A,B,F}|{C,D,E}, {A,C,D}|{B,E,F}, {A,C,E}|{B,D,F}, {A,C,F}|{B,D,E}, {B,C,D}|{A,E,F}, {B,C,E}|{A,D,F}, and {B,C,F}|{A,D,E}.
		

Links

• Dennis P. Walsh, Note on assigning n people into k unlabeled groups of equal size

Crossrefs

T(2n,n) is A001147(n).

T(3n,n) is A025035(n).

T(4n,n) is A025036(n).

Row sums of T(n,k) provide A038041(n).

A200473 is A200472 with zeros removed.

Programs

Maple

T:= (n, k)-> `if`(modp(n, k)=0, n!/(k!*((n/k)!)^k), 0):
seq(seq(T(n, k), k=1..n), n=1..20);

Mathematica

nn=11;s=Sum[Exp[y x^i/i!]-1,{i,1,nn}];Range[0,nn]!CoefficientList[Series[s,{x,0,nn}],{x,y}]//Grid  (* Geoffrey Critzer, Sep 15 2012 *)

PARI

T(n,k) = if(n%k!=0, 0, (n!/k!)/((n/k)!)^k );
for (n=1,15, for (k=1,n, print1(T(n,k),", "));print());
/* Joerg Arndt, Sep 16 2012 */

Formula

For k that divide n, T(n,k) = (n!/k!)/((n/k)!)^k; otherwise, T(n,k) = 0.

E.g.f. when k is fixed: (1/k!) sum(j>=1, (x^j/j!)^k ).

E.g.f. for T(n*r,n): exp(x^r/r!).

T(2n,n) = (2n-1)!! = (2n-1)(2n-3)...(3)(1).