6259. 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 $7!=5040$ permutacija, pa $1841 .$ postoji. Ne ispisujemo ih sve, već mesto po mesto odredimo u kom se bloku nalazi tražena permutacija.

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

\begin{aligned}\text{a}\ldots&:\ 6!=720,\quad\text{mesta }1\text{–}720\\\text{b}\ldots&:\ 6!=720,\quad\text{mesta }721\text{–}1440\\\text{c}\ldots&:\ 6!=720,\quad\text{mesta }1441\text{–}2160\end{aligned}

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

\begin{aligned}\text{ca}\ldots&:\ 5!=120,\quad\text{mesta }1441\text{–}1560\\\text{cb}\ldots&:\ 5!=120,\quad\text{mesta }1561\text{–}1680\\\text{cd}\ldots&:\ 5!=120,\quad\text{mesta }1681\text{–}1800\\\text{ce}\ldots&:\ 5!=120,\quad\text{mesta }1801\text{–}1920\end{aligned}

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

\begin{aligned}\text{cea}\ldots&:\ 4!=24,\quad\text{mesta }1801\text{–}1824\\\text{ceb}\ldots&:\ 4!=24,\quad\text{mesta }1825\text{–}1848\end{aligned}

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

\begin{aligned}\text{ceba}\ldots&:\ 3!=6,\quad\text{mesta }1825\text{–}1830\\\text{cebd}\ldots&:\ 3!=6,\quad\text{mesta }1831\text{–}1836\\\text{cebf}\ldots&:\ 3!=6,\quad\text{mesta }1837\text{–}1842\end{aligned}

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

\begin{aligned}\text{cebfa}\ldots&:\ 2!=2,\quad\text{mesta }1837\text{–}1838\\\text{cebfd}\ldots&:\ 2!=2,\quad\text{mesta }1839\text{–}1840\\\text{cebfg}\ldots&:\ 2!=2,\quad\text{mesta }1841\text{–}1842\end{aligned}

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

\begin{aligned}\text{cebfga}\ldots&:\ 1,\quad\text{mesta }1841\text{–}1841\end{aligned}

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

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

Započni učenje

Privatni časovi

430.a

Beleške

Slični zadaci

Slični zadaci