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 05: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


Download original PDF file


untitled-2.pdf (PDF, 76 KB)


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


Document preview untitled-2.pdf - page 1/1


Related documents


untitled 2
ar special report
mahatma vol3
guia
gfareport7
gfareport7a 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

QR Code

QR Code link to PDF file untitled-2.pdf