Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript
  • 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?

R

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

L

Lucas' Problem of Married Couples

Overview

  • 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

L

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

R

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

}

L

3 types of arrangements (A, B, C) that correspond to the three ways mentioned above

R

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

L

C(n+1) C-Arrangements

Group 1

  • 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

Group 2

  • (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

  • Arrangement:

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

R

L

Methods for Next Steps

  • 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

R

  • 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

F6

M6

F1

M1

F1

  • 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

F5

M3

F5

M3

F2

M4

With the addition of couple n+1 (6) inserted before F1:

Example: Beginning C-arrangement with n=5

M4

F2

  • 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

F1

M5

F4

M5

F5

M1

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.

B1

F2

M3

  • 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

M2

F3

M2

F3

M4

F4

M2

M4

F4

F1

F3

START HERE

M3

M2

M4

M2

F3

M1

M3

F4

F1

F2

F3

F2

M1

M3

M2

F2

F3

M1

F1

M5

F5

M3

F2

M4

B(2n-1)

M1

F4

  • 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

M2

F3

L

R

}

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

R

Substitutions

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

L

Thanks for listening!

Recurrence Formula

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

R

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

L

Recurrence Formula for A's

R

Completion

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

L

First, defining n-pair B-arrangements that have 2n forms- 2n because men can sit on left or right of their wives

1. ...F1M1... (Couple 1 sitting next to each other)

2. ...F1M2F2... (Couple 2 sitting next to each other)

(2n-1). ...FnMnF1... (Couple n sitting next to each other)

(2n). ...FnM1F1... (Couple 1 sitting next to each other again, but M1 to the left of F1 unlike #1)

Next Steps

  • Next, we will use substitution from the formulas that we have already found in order to obtain formulas with only one type of arrangement- we will start with B- arrangements and then use relationships found to obtain an explicit formula for A-arrangements

Table with examples:

(From washjeff.edu)

This yields a total of:

(3n-4)·Bn A(n+1)arrangements

{

-n·A(n-1)

  • We use formulas to express A(n-1), An, and A(n+1) in terms of Bn and B(n+1)

An = B(n+1) - Bn

Found in a prior step

A(n-1)

  • Using: (n-1)·B(n+1) - (n^2 - n -1)·Bn - n·B(n-1) = -2(-1)^n and A(n-1) = Bn - B(n-1)
  • (n-1)·B(n+1) = ((n^2)-1)·Bn + [-n·Bn + n·B(n-1)] -(2·(-1)^n)

  • (n-1)·B(n+1) = ((n^2)-1)·Bn - n·A(n-1) -(2·(-1)^n)
  • A(n-1) = [[(n^2 - 1)·Bn]/n] + [[(1-n)·B(n+1)]/n] - [(2·(-1)^n)/n]

A(n+1)

  • Using: (n-1)·B(n+1) - (n^2 - n -1)·Bn - n·B(n-1) = -2(-1)^n and A(n+1) = B(n+2) - B(n+1)
  • Substitute (n+1) in for n in the recurrence formula:
  • (n)·B(n+2) = ((n+1)^2 - (n+1) - 1)·B(n+1) + (n+1)·B(n) - 2(-1)^(n+1)
  • (n)·B(n+2) = (n^2 + 2·n + 1 - n - 1 - 1)·B(n+1) + (n+1)·B(n) + 2(-1)^(n)
  • (n)·B(n+2) - (n)·B(n+1) = (n^2 - 1)·B(n+1) + (n+1)·B(n) + 2(-1)^(n)
  • (n)·A(n+1) = (n^2 - 1)·B(n+1) + (n+1)·B(n) + 2(-1)^(n)
  • A(n+1) = [((n^2 - 1)·B(n+1))/n] + [((n+1)·B(n))/n] + [(2(-1)^(n))/n)]

Elimination of B(n+1) and Bn

  • We eliminate B(n+1) in the second and third (bold) equations by substituting B(n+1)= An + Bn
  • We eliminate Bn by using the process of elimination among common variables
  • Then we get:

(n-1)·A(n+1) = (n^2 - 1)·An + (n+1)·A(n-1) +4(-1)^n

M1

F3

F2

M3

M2

F1

B(n+1) B-Arrangements

Group 1

  • (n+1) pairs arranged in such a way that only one couple sits next to each other
  • Arrangement:

F1X1F2X2...FnXnF(n+1)M(n+1)

  • Divide these arrangements into 2 groups:

1) Xn=M1

2) Xn≠M1

  • Then we remove the (n+1) pair {F(n+1), M(n+1)}
  • Once the (n+1) couple has been removed, Group 1 gives us all Bn n-pair B-arrangements

Explanation

  • Group 1 defined as where Xn=M1
  • Arrangement with M1:

F1X1F2X2...FnM1

  • As the couples are seated in a circle, M1 will be sitting next to F1, causing this to be a B-arrangement
  • Therefore, Group 1 gives us all Bn n-pair B-arrangements

Group 2

  • Once the (n+1) couple has been removed, Group 2 gives us all An n-pair A-arrangements

Explanation

  • Group 2 defined as where Xn≠M1
  • Arrangement where Xn is any man except for M1:

F1X1F2X2...FnXn

  • Since Xn cannot be M1, no couples are sitting next to each other in this group
  • Therefore, Group 2 gives us all An n-pair A-arrangements
  • Therefore, we can determine the relationship between B(n+1), Bn, and An to be:

B(n+1)=Bn + An

If Mu=Mv

  • F1X1F2X2...FvMvF(v+1)...FnXn

}

If Mu=M(v+1)

  • F1X1F2X2...FvM(V+1)F(v+1)...FnXn

}

If Xn=M1

  • F1X1F2X2...FvMuF(v+1)...FnM1

}

  • For either case, women occupy 3 seats

3 different women could sit here

Remaining 1 woman could sit here

Remaining 2 different women could sit here

M1

F3

F2

M3

M2

F1

1

2

6

Example: n=3, chairs arranged 1 to 6 (2n)

5

3

4

=where M(n+1) can be inserted

=where M(n+1) cannot be inserted

M1

F3

F2

M3

M2

F1

M1

F2

F4

M2

M3

F1

F3

M4

M1

F2

F4

M4

M3

F1

F3

M2

M1

F3

F2

M3

M2

F1

M1

F3

F2

M3

M2

F1

M1

F3

F2

M3

M2

F1

Table with examples:

(From washjeff.edu)

Learn more about creating dynamic, engaging presentations with Prezi