Number of ways to arrange n numbers in k groups

[ENgez]

Hello,

I was given a question (not a HW question..) in which i was asked to calculate the number of ways to sort n numbers into k groups, where for any two groups, the elements of one group are all smaller or larger than the elements of the other group.

The answer is supposed to be $$(k!)^{\frac{k}{n}}(\frac{k}{n}!)$$

I understand the term $$(\frac{k}{n}!)$$

as the it is the number of ways to arrange the groups. What I do not understand is the power of the first term.
Can anyone give me an intuitive answer where it comes from?

 

[andrewkirk]

What is your understanding of the meaning of $(\frac{k}{n}!)$?

Since $\frac{k}{n}$ will be a fraction less than 1, its factorial is not defined.

The answer I get for this problem is a single combination, which is nothing like the suggested answer. Perhaps there is more detail in the question - additional specifications - that has been omitted.

 

[ENgez]

my mistake, every k/n is supposed to be n/k.

 

[pbuk]

my mistake, every k/n is supposed to be n/k.

That doesn't help: x! is still only defined for integers. Furthermore, (k!)n/k is only going to yield an integer for a limited set of (n, k).

Assuming the groupings are not distinct so for instance {{1, 2}, {3, 4}} is identical to {{3, 4}, {1, 2}}, the correct answer is in fact a single binomial coefficient $\binom {n-1}{k-1}$

1. Sort the numbers into ascending order.
2. The problem can then be represented by partitioning a list of n star symbols into k groups separated by bars e.g. for (n=6, k=3) one solution is * | * * * | * *
3. Assuming each group must contain at least one number, the number of arrangements for such a "stars and bars" problem can easily be seen to be $\binom {n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k-2)!}$

 

[ENgez]

tnx for the reply, but the groups are distinct, as I am interested in the number of ways to shuffle them around.
you can assume that n/k is an integer.

 

[pbuk]

tnx for the reply, but the groups are distinct, as I am interested in the number of ways to shuffle them around.

Then multiply the answer I gave by the number of ways to shuffle k groups which is simply k!.

tnx for the reply, but the groups are distinct, as I am interested in the number of ways to shuffle them around.
you can assume that n/k is an integer.

Not necessary, however this makes me wonder whether the groups must be of equal size? If this is the case then the solution is trivial and I invite you to provide it - everything you need is in this thread.