Permütasyonda Düzensizlik

Question

Permütasyon sorularinin cözümünde kullanılan bir formül var.  n tane nesne icin düzensizlik sayisi:

$n!\left( \dfrac {1} {0!}-\dfrac {1} {1!}+\dfrac {1} {2!}-\dfrac {1} {3!}+\ldots \dfrac {1} {n!}\right)$

Örnegin:

4 kisi bir kafede birbirlerinden farklı sipariş veriyorlar. Garson siparişleri rastgele dagitiyor. Buna gore, bu kişilerden hicbirinin kendi siparişini almadığı kaç durum vardir? 

Neden "tüm durum- herkesin kendi siparişini aldığı durum" diye düşünemiyoruz?

Bu formülün cikis noktasi nedir?

Ödül 25 puan.

Comments

Neden cevaba yazılmadan ödüllü kategorisi yapıldı ödül nekadar?

---

Anıl unutmusum puani eklemeyi simdi ekledim

Answer 1

Siparişlere sırasıyla $S1,S2,S3,S4$ diyelim. Bu siparişler dağıtılırken, hiçbirinin kendi siparişini almadığı durum sayısı, düzensiz permütasyon formülünden

$P(4) = 4!(1-1/1! + 1/2! - 1/3! + 1/4!)$ den $9$ olarak bulunur.

Şimdi üşenmeden tek tek yazalım.

$n = 1$ için $P(1) = 0$ dır.

$n= 2$ için $P(2) = 1$ olur. $(S2,S1)$

$n = 3$ için $P(3) = 2$ olur. $(S2,S3,S1), (S3,S1,S2)$

$n = 4$ için $P(4) = 9$ olarak hesapladık ama diyelim ki bu formülü bilmiyoruz. Bunu farklı bir şekilde hesaplayalım.

$S1$ in 1.sırada olduğu permütasyonları $X1$, $S2$ nin 2.sırada olduğu permütasyonlara $f(X2)$, $X3$ ün 3.sırada olduğu permütasyonlara $f(X3)$, $X4$ ün 4.sırada olduğu permütasyonlara $f(X4)$ diyelim.

Ve bunların permütasyon sayılarını $f(X1) , f(X2)...$ şeklinde gösterelim.

$f(X1)$ i kolayca hesaplarız. $S1$ sabit kalır. Diğerleri kendi aralarında $3!$ farklı şekilde sıralanır.

Buradan $f(X1) = f(X2) = f(X3) = f(X4) = 3!$ elde ederiz.

Aynı şekilde $f(X1,X2)$ ifadesini hesaplamak için $S1$ ve $S2$ yi sabit tutarız. Geri kalanlar kendi aralarında $2!$ farklı şekilde sıralanır.

Buradan $f(X1,X2) = f(X1,X3) = f(X2,X4)=.....=2!$ sonucu çıkar. Buradan $C(4,2)$ tane ifade vardır.

Aynı şekilde $f(X1,X2,X3)=......=1!$ $C(4,3)$ tane.

$f(X1,X2,X3,X4) = 0! = 1$

Ve dahiliyet hariciyet prensibinden

$P(4) = 4! - 4.3! + C(4,2).2! - C(4,3).1! + C(4,4).0!$

$P(4) = 4!(1 - 1/1! + 1/2! - 1/3! + 1/4!)$ elde edilir.

Senin soruna gelecek olursak

Bütün durumlar $4! = 24$

ve herkesin kendi siparişini aldığı $1$ durum vardır. Halbuki $3$ kişi kendi siparişini almaz, 4.kişi kendi siparişini alır. Bu tür durumlarda var

Comments

@Dogukan633 elinize saglik, güzel bir cözüm simdi daha iyi anladim.

---

Dogukana ödülü veriyor musunuz?

---

Evet dusebilirsin benden :)

Answer 2

Bu formülden ziyade bozuk düzen ile ilgili.

Bozuk düzen '' n tane nesnenin sıralamasında hiçbirinin olması gerektiği yerde olmadığı durumlardır.''

Mesela (x,y,z,t) dörtlüsü için hiç bir elemanın verilen şekilde olmadığı kaç durum vardır gibi.Ya da yukarıda verilen örnek gibi.Bu tip soruları alt faktöriyel ile çözüyoruz. !n  ile gösterilir.Yukarıda verilen formül aslında alt faktöriyelin formül açılımı.Aslı ise şudur.

'' n tane nesne bozuk düzende !n (alt faktöriyel) şekilde sıralanır.

$$!n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!} $$

ile hesaplanır.

Bu tip soruların çözümü için açılım yapılırken ilk iki ifade

 $\dfrac{1}{0!}-\dfrac{1}{1!} $ zaten sadeleşeceğinden yapılması gereken 2'nin faktöriyelinden başlayıp (binom açılımındaki mantık gibi sırasıyla + - ile gidilerek) n (nesne sayısının)'nin  faktöriyeline kadar açıp payda eşitlemektir.Bulunan sonuç n! ile çarpılır.Merakı fazla olmayan öğrenciler için hem sıkıcı olmaz hem de iş görür kanaatindeyim.Formülün çıkış mantığı (ispatı) notlarımın arasındaydı bulunca ekleyebilirim.

Comments

Acikcasi merak ediyorum cikis noktasini, bulunca eklerseniz sevinirim:) tesekkur ederim 

---

Bir sırada sıralanmış n tane $({n_1,n_2,n_3,...,n_n}) $ elemanın yerlerinden ayrılıp tekrar sıralandıklarında hiç birinin ilk yerinde olmadığı bir durumları ele alalım.

Tüm sıralamaların sayısına $A_0 $    diyelim. $A_0=n! $  dir.

$n_1 $ in kendi yerinde olduğu sıra sayısı $(n-1)! $ dir.Buna göre en az birinin kendi yerinde olduğu sıra sayısı $A_1=C(n,1).(n-1)! $ dir.

$n_1 $ ve $ n_2 $ nin kerndi yerinde olduğu sıra sayısı $(n-2)! $ dir.Buna göre en az ikisinin kendi yerinde olduğu sıraların sayısı $A_2=C(n,2).(n-2)! $    dir.

$n_1,n_2,n_3 $ ün kendi yerinde olduğu sıraların sayısı$(n-3)! $ dir.Buna göre en az üçünün kendi yerinde olduğu sıraların sayısı $A_3=C(n,3).(n-3)! $ dir.

...

En az $(n-1) $ tane elemanın kendi yerinde olduğu sıraların sayısı $A_{n-1}=C(n-1).1! $

Hepsinin kendi yerinde olduğu sıralama sayısı $0! $ ve buna göre $A_n=C(n,n).0! $

O halde n kişiden hiç birinin kendi yerinde olmadığı sıraların sayısı

$A=A_0-A_1+A_2-A_3+...-A_{n-1}+A_n $

$A=n!-C(n,1).(n-1)!+C(n-2).(n-2)!-...+(-1)^{n-1}.C(n,n-1).1!+(-1)^n.C(n,n).0! $

Buradaki A sayısına n 'nin alt faktöriyeli denir.!n ile gösterilir.Gerekli kombinasyon açılımlarını yaparsak

$!n=n!-\dfrac{n!}{1!}+\dfrac{n!}{2!}-\dfrac{n!}{3!}+...+(-1)^n.\dfrac{n!}{n!} $

$!n=n!.(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+(-1)^n.\dfrac{1}{n!}) $

$$!n=n!.\sum_{k=0}^n\dfrac{(-1)^k}{k!} $$ elde edilir.