6286. 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! .$ ) Elementi su $a$ tri puta, $b ,$ $c$ i $d$ tri puta, tip $(3,1,1,3) ,$ pa permutacija ima $\frac{8!}{3!\,3!}=1120 .$ 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 $1100 .$ 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 $1100 .$ 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 $1100 .$ 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 $1100 .$ 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 $1100 .$ mesto pada u blok koji počinje sa $\text{ddcdb} :$

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

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

Tražena permutacija je $\text{ddcdbaaa} .$

Započni učenje

Privatni časovi

443.a

Beleške

Slični zadaci

Slični zadaci