# Number of ways to arrange n numbers in k groups

1. Feb 9, 2016

### 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 in to 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?

2. Feb 9, 2016

### 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.

3. Feb 10, 2016

### ENgez

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

4. Feb 10, 2016

### MrAnchovy

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)!}$

5. Feb 10, 2016

### 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.

6. Feb 10, 2016

### MrAnchovy

Then multiply the answer I gave by the number of ways to shuffle k groups which is simply k!.
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.