6262. 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. Permutacije posmatramo u leksikografskom poretku. Ukupno ih ima $6!=720 .$ Mesto po mesto određujemo blok u kome je $500 .$ permutacija.

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

\begin{aligned}\text{a}\ldots&:\ 5!=120,\quad\text{mesta }1\text{–}120\\\text{b}\ldots&:\ 5!=120,\quad\text{mesta }121\text{–}240\\\text{c}\ldots&:\ 5!=120,\quad\text{mesta }241\text{–}360\\\text{d}\ldots&:\ 5!=120,\quad\text{mesta }361\text{–}480\\\text{e}\ldots&:\ 5!=120,\quad\text{mesta }481\text{–}600\end{aligned}

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

\begin{aligned}\text{ea}\ldots&:\ 4!=24,\quad\text{mesta }481\text{–}504\end{aligned}

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

\begin{aligned}\text{eab}\ldots&:\ 3!=6,\quad\text{mesta }481\text{–}486\\\text{eac}\ldots&:\ 3!=6,\quad\text{mesta }487\text{–}492\\\text{ead}\ldots&:\ 3!=6,\quad\text{mesta }493\text{–}498\\\text{eaf}\ldots&:\ 3!=6,\quad\text{mesta }499\text{–}504\end{aligned}

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

\begin{aligned}\text{eafb}\ldots&:\ 2!=2,\quad\text{mesta }499\text{–}500\end{aligned}

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

\begin{aligned}\text{eafbc}\ldots&:\ 1,\quad\text{mesta }499\text{–}499\\\text{eafbd}\ldots&:\ 1,\quad\text{mesta }500\text{–}500\end{aligned}

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

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

Započni učenje

Privatni časovi

431

Beleške

Slični zadaci

Slični zadaci