- First, we will seat the women
- Women can sit in either all odd-numbered seats, or all even-numbered seats
- For 1 case, the number of different arrangements of the women is equal to 3·2·1=6
- Therefore, for each case (women sitting in odd-numbered chairs or even-numbered chairs), there are n! ways for the women to be seated
- For the 2 ways to seat women, there are 2·n! ways to seat the women (2·3!=12)
- For the rest of the problem, we will assume that the women are seated in one of these possible ways- all in the odd-numbered seats, or all in the even-numbered seats
- Now, we will look at how many possible ways the men can be seated between women
Formation from A-Arrangements
F1X1F2X2...FnXnF(n+1)M(n+1)
Therefore, for this example where n=3, there is only 1 possible exchange. This shows that there are (n-2) possible exchanges for any value n.
Formation from B-Arrangements
Insertion of the pair (F(n+1), M(n+1)) will not be able to generate An arrangements for B1 or for B(2n-1):
- Example: For n=4, where the couple (F(5), M(5)) is inserted
B1: F1M1F2M4F3M2F4M3F5M5
B(2n-1): F1M3F2M1F3M2F4M4F5M5
For the B-arrangements from 2 to (2n-2), M(n+1) can be inserted to form Bn B-arrangements for (2n-3) of the men for the arrangement with 2n forms (explained previously) to make an A(n+1) pair arrangement
Formation from C-Arrangements
- Original Cn n-pair C-arrangements:
M1F1X2F2X3F3...XnFn
- Mv is the other man (besides M1) who is seated next to his wife (v is some value from 2 to n)
- If we insert the pair (F(n+1), M(n+1)) BEFORE F1 (after M1), the pair M1F1 is no longer sitting next to each other
- Then, we can exchange M(n+1) with Mv- the man still sitting next to his wife, in order to obtain a (n+1)-pair A-arrangement
This yields a total of:
Cn·(n+1)-pair A-arrangements
Background
- Married couples problem- probleme des menages
- First published in 1891 in Theorie de Nombres
- Many solutions- we will use an adaptation of Taylor’s approach
- Question: How many ways can n married couples be seated about a round table in such a manner that there is always one man between two women and none of the men is ever seated next to his own wife?
Eduoard Lucas
- Francois Edouard Anatole Lucas born April 4th 1842 in Amiens, France
- Studied at Ecole Normale Superieure
- Worked in Paris observatory
- Became professor of math in Paris and served in the army
- Most well known for study of Fibonacci sequence and related Lucas sequences/numbers
- Died on October 3, 1891 at age 49 in Paris
Lucas' Problem of Married Couples
- Determining all of the possible arrangements that can occur: A, B, C
- Determining the numerical relationships between types of arrangements with n couples VS n+1 couples
- Determining how many A arrangements can be formed from each type of A, B, C arrangements
- Determining a recurrence formula from B arrangements
- Making substitutions to determine the coefficients of the recurrence formula for B arrangements
- Transforming the recurrence formula from B arrangements to A arrangements to solve the problem
By Lauren Gillinov and Regan Brady
First Steps
- Label the chairs arranged in a circle from 1 to 2n
Ways to seat women
Defining Terms and Arrangements
- Women labeled F1, F2, F3...Fn
- Men labeled M1, M2, M3...Mn
- Couples (Fn, Mn)
- Husbands who we do not know anything about- we do not know who they are married to, are labeled Xn
- Assume the (n+1) pair arrangement where no husband sits next to his wife is as follows:
F1X1F2X2...FnXnF(n+1)X(n+1)
- Now, we will remove the (n+1)st couple
- Removed (F(n+1), M(n+1)=Xv), and then replace M(n+1)=Xv with X(n+1)=Mu (Mu is some man- we do not know which one)
- Then, we get the n-pair arrangement:
F1X1F2X2...FvMuF(v+1)...FnXn
Arrangement
F1X1F2X2...FvMuF(v+1)...FnXn
- There are three possible outcomes of this arrangement:
1. No man sits next to his wife
- Occurs when Mu≠Mv, Mu≠M(v+1), Xn≠M1
2. One man sits next to his wife
- Occurs when Mu=Mv OR Mu=M(v+1) OR Xn=M1
3. Two men sit next to their wives
- Occurs when Mu=Mv OR Mu=M(v+1) and Xn=M1
If Mu=Mv and Xn=M1
- F1X1F2X2...FvMvF(v+1)...FnM1
If Mu=M(v+1) and Xn=M1
- F1X1F2X2...FvM(v+1)F(v+1)...FnM1
3 types of arrangements (A, B, C) that correspond to the three ways mentioned above
C-Arrangements
A-Arrangements
B-Arrangements
- A certain man sits on a certain side of his wife and another man sits next to his wife
- Cn is the number of ways n couples can be seated in a C-arrangement
- No man sits next to his wife
- An is the number of ways n couples can be seated in an A-arrangement
- One man sits next to his wife
- Bn is the number of ways n couples can be seated in a B-arrangement
Relationships Between Arrangements
- In order to solve the problem, we will find the relationships between: An, Bn, Cn, A(n+1), B(n+1), and C(n+1) so we can relate them all at the end of the problem
- An is the number of A-arrangements possible from n couples
- Bn is the number of B-arrangements possible from n couples
- Cn is the number of C-arrangements possible from n couples
- Given that M1F1 are seated next to each other and one other man X2, X3...Xn is also seated next to wife
- Arrangement:
M1F1X1F2X2...FnXnF(n+1)
- Group 1 where X1=M(n+1)
- If we remove M1F1 from the original C(n+1) C-arrangements, we obtain from this group Cn C-arrangements of the pairs 2 through (n+1) where M(n+1) is seated on the right of F(n+1) and one other man is still sitting next to his wife
- So from this group, when (M1,F1) is removed, there are Cn possible C-arrangements
Explanation
- Arrangement after removing first couple
M(n+1)F2X2...FnXnF(n+1)
- Since the couples are seated around a circular table, couple (F(n+1),M(n+1)) are seated next to each other
- This creates Cn C-arrangements
- (n+1) pairs arranged so that a certain man is on a certain side of his wife and another man is next to his wife
- Assuming that (F1,M1) is one of the couples that are seated
next to each other, along with some other couple with a
man (X1 through X(n+1)) who is also sitting next to his wife
M1F1X1F2X2...FnX(n+1)F(n+1)
- Divide this arrangement into two groups
1) X1=M(n+1)
2) X1≠M(n+1)
- Then we remove the 1st pair (F1, M1)
- Therefore, we can determine the relationship between
C(n+1), Cn, and Bn to be:
C(n+1)= Cn + (2n-1)Bn
- Given that (M1,F1) are seated next to each other and one other man X2, X3...Xn is also seated next to wife
- Arrangement:
M1F1X1F2X2...FnXnF(n+1)
- Group 2 where X1≠M(n+1)
- This group contains (2n-1) subgroups
Explanation
- The man other than M1 sitting next to his wife can either sit on her left or on her right- therefore, in 2n possible ways
- However, since X1≠M(n+1), one of the possible arrangements cannot occur (F(n+1) cannot be sitting next to her husband under these circumstances) making there be (2n-1) subgroups
- Arrangement:
X1F2X2...FnXnF(n+1)
- Once we remove the pair (M1,F1) from the original C(n+1) C-arrangements, we get Bn possible B arrangements for each of the subgroups of pairs 2 through (n+1) because only one other couple is still seated next to each other
- So from this group, when (M1,F1) is removed, there are (2n-1)·Bn possible B-arrangements
- We are going to insert F(n+1),M(n+1) in a A, B, or C- arrangement of n pairs before F1, and then exchange the places of M(n+1) with some other man so that no man is sitting next to his wife after the exchange occurs, in order to obtain all of the A(n+1) A arrangements from each group
- This method gives us all the A-arrangements of the (n+1) pairs
- In order to determine A(n+1), it is therefore only necessary to determine the number of ways that this insertion/exchange can be accomplished for an A, B, or C-arrangement
- We will accomplish this in three steps by finding the amount of formations of the (n+1) pair A-arrangements from A-arrangements, B-arrangements, and C-arrangements
- A arrangements cannot be made for B1 or B(2n-1)- as just explained
- (2n-3)·Bn A(n+1)arrangements
1. ...F1M1...
2. ...F1M2F2...
3. ...F2M3F3...
(2n-2) ...F(n-1)M(n-1)Fn...
(2n-1). ...FnMnF1...
(2n). ...FnM1F1...
- The 2nth arrangement can create a B arrangement in n-1 ways, because M(n+1) can be exchanged with any term except for M1
- (n-1)·Bn A(n+1) arrangements
- A-arrangements where no men sitting next to their wives
- M(n+1) can be exchanged for all of the men that are not on either side of F(n+1)
- So M(n+1) can be exchanged for any man that is not Xn or his original position, hence the (n-2) possible exchanges
- So for each An A-arrangement, there are a total of (n-2) ways to form an A arrangement with n+1 couples
This yields a total of:
(n-2)·An (n+1)-pair A-arrangements
With the addition of couple n+1 (6) inserted before F1:
Example: Beginning C-arrangement with n=5
- If M6 is exchanged for M4, an (n+1) pair A-arrangement is formed
- Depending on which man Mv is (the man other than M1 sitting next to his wife), this A-arrangement of (n+1) couples can be formed in Cn ways
Example where n=3 (A3 arrangement)
Therefore, this A(n+1) arrangement is an A4 arrangement, which actually becomes a B4 arrangement with the insertion of (F4, M4).
In order to transform this back into a An arrangement, M(n+1), or M4, must be inserted for some other man. M4 can be exchanged for any man that is not Xn (M2 in this example), and that is not M1.
- In this example, it can be seen that after the addition of the 5th couple, it is impossible to exchange M5 with another man to make the arrangement an A-arrangement (where no man sits next to his wife)
- This is because M5 would have to be exchanged with M1- which would still leave M1 sitting next to F1, just sitting on her right instead of her left
- Similarly, in this example, it can be seen that after the addition of the 5th couple, it is impossible to exchange M5 with another man to make the arrangement an A-arrangement (where no man sits next to his wife)
- This is because M5 would have to be exchanged with M4- which would still leave M5 sitting next to F5, just sitting on her left instead of her right
}
Total of (n+1)-pair A-Arrangements
A(n+1)=[(n-2)·An + (3n-4)·Bn + Cn]
- For n=3, there will be (n+1) couples, or 4 couples
- A3 + 5·B3 + C3 A-arrangements when there are 4 couples
B(n+1)=Bn + An
An= B(n+1) -Bn -For the next step we will insert (n+1) for n
A(n+1)= B(n+2) - B(n+1)
Using the equation previously found for A(n+1), we obtain a formula in terms of Bn
- A(n+1)=(n-2)·An + (3n-4)·Bn + Cn
- B(n+2) - B(n+1) = (n-2)(B(n+1) -Bn) + (3n-4)·Bn + Cn
- B(n+2) = (n-1)·B(n+1) + (2n-2)·Bn + Cn
Replacing n with n+1, we obtain:
- B(n+3)=n·B(n+2) + 2n·B(n+1) + C(n+1)
We solve to find an equation for: B(n+3) - B(n+2) with the help of the previously found equation
C(n+1) = Cn + (2n-1)Bn
- n·B(n+2) + 2n·B(n+1) + C(n+1) - [(n-1)·B(n+1) + (2n-2)·Bn + Cn]
- B(n+3) = [B(n+2) + n·B(n+2)] + [2n·B(n+1) - (n-1)·B(n+1)] - [(2n-2)·Bn] + [C(n+1)] - [Cn]
- B(n+3) = [(n+1)·B(n+2)] + [(n+1)·B(n+1)] - [(2n-2)·Bn] + Cn + (2n-1)·Bn - Cn
- B(n+3) = (n+1)·[B(n+2) + B(n+1)] + Bn
Thanks for listening!
- Recurrence formula is defined by: g(n)= f(n+1) - f(n)
- The recurrence formula that we found in the last slide is:
B(n+2) = (n)·[B(n+1) + B(n)] + B(n-1)
- We need three successive B's to find the following B, so we want to be able to find one in the form of:
- C= En·B(n+1) + Fn·(Bn) + Gn·B(n-1)
- En, Fn, and Gn are functions
- We then replace n with (n+1) to obtain:
- C=E(n+1)·B(n+2) + F(n+1)·B(n+1) + G(n+1)·Bn
- We subtract the second formula from the first:
- 0= -E(n+1)·B(n+2) + (En - F(n+1))·B(n+1) + (Fn-G(n+1))·Bn + Gn·B(n-1)
- We compare the equation we obtained with the equation of the recurrence formula multiplied by Gn, to find the functions En, Fn, and Gn
- Gn·B(n+2) = Gn·(n)·B(n+1) + Gn·(n)·B(n) + Gn·B(n-1)
- 0= -Gn·B(n+2) + Gn·n·(B(n+1)) + Gn·n·(Bn) + Gn·B(n-1)
- 0= -E(n+1)·B(n+2) + (En - F(n+1))·B(n+1) + (Fn-G(n+1))·Bn + Gn·B(n-1)
Now the last two formulas are in the same form, so we can compare them to find:
(I) E(n+1)=Gn (II) En - F(n+1)=n·Gn (III) Fn - G(n+1)=G(n+1)
Coefficients
- Now the last two formulas are in the same form, so we can compare them to find:
- (I) E(n+1)=Gn (II) En - F(n+1)=n·Gn (III) Fn - G(n+1)=n·G(n)
- Therefore, from (III), we obtain Fn= G(n+1) + n·Gn, or F(n+1)= G(n+2) + (n+1)·G(n+1)
- With (II) and (I), we can see that F(n+1)= En - N·Gn = G(n-1) - n·Gn
- From both equations for F(n+1), we obtain: G(n+2) + (n+1)·G(n+1) = G(n-1) - n·Gn or
- (n+1)·G(n+1) + n·Gn = G(n-1) - G(n+2)
- A solution to this equation (n+1)·G(n+1) + n·Gn = G(n-1) - G(n+2) is that G(n) = n(-1)^n as shown and simplified below
- (n+1)·(n+1)·(-1)^(n+1) + n·n·(-1)^n = (n-1)·(-1)^(n-1) - (n+2)·(-1)^(n+2)
If n is even:
- -(n^2+2n+1) + n^2 = -(n-1) - (n+2)
- -2n-1 = -2n-1
If n is odd:
- (n^2+2n+1) - n^2 = (n-1) + (n+2)
- 2n + 1 = 2n +1
- With this solution (Gn=n(-1)^n) in mind, we can see from equation I that:
- E(n) = G(n-1), or E(n) = (n-1)·(-1)^(n-1), which can be written as E(n) = -(n-1)·(-1)^n
- Additionally, with the solution Gn=n(-1)^n, we can see from equation III that:
- Fn - (n+1)·(-1)^(n+1)=n·n·(-1)^n or Fn=-(n+1)·(-1)^n + n^2·(-1)^n, which can be written as Fn=((-1)^n)·[(n^2)-n-1]
- When we substitute in our coefficients in terms of n, we obtain:
- (n-1)·B(n+1) - (n^2 - n -1)·Bn - n·B(n-1) = -c(-1)^n
- In order to determine the constant for the recurrence formula, we substitute n=4
- (3)·B(5) - (11)·B(4) - 4·B(3) = -c(-1)^4
- So, in order to solve for c, we need to solve for B(5), B(4), and B(3):
B5 Possible Arrangements
F1 M5 F2 M4 F3 M2 F4 M3 F5 M1
F1 M3 F2 M2 F3 M5 F4 M1 F5 M4
F1 M4 F2 M5 F3 M3 F4 M1 F5 M2
B4 Possible Arrangements
F1 M1 F2 M4 F3 M2 F4 M3
B3 Possible Arrangements:
- These arrangements are not possible because if there are 3 couples, 1 couple cannot sit next to each other without another also sitting next to each other
- We then determine the value of the constant c to be 2
3·3 - 11·1 - 4·0 = -c
-2 = -c
2 = c
- Therefore, the recurrence formula is:
- (n-1)·B(n+1) - (n^2 - n -1)·Bn - n·B(n-1) = -2(-1)^n
Recurrence Formula for A's
The recurrence formula for the A's is:
(n-1)·A(n+1) = (n^2 - 1)·An + (n+1)·A(n-1) +4(-1)^n
An example of calculating A from two prior A's, where n=4:
A(n-1)= A3 = 1 (only one possible A arrangement for 3 couples
An= A4= 2 (2 possible A arrangements for 4 couples)
(n-1)·A(n+1) = (n^2 - 1)·An + (n+1)·A(n-1) +4(-1)^n
(3)A5= 15·2 + 5·1 + 4·1
A5= 39/3 =13 possible A arrangements for 5 couples
The number of arrangements for certain values of A are:
A3=1, A4=2, A5=13, A6=80, A7=579, A8=4738, A9=43387, A10=439792, A14=10,927,434,464