[Solved]: Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

Problem Detail: 

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)]

Asked By : Tim

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13861

3.2K people like this

 Download Related Notes/Documents