6261. Permutacije i permutacije sa ponavljanjem

Permutacija (bez ponavljanja) skupa od $n$ elemenata je svaka uređena $n$ -torka u kojoj se svaki element skupa pojavljuje tačno jednom; takvih permutacija ima $P(n)=n! .$ (Prvo mesto popunjavamo na $n$ načina, drugo na $n-1 ,$ …, poslednje na $1 .$ ) 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. Ukupno ima $6!=720$ permutacija. Mesto po mesto određujemo blok u kome je $389 .$ permutacija.

1. mesto. Elementi su $1, 2, 3, 4, 5, 6 .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $389 .$ mesto pada u blok koji počinje sa $\text{4} :$

\begin{aligned}\text{1}\ldots&:\ 5!=120,\quad\text{mesta }1\text{–}120\\\text{2}\ldots&:\ 5!=120,\quad\text{mesta }121\text{–}240\\\text{3}\ldots&:\ 5!=120,\quad\text{mesta }241\text{–}360\\\text{4}\ldots&:\ 5!=120,\quad\text{mesta }361\text{–}480\end{aligned}

2. mesto. Početak je $\text{4} ,$ a preostali elementi su $1, 2, 3, 5, 6 .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $389 .$ mesto pada u blok koji počinje sa $\text{42} :$

\begin{aligned}\text{41}\ldots&:\ 4!=24,\quad\text{mesta }361\text{–}384\\\text{42}\ldots&:\ 4!=24,\quad\text{mesta }385\text{–}408\end{aligned}

3. mesto. Početak je $\text{42} ,$ a preostali elementi su $1, 3, 5, 6 .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $389 .$ mesto pada u blok koji počinje sa $\text{421} :$

\begin{aligned}\text{421}\ldots&:\ 3!=6,\quad\text{mesta }385\text{–}390\end{aligned}

4. mesto. Početak je $\text{421} ,$ a preostali elementi su $3, 5, 6 .$ Brojimo blokove redom, po veličini sledećeg elementa; traženo $389 .$ mesto pada u blok koji počinje sa $\text{4216} :$

\begin{aligned}\text{4213}\ldots&:\ 2!=2,\quad\text{mesta }385\text{–}386\\\text{4215}\ldots&:\ 2!=2,\quad\text{mesta }387\text{–}388\\\text{4216}\ldots&:\ 2!=2,\quad\text{mesta }389\text{–}390\end{aligned}

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

\begin{aligned}\text{42163}\ldots&:\ 1,\quad\text{mesta }389\text{–}389\end{aligned}

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

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

Započni učenje

Privatni časovi

430.v

Beleške

Slični zadaci

Slični zadaci