v1 · padrão canônico

Lekcja 37 — Permutacje i układy

Permutacja całkowita Pn = n!. Układ A(n,p). Kiedy kolejność ma znaczenie.

Used in: 1. rok Liceum (15 lat) · Equiv. Math A japoński · Equiv. Klasse 10 niemiecki

P_n = n!, \qquad A_n^p = \frac{n!}{(n-p)!}

Choose your door

Rigorous notation, full derivation, hypotheses

Definicje i demonstracje

Silnia

"Definiujemy silnię liczby $n$ jako $n! = n(n-1)(n-2) \cdots 2 \cdot 1$ dla $n \geq 1$ , i $0! = 1$ ." — OpenStax Algebra and Trigonometry 2e, §11.7

Wzrost silni:

Superwykładniczy wzrost n!. Przybliżenie Stirlinga: n! ≈ √(2πn)·(n/e)ⁿ.

Permutacja z powtórzeniami

Dla $n$ obiektów z $n_1$ typu 1, $n_2$ typu 2, ..., $n_k$ typu $k$ (gdzie $n_1 + n_2 + \cdots + n_k = n$ ):

P_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}

what this means · Dzielimy przez n_i! ponieważ zamiana równych elementów typu i między sobą nie generuje nowej konfiguracji.

Anagramy "ARARA" (3 A, 2 R): $5!/(3! \cdot 2!) = 10$ .

"Liczba rozróżnialnych permutacji $n$ obiektów gdzie znajduje się $n_1$ identycznych obiektów typu 1, $n_2$ typu 2, ..., i $n_r$ typu $r$ , to $\frac{n!}{n_1! n_2! \cdots n_r!}$ ." — OpenStax Algebra and Trigonometry 2e, §11.7

$n$ obiektów w okręgu: $(n-1)!$ . Powód: "pierwsza pozycja" jest arbitralna — obracanie wszystkich razem nie generuje nowej konfiguracji. Formalnie: ustal jeden obiekt w pozycji; pozostałe $n-1$ permutują swobodnie.

Przykłady rozwiązane

Example— 1· Bezpośredni rachunek układu

Problem: Oblicz $A_8^3$ — na ile sposobów wybrać i porządkować 3 obiekty spośród 8 dostępnych.

Strategia: Zastosuj wzór $A_n^p = n!/(n-p)!$ , lub równoważnie $A_n^p = n(n-1)\cdots(n-p+1)$ ( $p$ czynników zstępujących ze względu na $n$ ).

Rozwiązanie:

Forma silniowa: $A_8^3 = \dfrac{8!}{(8-3)!} = \dfrac{8!}{5!} = \dfrac{8 \cdot 7 \cdot 6 \cdot 5!}{5!} = 8 \cdot 7 \cdot 6$ .
Mnożenie: $8 \cdot 7 = 56$ i $56 \cdot 6 = 336$ .
Wynik: $A_8^3 = 336$ .

Weryfikacja: Poprzez bezpośredni rachunek poprzez PFC (1. pozycja: 8 opcji; 2.: 7; 3.: 6) otrzymujemy $8 \cdot 7 \cdot 6 = 336$ . Konsystentne.

Źródło. OpenStax Algebra and Trigonometry 2e §11.7 — licencja CC-BY 4.0.

Example— 2· Anagramy z powtórzeniami liter

Problem: Ile różnych anagramów można utworzyć ze słowa "BANANA"?

Strategia: Słowo ma 6 liter z powtórzeniami: 3 litery A, 2 litery N i 1 litera B. Zastosuj wzór permutacji z powtórzeniami.

Rozwiązanie:

Identyfikuj mnożniki: $n = 6$ , $n_A = 3$ , $n_N = 2$ , $n_B = 1$ .
Zastosuj wzór: $P_6^{3,2,1} = \dfrac{6!}{3! \cdot 2! \cdot 1!}$ .
Oblicz: $6! = 720$ , $3! = 6$ , $2! = 2$ , $1! = 1$ . Stąd $720/(6 \cdot 2 \cdot 1) = 720/12 = 60$ .

Weryfikacja: Bez dzielenia przez powtórzenia, mielibyśmy $6! = 720$ permutacji, ale zamiany między 3 równymi A nie generują nowego anagramu ( $3! = 6$ permutacji identyczne), i zamiany między 2 N generują $2! = 2$ permutacji identyczne. $720/(6 \cdot 2) = 60$ .

Źródło. Wikilivros — Matemática elementar / Combinatória — licencja CC-BY-SA.

Example— 3· Permutacja kołowa z ograniczeniem

Problem: 8 osób będzie siedział wokół okrągłego stołu. Dwie z nich, Ana i Bruno, chcą siedzieć razem. Ile odrębnych konfiguracji?

Strategia: Potraktuj Anę i Bruno jako jeden blok. Pozostaje wtedy 7 "obiektów" do rozmieszczenia wokół okrągłego stołu: $(7-1)! = 6!$ . Wewnątrz bloku, Ana i Bruno mogą zamieniać się: $2!$ sposobów.

Rozwiązanie:

Blok "AB" + 6 innych osób = 7 obiektów wokół okrągłego stołu: $(7-1)! = 6! = 720$ .
Permutacja wewnętrzna bloku: $2! = 2$ (AB lub BA).
Razem: $720 \cdot 2 = 1\,440$ .

Weryfikacja: Bez ograniczenia, 8 osób wokół okrągłego stołu daje $7! = 5\,040$ konfiguracji. Biorąc pozycję Any, Bruno ma 2 możliwych sąsiadów spośród 7 pozostałych miejsc — ułamek $2/7$ . $5\,040 \cdot 2/7 = 1\,440$ . Konsystentne.

Źródło. Wikilivros — Matemática elementar / Combinatória — licencja CC-BY-SA.

Example— 4· Rozwiązanie równania silniowego

Problem: Określ wartość $n \in \mathbb{N}$ spełniającą $\dfrac{(n+2)!}{n!} = 56$ .

Strategia: Uprościć iloraz silni używając $(n+2)! = (n+2)(n+1) \cdot n!$ , redukując do równania wielomianowego w $n$ .

Rozwiązanie:

Uprość: $\dfrac{(n+2)!}{n!} = \dfrac{(n+2)(n+1) \cdot n!}{n!} = (n+2)(n+1)$ .
Równanie: $(n+2)(n+1) = 56$ , czyli $n^2 + 3n + 2 = 56 \Rightarrow n^2 + 3n - 54 = 0$ .
Formuła Bhaskary: $n = \dfrac{-3 \pm \sqrt{9 + 216}}{2} = \dfrac{-3 \pm 15}{2}$ . Rozwiązania: $n = 6$ lub $n = -9$ .
Ponieważ $n \in \mathbb{N}$ , odrzucamy $n = -9$ . Odpowiedź: $n = 6$ .

Weryfikacja: $(6+2)!/6! = 8!/6! = 8 \cdot 7 = 56$ . Zgadza się.

Źródło. Stitz–Zeager Precalculus §9.5 — licencja CC-BY-NC-SA.

Example— 5· Hasła z ograniczeniem pozycyjnym

Problem: Hasło ma 5 znaków, wszystkie różne, wybrane z alfabetu $\{A, B, C, \ldots, Z\}$ (26 liter). Z wymogu, pierwszy znak musi być samogłoską ( $A, E, I, O, U$ ). Ile odrębnych haseł istnieje?

Strategia: Poprzez PFC: zliczyć pierwszą pozycję (samogłoska) i następnie układ 4 pozycji pozostałych spośród 25 liter, które pozostały.

Rozwiązanie:

Pierwszy znak: 5 opcji (samogłoski).
Następne 4 pozycje: układ $A_{25}^4 = 25 \cdot 24 \cdot 23 \cdot 22$ , ponieważ bez powtórzenia.
Rachunek: $25 \cdot 24 = 600$ , $600 \cdot 23 = 13\,800$ , $13\,800 \cdot 22 = 303\,600$ .
Razem: $5 \cdot 303\,600 = 1\,518\,000$ .

Weryfikacja: Bez ograniczenia, $A_{26}^5 = 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 = 7\,893\,600$ . Ułamek haseł zaczynających się samogłoską to $5/26$ . $7\,893\,600 \cdot 5/26 = 1\,518\,000$ . Konsystentne.

Źródło. OpenStax Algebra and Trigonometry 2e §11.7 — licencja CC-BY 4.0.

Exercise list

46 exercises · 11 with worked solution (25%)

Application 32Understanding 4Modeling 8Challenge 1Proof 1

Ex. 37.1Application
Oblicz $5!$ .
Solve online
Ex. 37.2Application
Oblicz $8!/5!$ .
Solve online
Ex. 37.3ApplicationAnswer key
Ile anagramów "MAR" istnieje?
Solve online
Ex. 37.4Application
Ile anagramów "CASA" istnieje?
Solve online
Ex. 37.5Application
Ile anagramów "MISSISSIPPI" istnieje?
Solve online
Ex. 37.6ApplicationAnswer key
Oblicz $A_5^3$ .
Solve online
Ex. 37.7Application
Oblicz $A_8^2$ .
Solve online
Ex. 37.8ApplicationAnswer key
Ile kolejek z 4 osób można utworzyć z 7 kandydatów?
Solve online
Ex. 37.9Application
Nagroda 1., 2., 3. wśród 12 sportowców. Ile odrębnych podium jest możliwych?
Solve online
Ex. 37.10Application
Ile liczb 3-cyfrowych z różnymi cyframi można utworzyć z $\{1, 2, 3, 4, 5\}$ ?
Solve online
Ex. 37.11ApplicationAnswer key
Sprawdź równość $7!/(7-3)! = 7 \cdot 6 \cdot 5$ .
Solve online
Ex. 37.12Application
Rozwiąż $n! = 720$ .
Solve online
Ex. 37.13Application
Rozwiąż $A_n^2 = 30$ dla $n \in \mathbb{N}$ .
Solve online
Ex. 37.14ApplicationAnswer key
Ile anagramów "CIDADE" istnieje?
Solve online
Ex. 37.15Application
Ile anagramów "BANANA" istnieje?
Solve online
Ex. 37.16ApplicationAnswer key
Ile haseł z 5 różnymi cyframi można utworzyć z cyfr $\{0, 1, \ldots, 9\}$ ?
Solve online
Ex. 37.17Application
Na ile sposobów 6 odrębnych książek może być umieszczone na 3 półkach (2 na każdą), uwzględniając kolejność w każdej półce?
Solve online
Ex. 37.18Application
8 osób wokół okrągłego stołu. Ile odrębnych konfiguracji?
Solve online
Ex. 37.19Understanding
Uzasadnij, dlaczego permutacja kołowa $n$ osób wynosi $(n-1)!$ , a nie $n!$ .
Solve online
Ex. 37.20Application
Ile anagramów "AMOR" zaczynających się literą A?
Solve online
Ex. 37.21Application
Ile anagramów "MATEMATICA" istnieje?
Solve online
Ex. 37.22Application
Ile anagramów "PROVA" zaczynających się spółgłoską?
Solve online
Ex. 37.23Application
Anagramy "AMOR" z A i O razem w tej kolejności (blok "AO" niepodzielny).
Solve online
Ex. 37.24ApplicationAnswer key
10 studentów będzie siadać na 10 krzesłach w linii. 2 przyjaciół chcą być razem. Ile konfiguracji?
Solve online
Ex. 37.25Application
8 osób wokół okrągłego stołu; 2 chcą być razem. Ile konfiguracji?
Solve online
Ex. 37.26Application
Anagramy "LIVRO" zaczynające się samogłoską.
Solve online
Ex. 37.27ApplicationAnswer key
Ile liczb 4-cyfrowych z różnymi cyframi można utworzyć z cyfr $\{1, \ldots, 9\}$ ?
Solve online
Ex. 37.28Application
Ile parzystych liczb 4-cyfrowych z różnymi cyframi można utworzyć z cyfr $\{1, 2, 3, 4, 5\}$ ?
Solve online
Ex. 37.29Application
Rozwiąż $n!/(n-3)! = 60$ dla $n \in \mathbb{N}$ .
Solve online
Ex. 37.30Application
Rozwiąż $(n+1)!/n! = 5$ .
Solve online
Ex. 37.31Application
W wysicigu z 10 sportowcami, ile odrębnych podium (1., 2., 3.) może się zdarzyć?
Solve online
Ex. 37.32Application
Ile anagramów "FATORIAL" istnieje (wszystkie litery odrębne)?
Solve online
Ex. 37.33Application
Pięć kart wybranych i uporządkowanych w kolejce z 7 odrębnych kart — ile konfiguracji?
Solve online
Ex. 37.34Understanding
Sprawdź rekurencję $A_n^p = n \cdot A_{n-1}^{p-1}$ dla $n = 6, p = 3$ .
Solve online
Ex. 37.35Modeling
Drużyna piłki nożnej: 11 graczy zajmuje 11 odrębnych pozycji na boisku. Ile postawień z pozycjonowaniem istnieje?
Solve online
Ex. 37.36Modeling
Hasła z 8 znakkami alfabetycznymi małymi bez powtórzenia. Ile odrębnych haseł istnieje?
Solve online
Ex. 37.37ModelingAnswer key
W logistyce, jaka jest liczba możliwych porządków dostarczenia 10 odrębnych pakietów do 10 miejsc docelowych?
Solve online
Ex. 37.38Modeling
W grze w karty, ile odrębnych konfiguracji talii 52 kart istnieje po tasowaniu?
Solve online
Ex. 37.39Modeling
W DNA, sekwencja 8 zasad (A, T, C, G) gdzie każda baza pojawia się dokładnie 2 razy. Ile odrębnych sekwencji istnieje?
Solve online
Ex. 37.40Modeling
W populacyjnej genetyce, ile możliwych porządków istnieje do uporządkowania 4 odrębnych aleli w łańcuchu?
Solve online
Ex. 37.41Modeling
W uczeniu maszynowym, ważność cechy permutacji tasuje cechę nad $N$ próbkami i mierzy spadek w predykcji. Ile możliwych permutacji istnieje $N$ próbek?
Solve online
Ex. 37.42Modeling
W grafice komputerowej, ile porządków renderowania istnieje dla 100 wielokątów?
Solve online
Ex. 37.43Understanding
Udowodnij, że $A_n^p = n \cdot A_{n-1}^{p-1}$ .
Solve online
Ex. 37.44UnderstandingAnswer key
Pokaż, że $P_n = A_n^n$ .
Solve online
Ex. 37.45Challenge
Ile anagramów "AMOR" zaczynających się spółgłoską i kończących się samogłoską?
Solve online
Ex. 37.46ProofAnswer key
Udowodnij, że $A_n^p = n!/(n-p)!$ używając Fundamentalnej Zasady Liczenia.
Solve online

Źródła

Tylko książki, które bezpośrednio zawiesiły tekst i ćwiczenia.

OpenStax Algebra and Trigonometry 2e — Jay Abramson i inni · 2022, wyd. 2 · EN · CC-BY 4.0 · §11.7 Counting Principles. Źródło pierwotne.
Wikilivros — Matemática elementar / Combinatória — kolaboratywne · PT-BR · CC-BY-SA · permutacje, układy, anagramy. Źródło rodzime w języku portugalskim.
Stitz–Zeager Precalculus — Carl Stitz, Jeff Zeager · 2013, v3 · EN · CC-BY-NC-SA · §9.5 Counting.
Book of Proof — Richard Hammack · 2018, wyd. 3 · EN · CC-BY-ND · roz. 3.

Lekcja 37 — Permutacje i układy

Definicje i demonstracje

Silnia

Permutacja prosta

Permutacja z powtórzeniami

Układ prosty

Permutacja kołowa

Przykłady rozwiązane

Exercise list

Źródła