Lema 7.10.
Untuk setiap himpunan bagian \(S\subseteq [n]\text{,}\) \(N(S)\) hanya bergantung pada \(|S|\text{.}\) Lebih tepatnya, jika \(|S|=k\text{,}\) maka
\begin{equation*}
N(S) = (n-k)!
\end{equation*}
Subbab 7.4 Permutasi Tanpa Titik Tetap
Sekarang mari kita tinjau suatu situasi yang memungkinkan kita menggunakan sifat-sifat yang didefinisikan dalam Contoh 7.5. Tetapkan suatu bilangan bulat positif \(n\) dan misalkan \(X\) menyatakan himpunan semua permutasi pada \([n]\text{.}\) Suatu permutasi \(\sigma\in X\) disebut permutasi tanpa titik tetap jika \(\sigma(i)\neq i\) untuk setiap \(i=1,2,\dots,n\text{.}\) Sebagai contoh, permutasi \(\sigma\) yang diberikan di bawah ini merupakan permutasi tanpa titik tetap, sedangkan \(\tau\) bukan.
| \(i\) | 1 | 2 | 3 | 4 |
| \(\sigma(i)\) | 2 | 4 | 1 | 3 |
| \(i\) | 1 | 2 | 3 | 4 |
| \(\tau(i)\) | 2 | 4 | 3 | 1 |
Jika sekali lagi kita menetapkan bahwa \(P_i\) adalah sifat \(\sigma(i)=i\text{,}\) permutasi tanpa titik tetap tepat merupakan permutasi yang tidak memenuhi \(P_i\) untuk satu pun \(i=1,2,\dots,n\text{.}\)
Bukti.
Untuk setiap \(i\in S\text{,}\) nilai \(\sigma(i)=i\) telah ditetapkan. Nilai-nilai \(\sigma\) lainnya membentuk suatu permutasi pada \(n-k\) posisi yang tersisa, dan terdapat \((n-k)!\) permutasi semacam itu.
Seperti sebelumnya, hasil utama bagian ini langsung diperoleh dari lemma dan Prinsip Inklusi–Eksklusi.
Teorema 7.11.
Untuk setiap bilangan bulat positif \(n\text{,}\) bilangan \(d_n\) yang menyatakan banyaknya permutasi tanpa titik tetap pada \([n]\) memenuhi
\begin{equation*}
d_n=\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)!.
\end{equation*}
Sebagai contoh,
\begin{align*}
d_5 \amp =\binom{5}{0}5!-\binom{5}{1}4!+\binom{5}{2}3!-\binom{5}{3}2!+
\binom{5}{4}1!-\binom{5}{5}0!\\
\amp =120-120+60-20+5-1\\
\amp =44.
\end{align*}
Sudah menjadi kebiasaan untuk menyajikan topik permutasi tanpa titik tetap dalam bentuk cerita yang disebut masalah Penitipan Topi. Cerita ini berasal dari masa ketika kaum pria mengenakan topi tinggi. Pada sebuah pesta dansa resmi, \(100\) pria menitipkan topi tinggi mereka kepada petugas penitipan topi sebelum memasuki lantai dansa. Kemudian pada malam itu, petugas penitipan topi yang usil memutuskan untuk mengembalikan topi-topi tersebut secara acak. Berapakah peluang bahwa seluruh \(100\) pria menerima topi yang bukan miliknya sendiri? Ternyata jawabannya sangat dekat dengan \(1/e\text{,}\) sebagaimana ditunjukkan oleh hasil berikut.
Teorema 7.12.
Untuk suatu bilangan bulat positif \(n\text{,}\) misalkan \(d_n\) menyatakan banyaknya permutasi tanpa titik tetap pada \([n]\text{.}\) Maka
\begin{equation*}
\lim_{n\rightarrow\infty}\frac{d_n}{n!} = \frac{1}{e}.
\end{equation*}
Dengan kata lain, proporsi seluruh permutasi pada \([n]\) yang merupakan permutasi tanpa titik tetap mendekati \(1/e\) ketika \(n\) membesar.
Bukti.
Mudah dilihat bahwa
\begin{align*}
\frac{d_n}{n!} \amp = \frac{\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)!}{n!}\\
\amp = \sum_{k=0}^n (-1)^k \frac{n!}{k!(n-k)!}\frac{(n-k)!}{n!}\\
\amp = \sum_{k=0}^n (-1)^k \frac{1}{k!}.
\end{align*}
Ingat kembali dari Kalkulus bahwa pengembangan deret Taylor untuk \(e^x\) diberikan oleh
\begin{equation*}
e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!},
\end{equation*}
sehingga hasil tersebut diperoleh dengan menyubstitusikan \(x=-1\text{.}\)
Biasanya kita tidak terlalu tertarik pada \(d_n\) itu sendiri, melainkan pada pencacahan permutasi dengan batasan tertentu, seperti diperlihatkan oleh contoh berikut.
Contoh 7.13.
Perhatikan masalah Penitipan Topi, tetapi sekarang, alih-alih mensyaratkan agar tidak ada pria yang pulang membawa topinya sendiri, kita ingin mengetahui banyaknya cara membagikan \(100\) topi sehingga tepat \(40\) pria pulang membawa topinya sendiri.
Jika \(40\) pria pulang membawa topinya sendiri, ada \(60\) pria yang tidak menerima topi mereka sendiri. Terdapat \(C(100,60)\) cara untuk memilih \(60\) pria yang tidak akan menerima topinya sendiri dan \(d_{60}\) cara untuk membagikan topi-topi tersebut agar tidak seorang pun menerima topinya sendiri. Hanya ada satu cara untuk membagikan \(40\) topi kepada para pria yang harus menerima topinya sendiri. Dengan demikian, terdapat
\begin{align*}
\binom{100}{60}d_{60} =
\amp 420788734922281721283274628333913452107738151595140722182899444\\
\amp 67852500232068048628965153767728913178940196920
\end{align*}
cara untuk mengembalikan topi-topi tersebut.
