A199673 Number of ways to form k labeled groups, each with a distinct leader, using n people. Triangle T(n,k) = n!*k^(n-k)/(n-k)! for 1 <= k <= n.

1, 2, 2, 3, 12, 6, 4, 48, 72, 24, 5, 160, 540, 480, 120, 6, 480, 3240, 5760, 3600, 720, 7, 1344, 17010, 53760, 63000, 30240, 5040, 8, 3584, 81648, 430080, 840000, 725760, 282240, 40320, 9, 9216, 367416, 3096576, 9450000, 13063680, 8890560, 2903040, 362880

Offset: 1

Author

Dennis P. Walsh, Nov 08 2011

Keywords

• nonn
• easy
• tabl

Comments

T(n,1)=n since there are n choices for the leader of the single group. Also, T(n,n)=n! since each of the n groups consist solely of a leader and there are n! ways to assign the n people to the n labeled groups.

In general, T(n,k) = n!*k^(n-k)/(n-k)! since there are n!/(n-k)! ways to assign leaders to the k labeled groups and there are k^(n-k) ways to map the remaining (n-k) people to the k groups.

T(n,k) is the number of functions of [n] to an arbitrary k-subset of [n], where each of the k target values is used at least once.

The number of ways to distribute n different toys among k girls and k boys to that each girl gets exactly one toy. - Dennis P. Walsh, Sep 10 2012

Examples

			T(3,2)=12 since there are 12 ways to form group 1 and group 2, both with leaders, using people p1, p2, and p3, as illustrated below. The leader will be denoted Lj if person pj is designated the leader of the group.
Group 1   Group 2
{L1,p2}   {L3}
{L1,p3}   {L2}
{L1}      {L2,p3}
{L1}      {p2,L3}
{L2,p1}   {L3}
{L2,p3}   {L1}
{L2}      {L1,p3}
{L2}      {p1,L3}
{L3,p2}   {L1}
{L3,p1}   {L2}
{L3}      {L1,p2}
{L3}      {p1,L2}
First rows of triangle T(n,k):
  1;
  2,    2;
  3,   12,      6;
  4,   48,     72,      24;
  5,  160,    540,     480,     120;
  6,  480,   3240,    5760,    3600,      720;
  7, 1344,  17010,   53760,   63000,    30240,    5040;
  8, 3584,  81648,  430080,  840000,   725760,  282240,   40320;
  9, 9216, 367416, 3096576, 9450000, 13063680, 8890560, 2903040, 362880;
		

Links

• Joerg Arndt, Table of n, a(n) for n = 1..561
• George Kesidis, Takis Konstantopoulos, and Michael A. Zazanis, Age of information without service preemption, arXiv:2104.08050 [cs.PF], 2021.
• Dennis P. Walsh, Assigning people into labeled groups with leaders
• Dennis P. Walsh, Toy Story 2

Programs

Magma

[Factorial(n)*k^(n-k)/Factorial(n-k): k in [1..n], n in [1..9]];  // Bruno Berselli, Nov 09 2011

Maple

seq(seq(n!*k^(n-k)/(n-k)!, k=1..n), n=1..9);

Mathematica

nn = 10; a = y x Exp[x]; f[list_] := Select[list, # > 0 &]; Drop[Map[f, Range[0, nn]! CoefficientList[Series[1/(1 - a) , {x, 0, nn}], {x, y}]], 1] // Flatten  (* Geoffrey Critzer, Jan 21 2012 *)

PARI

T(n,k)=n!*k^(n-k)/(n-k)!;
/* print triangle: */
for (n=1, 15, for (k=1,n, print1(T(n,k),", ")); print() );
/* Joerg Arndt, Sep 21 2012 */

Formula

T(n,k) = n!*k^(n-k)/(n-k)! = k!*k^(n-k)*binomial(n,k) for 1 <= k <= n.

E.g.f.: (x*e^x)^k,for fixed k.

T(n,k1+k2) = Sum_{j=0..n} binomial(n,j)*T(j,k1)*T(n-j,k2).

T(n,1) = A000027(n);

T(n,2) = A001815(n);

T(n,3) = A052791(n);

Sum_{k=1..n} T(n,k) = A006153(n).

T(n,n) = A000142(n) = n!. - Dennis P. Walsh, Sep 10 2012