Combinatorics question involving dancing.?

Question

There are n boys and n girls at a dance and every boy dances with a different girl on every dance. On the first dance there are n! different arrangements of boys and girls. Suppose that on the second dance no boy dances with the same girl. With that restriction, there are D_n (the nth derrangement) number of ways to arrange the boys and the girls on the second dance. Given the m-th dance, how many ways can you arrange the boys and the girls such that no boy is dancing with a girl he has previously danced with????

Answer 1

To explain this matter, we have to use the Inclusion-Exclusion Principle. i think you probably aware of it. if don't, you can find about it easily on the internet and it is very simple and easy.
But the problem is that, in order to solve this analytically,the formulas used are too complicated and it is nearly impossible to write them down. so i'm gonna introduce the idea of how to solve this question.

you may begin with following tasks
First, to think of this, assign identity to men with 1,2,...,n numbers to distinguish from each other and let A_k denote kth man. (do the same to women as B_k). and let D2_n denote the number we are trying to find. (Dk-1_n for the number of possible arrangement of kth day)

There must be n! arrangements on the first day of dance. (for the first dance there are n! possibilities). for the second dance, each man has to choose as a partner a woman other than the one with who he first danced. the number of possibilities,D1_n, is the nth derangement number Dn.

On the third day, A_i cannot choose B_i1 and B_i2 whom he has already danced with. let the set T_k denote the way that A_k choose B_k1 or B_k2. So you can easily find out that

D2_n = |(T_1)c N (T_2)c N ... N (T_n)c| ..............(1)

where (T_k)c is the complemenary set of T_k and N stands for "Intersection" .

to solve (1), we need to use the Inclusion-Exclusion Principle and the way use it is too complicated. you could derive the formula which equals Dk_n, but computing it with pen is nearly impossible,. you have to use computer to compute.








(here goes additional answer to your question and this is the complete answer!<7:33pm 6.20>)

I do some research with my computer and the correct answer is the mth day's possible arrangements can vary depend on the m-1th day's choice and various other people's choices. if you take the number of people which is the initial value for this problem as n, it suddenly becomes extremely complicated. if you take the initial value more specific , let's say 10 (10 people), it is still impossible to say how many possible way to arrange people on mth (3<=m<=10) day. here goes an example for the reason why this is happening

case 1
let's set our initial value for n (there are n people)
on the first day and the second day, A1 danced with B1 and B2 respectively, and so does A2 with B2 and B1 respectively. on the third day, it is obvious that A1 and A2 cannot dance with two same women, so they must dance with the other women. so A1 has n-2 choices and can choose the women he likes. so let's say that A1 choose B3 as a dance partner, A2 must choose the women other than B1,B2 and B3 which leaves him n-3 choices. (the real situation may leave A1 and A2 choices far less because we are ignoring all the other people A3~An)

case2
on the first day and the second day, A1 danced with B1 and B2 respectively, and A2 danced with B3 and B4 respectively.on the third day, there are two choices which A1 can make.

i). A1 choose B3 and B4.
ii). A1 choose the women other than B1,B2,B3 and B4.

If A1 takes i),this leaves A2 n-2 choices. If A1 takes ii),this leaves A2 n-3 choices

you can see that the situation on the mth day can be vary depend on whom you have already chosen for your dance partner on the m-1th day and other people's choice on the same day. so the correct asnwer for your question is that there is no established arrangement on the mth day. but there are still infinite amount of possibilities for you to figure this madness out, and when if you done, please let me know :)

Answer 2

I am not familiar with calculating derangements. However, I am wondering if the answer is simply ((n-(m-1))!

My reasoning is to start at the nth dance.

Since each boy has danced with all but one girl, there is only one possible arrangement of partners.

At dance m=(n-1), The first boy has two possible partners. Once he picks his partner, suppose we ask that girl which of the other (n-1) boys she hasn't partnered. Now that boy has only one choice for a partner. So we pair him up with that girl. If we continue this way, we see that all the other boys are forced to accept only one possible partner. So we have 2*1^(n-1)=2 arrangements.

At dance m=(n-2): Our first boy has a choice of three potential partners. Once he chooses, we have two possibilities for each of the rejected girls. So we choose one of the two partners for one of the girls.
So we have 3*2 arrangements for the first two boys.
This is where I get stuck.

My next step, if I were to work further, is to try small values of n.

For example, if n=3 the there is only one girl remaining. so my answer is indeed 3*2*1=3! and I am at the first dance for n=3 so the problem is solved.

But for n=4, I am at the second dance, and how many choices do I have?

Perhaps this is enough for you to solve this problem. I really ought to be working on my own Topology problems!

Answer 3

Unless I misunderstood the statement of the problem ...
On the first dance there there is only n arrangements (n pairs) not n!.
There must be n dances to ensure that there will be n arrangements to insure that every girl dances with a different boy.