Simetrik grubu kullanarak sayma

Question

$k$ pozitif tamsayısı için $p(k)$ sayısı $S_k$ içinde sabit noktası olmayan permütasyonların sayısı olsun. Bu durumda $$\sum_{a=0}^n\binom{n}{a}p(n-a)=n!$$ eşitliğinin sağlandığını gösterin.

İpucu: $g\in S_n$ için $a(g)$, $g$'nin sabit bıraktığı noktalar sayısı olsun.

Comments

Safak Ozden hocam $p(0)=p(1)=0$, değil mi?

---

Sıfır elemanlı bir küme üzerindeki permütasyonların sayısı sıfır. O halde p(0)=0 olmalı. Diğeri de tanımdan çıkıyor. Evet haklısın yani.

---

Bence  $p(0)=1$ olmalı.(Sanırım ispatta birim permütasyona karşı gelecek)

(Ek 1: http://matkafasi.com/4/%240-%24-neden-1e-esit den $0!=1$ )

Ek 2: $p(0)=0$ olsa, eşitlik  $n=1$ için yanlış olur.

İpucu: $g\in S_n$ için $g$ nin $a$ tane sabit noktası varsa, $g$ yi $S_{n-a}$ nın  sabit noktası olmayan bir elemanı olarak düşünebiliriz.

---

Tümevarımda ilk adım nedir?

---

Tümevarıma gerek yok. Simetrik grubun elemanlarını ayıklayacaksın.

---

Şimdi fark ettim, Doğan hoca zaten nasıl ayıklayacağını da yazmış bir önceki notunda.