0
$\begingroup$

I am new to this and an amateur... please help.

My Question in practical terms: Given The three following inputs... determine the number of unique group arrangements as an ordered set.

INPUT: 'a' = Students 'b' = Groups 'c' = students per group

OUPUT ANSWER: 'z' as an integer

OUTPUT RULES: - All elements considered are ordered from left to right starting with the smallest number. - Order is not important... (1,2,3)=(2,3,1)=(3,2,1)=(3,1,2)=(1,3,2)=(2,1,3)...THEREFORE (1,2,3) is the only unique group that is to be counted.

Problem Example #1: I have 12 students that I need to arrange into 4 groups. I want the 4 groups to each contain 3 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 880 ordered arrangements. [Output Format: (1,2,3)(4,5,6)(7,8,9)(10,11,12)]

Problem Example #2: I have 12 students that I need to arrange into 3 groups. I want the 3 groups to each contain 2 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 13,860 ordered arrangements. [Output Format: (1,4)(3,6)(7,11)]

Problem Example #3: I have 24 students that I need to arrange into 3 groups. I want the 3 groups to each contain 6 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 125,847,260 ordered arrangements. [Output Format: (1,2,3,4,5,6)(9,10,11,12,13)(15,16,17,18,19,20)]

Unless I am mistaken, these are not 'combinations' or 'permutation's or 'complete sets' or 'hoyosa index'. So, for lack of better terms I am calling them ordered sets within ordered groups for now.

Is there a known formula to generate the answer without generating all possible solutions and searching?

20130822---ADDENDUM--- The numbers provided are accurate. The closest description tat I can call relate this to would be "Independent Edge Set AKA Matching"... except that I BELIEVE matching has a limit of two students per group. Sticking to the "Two Students per group" this can be determined using factorials similar to those you have provided. HOWEVER, I cannot find a formula that allows for the three INPUTS a,b,c as provided and ONLY accounts for unique ordered sets.

Using Problem Example #2: 12 Students (a), 2 groups (b), 3 students (c), = 13,860 unique ordered sets Set #1[(1,2,3,)(4,5,6)] Set #2[(1,2,3,)(4,5,7)] Set #3[(1,2,3,)(4,5,8)] ... Set #13,860 [(7,8,9)(10,11,12)]

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are your numbers right? I got for example 1 Binomial[12, 3]*Binomial[9, 3]*Binomial[6, 3]=369600, which is by the way 12!/3!^4. $\endgroup$
    – A.Schulz
    Aug 22, 2013 at 7:02
  • 1
    $\begingroup$ @A.Schulz And then you should aditionally divide by 4! since the order of the subsets does not seem to matter? Anyhow that is 15400, which again differs from the number given. $\endgroup$
    – Hendrik Jan
    Aug 22, 2013 at 7:51
  • $\begingroup$ This is largely a combinations problem. @HendrikJan "as an ordered set" might imply that the order matters. If it simply means that we sort them, alternatively to your method, you can fix an arbitrary number into one of the sets at each step, getting you to the same answer, i.e. got 12 -> fix 1 -> pick other 2 -> got 9 -> fix 1 -> pick other 2 -> got 6 -> fix 1 -> pick other 2, which is 11C2*8C2*5C2 = 15400. $\endgroup$
    – Bernhard Barker
    Aug 22, 2013 at 11:33
  • $\begingroup$ Is there a name for the formula you all reference. I would like to read up on it, as well as see a list of sets it produces to do a comparison. THANK YOU FOR YOUR INPUT SO FAR :) $\endgroup$
    – Tim
    Aug 22, 2013 at 15:50

1 Answer 1

Reset to default
2
$\begingroup$

Here the explanation for the numbers we found in the comments, which unfortunately do not match yours. If you have additional explanations I can delete this answer, or perhaps improve.

Goal: given $a$ students, make $b$ groups, each consisting of $c$ persons, $bc \le a$. What is the number of possibilities?

My assumptions, the groups are unordered, so $(1,2,3)$ is the same group as $(3,1,2)$. Also the solution $(1,2)(3,4)$ is equal to $(3,4)(1,2)$

Put your students in a row: $a!$ possibilities. The first $b$ students form the first group, the next $b$ students the second group, etc. The order in the line-up between each group of students does not matter, so we have to divide by th1s number of possibilities which is $(c!)^b$. Again we divide by $(a-bc)!$ the number of permutations of the not chosen ones. Also, the order of the groups themselves does not matter, we additionally divide by $b!$.

Answer: $a!\;/\;{(c!)^b (a-bc)! \;b!}$

Another way of obtaining the same number. Choose a group of $c$ students from total $a$, then a group of $c$ students from the remaining $c-b$, etc. This can be done in ${a \choose c}{a-c\choose c}\dots{a-c(b-1)\choose c}$. Again I divide by the possible orderings of the groups which is $b!$. Thus $\frac{a!}{c!(a-c)!}\frac{(a-c)!}{c!(a-2c)!}\dots \frac{(a-(b-1)c)!}{c!(a-bc)!} / b!$

Your first example $a=12$, $b=4$, $c=3$. You have 880, this number is 15400.

Second example $a=12$, $b=3$, $c=2$. 13680, we agree.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.