6284. 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! .$ ) Elemenata $a,a,b,c,d,d,d$ ima $7 ,$ tipa $(2,1,1,3) ,$ pa je broj njihovih permutacija $\frac{7!}{2!\,3!}=420 .$ Kako je $1099>420 ,$ permutacija sa rednim brojem $1099$ kod ovih elemenata ne postoji – u tekstu je očigledno štamparska greška.

\frac{7!}{2!\,3!}=420<1099

Isti postupak, kao u rešenju iz zbirke i u zadatku 443.a, primenjujemo na elemente $a,a,a,b,c,d,d,d$ (tri slova $a$ ), čijih permutacija ima $\frac{8!}{3!\,3!}=1120\ge1099 .$ 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.

1. mesto. Elementi su $a, a, a, b, c, d, d, d .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $1099 .$ mesto pada u blok koji počinje sa $\text{d} :$

\begin{aligned}\text{a}\ldots&:\ \frac{7!}{3!\,2!}=420,\quad\text{mesta }1\text{–}420\\\text{b}\ldots&:\ \frac{7!}{3!\,3!}=140,\quad\text{mesta }421\text{–}560\\\text{c}\ldots&:\ \frac{7!}{3!\,3!}=140,\quad\text{mesta }561\text{–}700\\\text{d}\ldots&:\ \frac{7!}{3!\,2!}=420,\quad\text{mesta }701\text{–}1120\end{aligned}

2. mesto. Početak je $\text{d} ,$ a preostali elementi su $a, a, a, b, c, d, d .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $1099 .$ mesto pada u blok koji počinje sa $\text{dd} :$

\begin{aligned}\text{da}\ldots&:\ \frac{6!}{2!\,2!}=180,\quad\text{mesta }701\text{–}880\\\text{db}\ldots&:\ \frac{6!}{3!\,2!}=60,\quad\text{mesta }881\text{–}940\\\text{dc}\ldots&:\ \frac{6!}{3!\,2!}=60,\quad\text{mesta }941\text{–}1000\\\text{dd}\ldots&:\ \frac{6!}{3!}=120,\quad\text{mesta }1001\text{–}1120\end{aligned}

3. mesto. Početak je $\text{dd} ,$ a preostali elementi su $a, a, a, b, c, d .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $1099 .$ mesto pada u blok koji počinje sa $\text{ddc} :$

\begin{aligned}\text{dda}\ldots&:\ \frac{5!}{2!}=60,\quad\text{mesta }1001\text{–}1060\\\text{ddb}\ldots&:\ \frac{5!}{3!}=20,\quad\text{mesta }1061\text{–}1080\\\text{ddc}\ldots&:\ \frac{5!}{3!}=20,\quad\text{mesta }1081\text{–}1100\end{aligned}

4. mesto. Početak je $\text{ddc} ,$ a preostali elementi su $a, a, a, b, d .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $1099 .$ mesto pada u blok koji počinje sa $\text{ddcd} :$

\begin{aligned}\text{ddca}\ldots&:\ \frac{4!}{2!}=12,\quad\text{mesta }1081\text{–}1092\\\text{ddcb}\ldots&:\ \frac{4!}{3!}=4,\quad\text{mesta }1093\text{–}1096\\\text{ddcd}\ldots&:\ \frac{4!}{3!}=4,\quad\text{mesta }1097\text{–}1100\end{aligned}

5. mesto. Početak je $\text{ddcd} ,$ a preostali elementi su $a, a, a, b .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $1099 .$ mesto pada u blok koji počinje sa $\text{ddcda} :$

\begin{aligned}\text{ddcda}\ldots&:\ \frac{3!}{2!}=3,\quad\text{mesta }1097\text{–}1099\end{aligned}

6. mesto. Početak je $\text{ddcda} ,$ a preostali elementi su $a, a, b .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $1099 .$ mesto pada u blok koji počinje sa $\text{ddcdab} :$

\begin{aligned}\text{ddcdaa}\ldots&:\ 2!=2,\quad\text{mesta }1097\text{–}1098\\\text{ddcdab}\ldots&:\ \frac{2!}{2!}=1,\quad\text{mesta }1099\text{–}1099\end{aligned}

Preostali elementi $a, a$ mogu se rasporediti samo na jedan način, pa je tražena permutacija $\text{ddcdabaa} .$

Za elemente kako su odštampani tražena permutacija ne postoji; za elemente $a,a,a,b,c,d,d,d$ to je $\text{ddcdabaa} .$

Započni učenje

Privatni časovi

442.a

Beleške

Slični zadaci

Slični zadaci