6288. 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{MATEMATIKA}$ su: A tri puta, M dva puta, T dva puta, a E, I, K po jednom; ukupno $10$ slova, pa permutacija ima $\frac{10!}{3!\,2!\,2!}=151200 .$ Po abecedi je $A<E<I<K<M<T ,$ pa je prva permutacija AAAEIKMMTT. 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{M} .$ Pre bloka $\text{M}\ldots$ dolaze blokovi sa manjim slovom na ovom mestu ( $A, E, I, K$ ); u njima je ukupno $90720$ permutacija, pa je do sada preskočeno $90720 :$

\begin{aligned}\text{A}\ldots&:\ \frac{9!}{2!\,2!\,2!}=45360\\\text{E}\ldots&:\ \frac{9!}{3!\,2!\,2!}=15120\\\text{I}\ldots&:\ \frac{9!}{3!\,2!\,2!}=15120\\\text{K}\ldots&:\ \frac{9!}{3!\,2!\,2!}=15120\end{aligned}

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

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

\begin{aligned}\text{MAA}\ldots&:\ \frac{7!}{2!}=2520\\\text{MAE}\ldots&:\ \frac{7!}{2!\,2!}=1260\\\text{MAI}\ldots&:\ \frac{7!}{2!\,2!}=1260\\\text{MAK}\ldots&:\ \frac{7!}{2!\,2!}=1260\\\text{MAM}\ldots&:\ \frac{7!}{2!\,2!}=1260\end{aligned}

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

\begin{aligned}\text{MATA}\ldots&:\ 6!=720\end{aligned}

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

\begin{aligned}\text{MATEA}\ldots&:\ 5!=120\\\text{MATEI}\ldots&:\ \frac{5!}{2!}=60\\\text{MATEK}\ldots&:\ \frac{5!}{2!}=60\end{aligned}

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

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

\begin{aligned}\text{MATEMAA}\ldots&:\ 3!=6\\\text{MATEMAI}\ldots&:\ 3!=6\\\text{MATEMAK}\ldots&:\ 3!=6\end{aligned}

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

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

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

\begin{aligned}\text{MATEMATIA}\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 MATEMATIKA dolazi $99261$ permutacija, pa je njen redni broj:

99261+1=99262

Dakle, MATEMATIKA je $99262 .$ permutacija po redu.

Započni učenje

Privatni časovi

444.a

Beleške

Slični zadaci

Slični zadaci