Compute the values: D2-2D1, D3-3D2, D4-4D3, D5-5D4, …, D10-10D9, where the D’s are the derangements values described on P.335. What is the pattern?
Compute the values: D2-2D1, D3-3D2, D4-4D3, D5-5D4, …, D10-10D9, where the D’s are the derangements values described on P.335. What is the pattern?
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Topic Video
Question
100%
- Compute the values: D2-2D1, D3-3D2, D4-4D3, D5-5D4, …, D10-10D9, where the D’s are the derangements values described on P.335. What is the pattern?
Transcribed Image Text:8.1 Examples Defined by Recurrence
Equations
Example 8.1.1:
Imagine a party where couples arrive together, but at the end
of the evening, every person leaves with a new partner. For each n
e P, let D, denote the number of different ways n couples can be
Derangements
"deranged" - that is, rearranged in couples so no one is paired
with the person they arrived with.
// one couple cannot be deranged.
/| 3 one and only one way to derange two couples.
// If the couples arrive as Aa, Bb, and Cc,
// then A would be paired with b or c.
//
Then D1 = 0
D2 = 1
D3 = 2
If A is paired with b, C must be paired with a (not c),
//
If A is paired with c, B must be paired with a (not b),
//
and then B with c.
//
and then C with b.
// How big are D
and D
D
5'
? How can we calculate
10
4'
them? Is there a formula?
Let's develop a strategy for counting derangements when n
>= 4. Suppose the n women are A,, A2, A3, ... An,
and each Aj
arrives with man a ¡.
Woman A, may be "re-paired" with any of the n - 1 men a, or
az or ... or a ni; let's say she's paired with a k where 2 <= k <= n.
Now let's consider a k's original partner, woman Ak: she might
take a, or she might refuse a, and take someone else.
If A, is paired with a kand A kis paired with a,
there are n – 2
couples left to derange, and that may be done in exactly Dn-2
different ways.
If A, is paired with a k but A k refuses a,, we could pretend that
Akand a, arrived together, so now, there aren - 1 couples left to
derange which may be done in exactly Dn-1 different ways.
For each of the n – 1 men that A, might choose, there are
{Dn-2 + Dn-1} different ways to complete the derangement.
Therefore, when n >= 4,
Dn = (n – 1) {Dn-2 + Dn-1} ·
(8.1.2)
// This also applies when n = 3.
// Equation 8.1.2 is an example of a second-order recurrence
equation,
// where the generic entry is expressed in terms the previous
%3D
two entries.
Using Eq. 8.1.2 together with the values of D, and
we can
D2'
evaluate Dn for any value of n:
// in
principle
D3 = (3 – 1) {D2 + D¡} = 2{1+ 0}
2
||
![// where the generic entry is expressed in terms the previous
two entries.
Using Eq. 8.1.2 together with the values of D, and D2,
// in
we can
Pg 335
evaluate D, for any value of n:
principle
D3 = (3 – 1) {D2 + D¡} = 2{1 + 0}
D4 = (4 – 1) {D3 + D2} = 3 {2 + 1}
D5 = (5 – 1) {D4 + D3} = 4 {9 + 2}
(6 – 1) {D5 + D4} = 5 {44 + 9}
D7 = (7 – 1) {D6 + D5} = 6 {265 + 44}
2
9.
44
D6
265
1 854
%3D
D3 = (8 – 1) {D7 + D6} = 7{1854 + 265}
14 833
D9 = (9 – 1) {D8 + D7} = 8 {14833 + 1854}
133 496
%3|
D10 = (10 – 1){D9 + Dg} = 9{133496 + 14833}
1 334 961
%D
// It's strange that 1 334 961 = 10 × (133 496) + 1. Or is it?
// Is there a (convenient and compact) formula for Dn that we
can use to calculate
// its values?
The sequence on P defined by Sn = A x n! where A is any real
number satisfies the recurrence equation (8.1.2). If n >= 3 then
: (п — 1){А (п — 2)! + A (п — 1)!}
= (n – 1) A (n – 2)! {1 + [n – 1]}
= A (n – 1) (n – 2)! {n}
= A x n!
(n – 1) {S„-2 + Sn-1}
= Sµ.
// But will this "formula" apply when n = 1 or n = 2?
// Does there exist a real number A such that D,= A(n!) when
n = 1 or n = 2?
if o = D, = A(1!), then A must equal o,
if 1= D2 = A(2!), then A must equal 2.
// No, because
// and
We can however use this formula to prove that D, is O(n!) by
proving
Theorem 8.1.1:
For all n >= 2, (1/3) n ! <= Dn<= (1/2) n!
Consider the table of values
n (1/3) n!
Dn
(1/2) n!
1 1/3
1/2
2 2/3
1 = 2/2
3 6/3 = 2
3 = 6/2
4 24/3 = 8
9
12 = 24/2
5 120/3 = 40
44
60 = 120/2
6 720/3 = 240 265 360 = 720/2
Proof.
I| || || || ||||](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fd55d239b-1399-4942-bcb8-cf1bf4c668fb%2Faa3edf83-3737-47ee-8bb8-7baddcb9e2c0%2Fpt2howv_processed.png&w=3840&q=75)
Transcribed Image Text:// where the generic entry is expressed in terms the previous
two entries.
Using Eq. 8.1.2 together with the values of D, and D2,
// in
we can
Pg 335
evaluate D, for any value of n:
principle
D3 = (3 – 1) {D2 + D¡} = 2{1 + 0}
D4 = (4 – 1) {D3 + D2} = 3 {2 + 1}
D5 = (5 – 1) {D4 + D3} = 4 {9 + 2}
(6 – 1) {D5 + D4} = 5 {44 + 9}
D7 = (7 – 1) {D6 + D5} = 6 {265 + 44}
2
9.
44
D6
265
1 854
%3D
D3 = (8 – 1) {D7 + D6} = 7{1854 + 265}
14 833
D9 = (9 – 1) {D8 + D7} = 8 {14833 + 1854}
133 496
%3|
D10 = (10 – 1){D9 + Dg} = 9{133496 + 14833}
1 334 961
%D
// It's strange that 1 334 961 = 10 × (133 496) + 1. Or is it?
// Is there a (convenient and compact) formula for Dn that we
can use to calculate
// its values?
The sequence on P defined by Sn = A x n! where A is any real
number satisfies the recurrence equation (8.1.2). If n >= 3 then
: (п — 1){А (п — 2)! + A (п — 1)!}
= (n – 1) A (n – 2)! {1 + [n – 1]}
= A (n – 1) (n – 2)! {n}
= A x n!
(n – 1) {S„-2 + Sn-1}
= Sµ.
// But will this "formula" apply when n = 1 or n = 2?
// Does there exist a real number A such that D,= A(n!) when
n = 1 or n = 2?
if o = D, = A(1!), then A must equal o,
if 1= D2 = A(2!), then A must equal 2.
// No, because
// and
We can however use this formula to prove that D, is O(n!) by
proving
Theorem 8.1.1:
For all n >= 2, (1/3) n ! <= Dn<= (1/2) n!
Consider the table of values
n (1/3) n!
Dn
(1/2) n!
1 1/3
1/2
2 2/3
1 = 2/2
3 6/3 = 2
3 = 6/2
4 24/3 = 8
9
12 = 24/2
5 120/3 = 40
44
60 = 120/2
6 720/3 = 240 265 360 = 720/2
Proof.
I| || || || ||||
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
