Ako sa
![](https://static.elitesecurity.org/tex/7d592956c17a6baece67855d10158111.png)
označimo broj ispravnih rasporeda pri vraćanju kamila
![](https://static.elitesecurity.org/tex/5290fde15044f63abd2b4eec7ec4c719.png)
, onda, za
![](https://static.elitesecurity.org/tex/af42ae2cd874b4d32465df6ee3924bb0.png)
, važi:
![](https://static.elitesecurity.org/tex/c3ee3a98bef68512af2e387f81af8a87.png)
Dokaz:
Ispravne kolone dužine
![](https://static.elitesecurity.org/tex/bd2b320696c94ea17dd122cd137b965c.png)
se mogu dobiti na dva različita načina:
1. Izdvojimo kamilu
![](https://static.elitesecurity.org/tex/61111e1b69e3a6e8950b9d06ff298bb6.png)
. Ostatak kamila može da se rasporedi ispravno na
![](https://static.elitesecurity.org/tex/5d8290f6217a0ff88f68950db7d60f87.png)
načina u novu kolonu, a za svaki od njih mi možemo kamilu
![](https://static.elitesecurity.org/tex/61111e1b69e3a6e8950b9d06ff298bb6.png)
smestiti na tačno
![](https://static.elitesecurity.org/tex/3f0a96bc844f8d7185440cbc0a66c344.png)
od postojećih
![](https://static.elitesecurity.org/tex/bd2b320696c94ea17dd122cd137b965c.png)
mesta unutar te kolone (kamila
![](https://static.elitesecurity.org/tex/61111e1b69e3a6e8950b9d06ff298bb6.png)
ne sme da se stavi
jedino iza kamile
![](https://static.elitesecurity.org/tex/eb559ab1e89182c9a3a3c4a39950a2aa.png)
). Na ovaj način možemo napraviti
![](https://static.elitesecurity.org/tex/c0a293e834b8fe3c24c15bd3727ef9b8.png)
različitih ispravnih kolona.
2. Izdvojimo kamilu
![](https://static.elitesecurity.org/tex/61111e1b69e3a6e8950b9d06ff298bb6.png)
. Ostatak kamila može da se rasporedi u kolonu u kojoj je
tačno jedan par kamila u pogrešnom poretku.
Posmatrajmo sada te dve pogrešno poređane kamile kao jednu novu kamilu. U tom smislu možemo da preoznačimo postojeću kolonu kamila na sledeći način:
![](https://static.elitesecurity.org/tex/64ee05b0f196e4ee5b208ac6612b61b7.png)
gde je
![](https://static.elitesecurity.org/tex/5ac8efafd63011075dd32d8d5dc4e6a0.png)
a
![](https://static.elitesecurity.org/tex/79721db935fb3facb912a38a5c92da9d.png)
"kamila" koju smo dobili spajanjem.
Ova kolona od
![](https://static.elitesecurity.org/tex/9adb91d18617c3dbe055e3b2ac7cd870.png)
kamile može se ispravno poređati na
![](https://static.elitesecurity.org/tex/2e75f661fbdc681ecc78a6a07977d79f.png)
načina, a pošto se dve pogrešno poređane kamile mogu odabrati na
![](https://static.elitesecurity.org/tex/9adb91d18617c3dbe055e3b2ac7cd870.png)
načina, to je ukupan broj kolona sa
tačno jednim parom kamila u pogrešnom poretku jednak
![](https://static.elitesecurity.org/tex/f9f25a1d291d7e8401c8c7e79cc433a9.png)
. Sada se u svaku od tako dobijenih kolona može umetnuti kamila
između one dve pogrešno postavljene kamile i time dobiti potpuno ispravna kolona.
Očigledno je da među kolonama dobijenim na način
1. i način
2. nema jednakih.
U postavci zadatka je
![](https://static.elitesecurity.org/tex/b844fdb090224e4f9a909b70a72b7376.png)
, pa ako po definiciji uzmemo da je
![](https://static.elitesecurity.org/tex/9659de17104619c5d703f1eda85056ee.png)
, a lako je videti da je
![](https://static.elitesecurity.org/tex/90160fa595f27f77ef7f31f33c9ad1a6.png)
, onda možemo da izračunamo i
![](https://static.elitesecurity.org/tex/d2f3760541306965d8fd6845df45805b.png)
(izračunavši prethodno
![](https://static.elitesecurity.org/tex/9efe5c2b1e4d3c080a85029c81854c3c.png)
).
Zadatak je u principu mogao da se reši i preko principa "uključenja-isključenja" ali bi u tom slučaju bilo daleko više posla.
Nadam se da će neko rešiti dobijenu diferencnu j-nu.
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.