Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of ways to arrange n numbers in k groups

  1. Feb 9, 2016 #1
    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 [tex](k!)^{\frac{k}{n}}(\frac{k}{n}!)[/tex]

    I understand the term [tex](\frac{k}{n}!)[/tex]

    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. jcsd
  3. Feb 9, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Feb 10, 2016 #3
    my mistake, every k/n is supposed to be n/k.
     
  5. Feb 10, 2016 #4
    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)!} ##
     
  6. Feb 10, 2016 #5
    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.
     
  7. Feb 10, 2016 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of ways to arrange n numbers in k groups
Loading...