Geomania.Org Forumları

Fantezi Cebir => Kombinatorik => Konuyu başlatan: Lokman Gökçe - Mart 08, 2012, 10:37:46 ös

Başlık: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: Lokman Gökçe - Mart 08, 2012, 10:37:46 ös

A = {1, 2, ..., n} kümesi üzerinde tanımlı bire bir ve örten fonksiyonlara permütasyon fonksiyonu denir.  Tersi kendisine eşit kaç farklı permütasyon fonksiyonu vardır?

Örneğin n = 2 için A = {1, 2} olup f₁ = {(1,1), (2,2)} ve f₂ = {(1,2), (2,1)} şeklinde iki tane permütasyon fonksiyonu vardır.

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: senior - Mart 09, 2012, 01:17:48 ös

Hocam, aşağıdaki cevabın daha kısa hali varsa siz de yazın birbirine eşitleyelim :D (toplam sembolünün altındaki i k olacak)

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: Lokman Gökçe - Mart 09, 2012, 02:32:00 ös

ben n nin çift ve tek olması durumlarına göre iki ayrı bağıntı elde etmiştim. sen [n/2] (tam değer fonksiyonu) kullanarak daha iyi ifade etmişsin Güneş kardeşim, tebrikler :)

n = 7 için ve n = 8 için problemi çözerek formülün ispatını ana hatlarıyla ortaya koyabiliriz. ben n = 7 durumunu çözeyim.

n = 7 için A = {1, 2, 3, 4, 5, 6, 7} olur.
Başlangıç için tersi kendisine eşit bir f fonksiyonu örneği verelim. f = {(1,1), (2,2), (3,3), (4,6), (5,7), (6,4), (7,5)} olur. Burada sabit nokta diye bir kavram tanımlayalım. Fonksiyondaki (x, x) şeklindeki noktalara sabit nokta diyelim. Örneğin f nin sabit noktaları (1,1), (2,2), (3,3) şeklinde 3 tanedir. diğer kalan 4 noktada için ikişer tanesi birbirinin simetriği şeklindedir.

O halde n = 7 durumunda f = f^-1 olabilmesi için tek sayıda sabit nokta bulunması gereklidir. Kalan noktalar da yarı yarıya simetrik olmalıdır.

1 tane sabit noktası olan fonksiyonların sayısı = C(7,1).5.3.1 = 105 olur.

3 tane sabit noktası olan fonksiyonların sayısı = C(7,3).3.1 = 105 olur.

5 tane sabit noktası olan fonksiyonların sayısı = C(7,5).1 = 21 olur.

7 tane sabit noktası olan fonksiyonların sayısı = C(7,7) = 1 dir. (Bu aslında I(x)=x özdeş fonksiyonudur)

toplam olarak 105 + 105 + 21 + 1 = 232 tane böyle fonksiyon vardır.

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: Lokman Gökçe - Mart 09, 2012, 02:43:37 ös

bu başlıkla ilgili tübitak 1993 den bir soru ekleyelim. Kolay gelsin...

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: Ferhat GÖLBOL - Mart 09, 2012, 05:48:47 ös

   Hocam, ben de s₁=1 ve s₂=2 olmak üzere s_n=s_n-1+(n-1)s_n-2 özdeşliğini bulmuştum, nasıl formülize edebileceğimi düşünüyordum. Çözümümü paylaşayım, alternatif olsun.

  A_n={1,2,...,n} kümesini düşünelim. Bu kümede, verilen koşulu sağlayan fonksiyon sayısı s_n olsun. n elemanının eşleştiği elemana göre inceleyelim.
  (n,n) elemanını içeren s_n-1 adet fonksiyon vardır: A_n-1={1,2,...,n-1} kümesinde tanımlanan her fonksiyona (n,n) elemanı eklenmiştir.
  (n,n-1) elemanını içeren s_n-2 fonksiyon vardır: A_n-2 kümesinde tanımlanan her fonksiyona (n,n-1) ve (n-1,n) elemanları eklenmiştir.
  (n,n-2) elemanını içeren yine s_n-2 eleman vardır: (n,n-1) elemanını içeren fonksiyonlardaki tüm n-1'ler n-2, tüm n-2'ler n-1 ile değiştirilmiştir.
  Benzer şekilde (n,n-3),...,(n,2),(n,1) elemanlarını içeren s_n-2'şer tane fonksiyon vardır. Toplamda s_n-1+(n-1)s_n-2 fonksiyon bulunur.

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: Lokman Gökçe - Mart 09, 2012, 08:47:39 ös

çözümün çok güzel olmuş Ferhat kardeşim, tebriker :)

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: idensu - Haziran 12, 2012, 07:55:23 ös

Bende ısrarla gönderilen yanıtlara bakmamıştım ve bir çözüm yaptım. Aklın yolu birmiş benden önce zaten arkadaşlar bulmuş ama bende yinede göndereyim dedim.

Başlık: Ynt: Tersi kendisine eşit permütasyon fonksiyonlarının sayısı
Gönderen: alpercay - Haziran 13, 2012, 10:16:59 öö

İnvolusyonlara daha önceden biraz bakmıştık.
http://geomania.org/forum/cebir-teoerem-ve-ispatlar/self-invers-fonksiyonlar-ve-involusyon/