untitled 2 .pdf
File information
Original filename: untitled-2.pdf
This PDF 1.5 document has been generated by TeX / pdfTeX-1.40.18, and has been sent on pdf-archive.com on 27/09/2017 at 07:03, from IP address 70.77.x.x.
The current document download page has been viewed 267 times.
File size: 76 KB (1 page).
Privacy: public file
Share on social networks
Link to this file download page
Document preview
Question 8
Give a combinatorial proof of the following identity.
m
X
m+n
m
n
=
k
r
+
k
m+r
k=0
Proof. During the time of the old republic, the Jedi masters held many seats in the republic’s
grand senate. Each year, an election is held for the control of the m + r seats. However,
under the reknown leadership of Jedi Master Yoda, all m jedi masters always won m seats of
the senate. As only jedi masters are allowed to take a seat in the old republic, the remaining
r seats always fell into the hands of corrupt nobles. Each year, m jedi and n nobles competed
for m + r seats but without fail, the m jedi all secured seats while the nobles squabbled over
the remaining r. The distribution of power seemed absolute until the invasion of Naboo.
Following the invasion, the jedi council speculated
on the results of the next election. They
m+n
enumerated the possibilities. There were m+r ways to distribute the seats. However, being
especially cautious, they considered all disjoint possibilities of distributing the council seats
as follows:
n
1. m0 r+0
: The best case, the Jedi maintain their political position.
n
2. m1 r+1
: The Jedi lose a seat in the senate. Consequently, the nobles gain a seat.
n
3. m2 r+2
: The Jedi lose two seats and the nobles capture them.
4. . . .
n
: The worst case scenario, the Jedi lose all the seats in the senate and it is
5. m
m r+m
now completely controlled by the nobles.
Since computing the arrangements of seats by m+n
is the same as going through all the
m+r
possible ways the Jedi could lose k ∈ {0, 1, 2, . . . , m} seats. It follows that
m
X
m
n
m+n
=
.
k
r+k
m+r
k=0
Note. I used the fact that |A1 ∪ A2 ∪ · · · ∪ An | = |A1 | + |A2 | + · · · + |An | if the A’s are pairwise
disjoint.
1

Link to this page
Permanent link
Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..
Short link
Use the short link to share your document on Twitter or by text message (SMS)
HTML Code
Copy the following HTML code to share your document on a Website or Blog