Tübitak Lise 1. Aşama 2000 Soru 27

[geo]

$\{1,2,3,4,5\}$ kümesinin, her $1\leq k \leq 4$ için $(\alpha_1\dots \alpha_k)$, $\{1,\dots, k\}$ kümesinin bir permütasyonu olmayacak şekilde kaç değişik $(\alpha_1\alpha_2\alpha_3\alpha_4\alpha_5)$ permütasyonu vardır?

$
\textbf{a)}\ 13
\qquad\textbf{b)}\ 65
\qquad\textbf{c)}\ 71
\qquad\textbf{d)}\ 461
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[geo]

Yanıt: $\boxed{C}$

$\{1,2,3,4,5\}$ kümesinin toplamda $5!=120$ permütasyonu var. Bunlardan
her $1\leq k \leq 4$ için $(\alpha_1\dots \alpha_k)$, $\{1,\dots, k\}$ kümesinin bir permütasyonu olan  $(\alpha_1\alpha_2\alpha_3\alpha_4\alpha_5)$ leri çıkartırsak sonucu elde ederiz.
$k=1$ için $(1\overbrace{\cdot \cdot \cdot \cdot}^{4!}) \rightarrow 24$
$k=2$ için $\{1,2\}$ kümesinin toplamda $2!$ permütasyonu var. Bunlardan biri $k=1$ de geçen $(12\alpha_3\alpha_4\alpha_5)$ permütasyonu olduğu için $(\overbrace{21}^{2!-1}\overbrace{\cdot \cdot \cdot}^{\text{Geriye kalanlar } 3!}) \rightarrow 6 $
$k=3$ için $\{1,2,3\}$ kümesinin toplamda $3!$ permütasyonu var. Bunlardan ikisi $k=1$ de geçen $(1\overbrace{\cdot \cdot}^{2,3}\alpha_4\alpha_5)$ permütasyonu, biri de $k=2$ de geçen $(21\overbrace{3}^{1 \text { tane}}\alpha_4\alpha_5)$ permütasyonu olduğu için $(\overbrace{\cdot \cdot \cdot}^{3!- 2! - 1}\overbrace{\cdot \cdot}^{\text{Geriye kalanlar }2!}) \rightarrow 6 $
$k=4$ için $\{1,2,3,4\}$ kümesinin toplamda $4!$ permütasyonu var. Bunlardan $3!$ tanesi $k=1$ de geçen $(1\overbrace{\cdot \cdot \cdot}^{2, 3, 4}5)$ permütasyonu, $2!$ tanesi $k=2$ de geçen $(21\overbrace{\cdot \cdot}^{3,4}5)$ permütasyonu ve $3$ tanesi de $k=3$ de geçen tüm permütasyonlar olduğu için $(\overbrace{\cdot \cdot \cdot \cdot}^{4!- 3! - 2! - 3}5) \rightarrow 13 $
$$120 - 24 - 6 - 6 - 13 =71$$

[geo]

İndirgenemez (Irreducible) ya da başka bir deyişle Ayrıştırılamaz (Indecomposable) Permütasyonların sayısı sorulmuş. (bkz. oeis/A003319)

$P_n$ ile $\{1, \dots, n\}$ kümesinin permütasyonlarını, $|P_n|=n!$ ile de permütasyonların sayısını gösterelim.
$P=(\alpha_1 \dots \alpha_n)$ permütasyonu için, ($1\leq k \leq n$ olmak üzere) $(\alpha_1\dots \alpha_k)$, $\{1, \dots, k\}$ kümesinin bir permütasyonu olacak şekilde seçilebilecek $k$ sayılarının en küçüğüne, permütasyonun derecesi, $\text{der} P$, diyelim. (Permütasyon tanımında derece ile başka bir şey ifade ediliyor olabilir; bu soruda o tanımı ezdiğimizi düşünelim.)
$Q_n$ ile de $\{1,\dots, n\}$ kümesinin, her $1\leq k \leq n-1$ için $(\alpha_1\dots \alpha_k)$, $\{1,\dots, k\}$ kümesinin bir permütasyonu olmayacak şekilde oluşturulan $(\alpha_1\dots\alpha_n)$ permütasyonlarını gösterelim.
$Q_1 = \{(1)\}$ ve $Q_2 = \{(21)\}$ dir. Soruda bizden $|Q_5|$ i bulmamız isteniyor.
$1\leq i \leq n$ için $D_i = \{P \in P_n \mid \text {der} P = i\}$ olsun. $i \neq j$ için $D_i \cap D_j = \emptyset$ ve $P_n = D_1 \cup \dots \cup D_n$ olacaktır.
Öncelikle, $D_n= \{P \in P_n \mid \text {der} P = n\} = Q_n$ olduğunu fark edelim.
$Q \in Q_i$ permütasyonuna $\{i+1, \dots, n\}$ kümesine ait bir permütasyon eklemlersek $D \in D_i$ permütasyonunu elde ederiz.
Bu durumda $n! = |P_n| = |Q_n| + |Q_{n-1}|\cdot 1! + |Q_{n-2}|\cdot 2! + \dots + |Q_{1}|\cdot (n-1)! = \displaystyle \sum_{i=1}^{n} |Q_i|\cdot (n-i)!$

$|P_3| = 3! = |Q_3| + |Q_2|\cdot 1! + |Q_1|\cdot 2! \Longrightarrow |Q_3| = 3! - 1 - 2 = 3$.

$|P_4| = 4! = |Q_4| + |Q_3|\cdot 1! + |Q_2|\cdot 2! + |Q_1| \cdot 3! \Longrightarrow |Q_4| = 4! - 3 - 2 - 6 = 13$.

$|P_5| = 5! = |Q_5| + |Q_4|\cdot 1! + |Q_3|\cdot 2! + |Q_2| \cdot 3! + |Q_1| \cdot 4! \Longrightarrow |Q_5| = 5! - 13 - 6 - 6 - 24 = 71$.