6289. Permutacije i permutacije sa ponavljanjem

Permutacija sa ponavljanjem tipa $(k_1,k_2,\ldots,k_m)$ je uređena $n$ -torka u kojoj se element $a_1$ pojavljuje $k_1$ puta, …, element $a_m$ $k_m$ puta, gde je $k_1+\cdots+k_m=n$ ; takvih ima $P_{(k_1,\ldots,k_m)}(n)=\frac{n!}{k_1!\,k_2!\cdots k_m!} .$ (Kada bi svi elementi bili različiti, bilo bi $n!$ rasporeda; međusobnim zamenama jednakih elemenata ne dobija se novi raspored, pa delimo sa $k_1!\cdots k_m! .$ ) Slova reči $\text{KOMBINATORIKA}$ su: A, I, K, O po dva puta, a B, M, N, R, T po jednom; ukupno $13$ slova, pa permutacija ima $\frac{13!}{2!\,2!\,2!\,2!}=389188800 .$ Po abecedi je $A<B<I<K<M<N<O<R<T ,$ pa je prva permutacija AABIIKKMNOORT. Leksikografski poredak je poredak kao u rečniku: od dve permutacije ranije dolazi ona koja na prvom mestu na kome se razlikuju ima manji element. Zato sve permutacije sa istim početkom čine jedan neprekidan blok, a blok sa početkom $p$ ima onoliko članova koliko ima permutacija preostalih elemenata. Redni broj reči je broj permutacija koje dolaze pre nje, uvećan za $1 .$ Idemo mesto po mesto i sabiramo veličine blokova koji dolaze pre bloka u kome je reč.

1. mesto je $\text{K} .$ Pre bloka $\text{K}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, B, I$ ); u njima je ukupno $149688000$ permutacija, pa je do sada preskočeno $149688000 :$

\begin{aligned}\text{A}\ldots&:\ \frac{12!}{2!\,2!\,2!}=59875200\\\text{B}\ldots&:\ \frac{12!}{2!\,2!\,2!\,2!}=29937600\\\text{I}\ldots&:\ \frac{12!}{2!\,2!\,2!}=59875200\end{aligned}

2. mesto je $\text{O} .$ Pre bloka $\text{KO}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, B, I, K, M, N$ ); u njima je ukupno $39916800$ permutacija, pa je do sada preskočeno $189604800 :$

\begin{aligned}\text{KA}\ldots&:\ \frac{11!}{2!\,2!}=9979200\\\text{KB}\ldots&:\ \frac{11!}{2!\,2!\,2!}=4989600\\\text{KI}\ldots&:\ \frac{11!}{2!\,2!}=9979200\\\text{KK}\ldots&:\ \frac{11!}{2!\,2!\,2!}=4989600\\\text{KM}\ldots&:\ \frac{11!}{2!\,2!\,2!}=4989600\\\text{KN}\ldots&:\ \frac{11!}{2!\,2!\,2!}=4989600\end{aligned}

3. mesto je $\text{M} .$ Pre bloka $\text{KOM}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, B, I, K$ ); u njima je ukupno $5443200$ permutacija, pa je do sada preskočeno $195048000 :$

\begin{aligned}\text{KOA}\ldots&:\ \frac{10!}{2!}=1814400\\\text{KOB}\ldots&:\ \frac{10!}{2!\,2!}=907200\\\text{KOI}\ldots&:\ \frac{10!}{2!}=1814400\\\text{KOK}\ldots&:\ \frac{10!}{2!\,2!}=907200\end{aligned}

4. mesto je $\text{B} .$ Pre bloka $\text{KOMB}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A$ ); u njima je ukupno $181440$ permutacija, pa je do sada preskočeno $195229440 :$

\begin{aligned}\text{KOMA}\ldots&:\ \frac{9!}{2!}=181440\end{aligned}

5. mesto je $\text{I} .$ Pre bloka $\text{KOMBI}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A$ ); u njima je ukupno $20160$ permutacija, pa je do sada preskočeno $195249600 :$

\begin{aligned}\text{KOMBA}\ldots&:\ \frac{8!}{2!}=20160\end{aligned}

6. mesto je $\text{N} .$ Pre bloka $\text{KOMBIN}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, I, K$ ); u njima je ukupno $10080$ permutacija, pa je do sada preskočeno $195259680 :$

\begin{aligned}\text{KOMBIA}\ldots&:\ 7!=5040\\\text{KOMBII}\ldots&:\ \frac{7!}{2!}=2520\\\text{KOMBIK}\ldots&:\ \frac{7!}{2!}=2520\end{aligned}

7. mesto je $\text{A} .$ Među preostalim slovima $A, A, I, K, O, R, T$ nijedno nije manje od $\text{A} ,$ pa ništa ne preskačemo (ukupno i dalje $195259680$ ).

8. mesto je $\text{T} .$ Pre bloka $\text{KOMBINAT}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, I, K, O, R$ ); u njima je ukupno $600$ permutacija, pa je do sada preskočeno $195260280 :$

\begin{aligned}\text{KOMBINAA}\ldots&:\ 5!=120\\\text{KOMBINAI}\ldots&:\ 5!=120\\\text{KOMBINAK}\ldots&:\ 5!=120\\\text{KOMBINAO}\ldots&:\ 5!=120\\\text{KOMBINAR}\ldots&:\ 5!=120\end{aligned}

9. mesto je $\text{O} .$ Pre bloka $\text{KOMBINATO}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, I, K$ ); u njima je ukupno $72$ permutacija, pa je do sada preskočeno $195260352 :$

\begin{aligned}\text{KOMBINATA}\ldots&:\ 4!=24\\\text{KOMBINATI}\ldots&:\ 4!=24\\\text{KOMBINATK}\ldots&:\ 4!=24\end{aligned}

10. mesto je $\text{R} .$ Pre bloka $\text{KOMBINATOR}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, I, K$ ); u njima je ukupno $18$ permutacija, pa je do sada preskočeno $195260370 :$

\begin{aligned}\text{KOMBINATOA}\ldots&:\ 3!=6\\\text{KOMBINATOI}\ldots&:\ 3!=6\\\text{KOMBINATOK}\ldots&:\ 3!=6\end{aligned}

11. mesto je $\text{I} .$ Pre bloka $\text{KOMBINATORI}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A$ ); u njima je ukupno $2$ permutacija, pa je do sada preskočeno $195260372 :$

\begin{aligned}\text{KOMBINATORA}\ldots&:\ 2!=2\end{aligned}

12. mesto je $\text{K} .$ Pre bloka $\text{KOMBINATORIK}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A$ ); u njima je ukupno $1$ permutacija, pa je do sada preskočeno $195260373 :$

\begin{aligned}\text{KOMBINATORIA}\ldots&:\ 1\end{aligned}

Preostala slova $A$ su već u rastućem poretku (jedini mogući raspored), pa dalje ništa ne preskačemo.

Ukupno pre reči KOMBINATORIKA dolazi $195260373$ permutacija, pa je njen redni broj:

195260373+1=195260374

Dakle, KOMBINATORIKA je $195260374 .$ permutacija po redu.

Započni učenje

Privatni časovi

444.b

Beleške

Slični zadaci

Slični zadaci