6287. 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$ jednom i $c$ dva puta, pa permutacija ima $\frac{6!}{3!\,2!}=60 .$ 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, c .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $55 .$ mesto pada u blok koji počinje sa $\text{c} :$

\begin{aligned}\text{a}\ldots&:\ \frac{5!}{2!\,2!}=30,\quad\text{mesta }1\text{–}30\\\text{b}\ldots&:\ \frac{5!}{3!\,2!}=10,\quad\text{mesta }31\text{–}40\\\text{c}\ldots&:\ \frac{5!}{3!}=20,\quad\text{mesta }41\text{–}60\end{aligned}

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

\begin{aligned}\text{ca}\ldots&:\ \frac{4!}{2!}=12,\quad\text{mesta }41\text{–}52\\\text{cb}\ldots&:\ \frac{4!}{3!}=4,\quad\text{mesta }53\text{–}56\end{aligned}

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

\begin{aligned}\text{cba}\ldots&:\ \frac{3!}{2!}=3,\quad\text{mesta }53\text{–}55\end{aligned}

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

\begin{aligned}\text{cbaa}\ldots&:\ 2!=2,\quad\text{mesta }53\text{–}54\\\text{cbac}\ldots&:\ \frac{2!}{2!}=1,\quad\text{mesta }55\text{–}55\end{aligned}

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

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

Započni učenje

Privatni časovi

443.b

Beleške

Slični zadaci

Slični zadaci