# Combinatorial Solution to School Admission Interview Scheduling Problem

• erisedk
In summary, the three children, each accompanied by a guardian, can be interviewed one after the other subject to the condition that no child is interviewed before its guardian.
erisedk

## Homework Statement

Three children, each accompanied by a guardian, seek admission in a school. The principal wants to interview all the 6 persons one after the other subject to the condition that no child is interviewed before its
guardian. In how many ways can this be done ?

## The Attempt at a Solution

So, I read the solution to this problem, because I could only work it out with a lot of casework (I did get the right answer), but this question wasn't supposed to be that time consuming.

No. of ways = 6C2 * 4C2 * 2C2 = 90
That doesn't make much sense to me. Help?

Suppose the 6 people are C1,G1,C2,G2,C3,G3,
Think of the 6 of them standing in line waiting to see the principal.
There are 6 positions in which they can stand in the line.
Choose 2 of the 6 positions in the line for C1 and G1 to stand in, placing C1 behind G1.
That can be done in 6C2 ways.
That leaves 4 positions in the line.
Choose 2 of the remaining 4 positions in the line for C2 and G2 to stand in, putting C2 behind G2.
That can be done in 4C2 ways.
That leaves 2 positions in the line.
Choose 2 of the remaining 2 positions in the line for C3 and G3 to stand in, putting C3 behind G3.
That can be done in 2C2 "ways". i.e., just 1 way!

Last edited:
Thanks! That was pretty neat :)

It's even easier than that.
With no constraint, there are 6! orders. In what fraction of those are guardian 1 and child 1 in the right order? Ditto, guardian 2 and child 2? Are those two fractions independent (as in, independent events)? Etc.

They should be independent, or I could just use symmetry to justify independence. So, that'd be 6!/(2)^3. Which does give the same answer :)

erisedk said:
They should be independent, or I could just use symmetry to justify independence. So, that'd be 6!/(2)^3. Which does give the same answer :)
Exactly. For every arrangement in which G1 precedes C1 there is an otherwise identical arrangement in which C1 precedes G1, just by swapping them. Hence the independence.

Hmm...why do we not need to multiply the answer by 3! since there are 3 'couples' to chose from when placing them in 6C2 and so forth?

toforfiltum said:
Hmm...why do we not need to multiply the answer by 3! since there are 3 'couples' to chose from when placing them in 6C2 and so forth?
Which post are you responding to?

haruspex said:
Which post are you responding to?
No one in particular, maybe just all of the posts above, since all agreed upon the same solution.

toforfiltum said:
No one in particular, maybe just all of the posts above, since all agreed upon the same solution.
My solution in posts #4 and #6 did not involve 6C2, so it can't apply to that. I'll take it as referring to Edwin's solution in post #2.

Edwin took a particular pair and chose two places in the queue for that pair, then considered the next pair, etc.
The resulting ordering does not depend on the order in which the pairs were chosen. Any given ordering of the six can result from any ordering of selection of the three pairs. If you were to multiply by the number of orders in which the pairs were selected you would count each ordering of the six six times.

haruspex said:
My solution in posts #4 and #6 did not involve 6C2, so it can't apply to that. I'll take it as referring to Edwin's solution in post #2.

Edwin took a particular pair and chose two places in the queue for that pair, then considered the next pair, etc.
The resulting ordering does not depend on the order in which the pairs were chosen. Any given ordering of the six can result from any ordering of selection of the three pairs. If you were to multiply by the number of orders in which the pairs were selected you would count each ordering of the six six times.
Oh I see. So his method has covered all possibilities. I have some weakness with combinatorics, especially in cases like this when I don't know if I should multiply the choices of couples or not. I have trouble seeing that the method above has covered all possibilities.

Anyway, thanks.

toforfiltum said:
in cases like this when I don't know if I should multiply the choices of couples or not. I have trouble seeing that the method above has covered all possibilities.
You're not alone!

toforfiltum
haruspex said:
You're not alone!
It's nice to know, because it's frustrating. I have invested a lot of time doing lots of problems like this; I've gotten better but it's still not intuitive.

If you don't mind, can you explain the other solution? I don't understand where the 2^3 come from. Are they the 3 couples grouped together?

toforfiltum said:
It's nice to know, because it's frustrating. I have invested a lot of time doing lots of problems like this; I've gotten better but it's still not intuitive.

If you don't mind, can you explain the other solution? I don't understand where the 2^3 come from. Are they the 3 couples grouped together?
There are 6! orderings of the six people. In half of these, G1 and C1 are in the wrong order, so rule those out. In half of the remainder, G2 and C2 are in the wrong order, getting us down to 6!/4. Finally, cut out those where G3 and C3 are in the wrong order.

haruspex said:
There are 6! orderings of the six people. In half of these, G1 and C1 are in the wrong order, so rule those out. In half of the remainder, G2 and C2 are in the wrong order, getting us down to 6!/4. Finally, cut out those where G3 and C3 are in the wrong order.
This solution is new to me, so I have trouble understanding it. When you say that in half of the orderings, G1 and C1 are in the wrong order, is the working suppose to be like this:
( 5+4+3+2+1) x 4!

or is it just common sense? I can't 'see' it.

toforfiltum said:
This solution is new to me, so I have trouble understanding it. When you say that in half of the orderings, G1 and C1 are in the wrong order, is the working suppose to be like this:
( 5+4+3+2+1) x 4!

or is it just common sense? I can't 'see' it.
Consider any ordering of the six. If G1 and C1 are in the wrong order you can swap them to produce an ordering of the six in which they are in the right order, and vice versa. So there must be the same number of 6-sequences with G1 and C1 in the right order as in the wrong order.

haruspex said:
Consider any ordering of the six. If G1 and C1 are in the wrong order you can swap them to produce an ordering of the six in which they are in the right order, and vice versa. So there must be the same number of 6-sequences with G1 and C1 in the right order as in the wrong order.
Ah, ok. Thanks!

## 1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and organizing objects or events that satisfy certain criteria.

## 2. What are some examples of combinatorics problems?

Some examples of combinatorics problems include: finding the number of ways to arrange a set of objects, finding the number of possible outcomes in a probability experiment, and finding the number of ways to select a subset of objects from a larger set.

## 3. How is combinatorics used in real life?

Combinatorics is used in a variety of real-life applications, such as in computer science, cryptography, genetics, and economics. It can also be used to solve puzzles and games, and to analyze and optimize processes in various industries.

## 4. What are the main principles in combinatorics?

The main principles in combinatorics include the fundamental principle of counting, permutations, combinations, and the binomial theorem.

## 5. How can I improve my skills in solving combinatorics problems?

To improve your skills in solving combinatorics problems, it is important to practice and familiarize yourself with the different principles and techniques. You can also study and solve different types of problems, and seek help from experts or resources such as textbooks, online tutorials, and workshops.

• Math Proof Training and Practice
Replies
83
Views
11K
Replies
12
Views
4K
• General Discussion
Replies
12
Views
5K
Replies
66
Views
14K
• Art, Music, History, and Linguistics
Replies
1
Views
1K
Replies
25
Views
7K
Replies
110
Views
22K
• General Discussion
Replies
64
Views
16K