Sayma Algoritma Bilişim Ders Notu

Matematikte sayma, belirli koşullara uyan elemanların veya durumların sayısını bulma işlemidir. Bu konu, bilgisayar bilimleri ve algoritmaların temelini oluşturan mantıksal düşünme becerilerini geliştirir. Sayma yöntemleri, permütasyon, kombinasyon ve binom açılımı gibi kavramlar, günlük hayatta karşılaştığımız birçok problemin çözümünde bize yol gösterir.

Sayma Yöntemleri 🔢

Bir kümenin elemanlarını veya bir olayın farklı gerçekleşme biçimlerini saymak için temel iki yöntem kullanılır: Toplama Yoluyla Sayma ve Çarpma Yoluyla Sayma.

Toplama Yoluyla Sayma ➕

İki veya daha fazla ayrık olayın gerçekleşme biçimlerinin toplamını bulmak için kullanılır. Eğer \( A \) olayı \( n \) farklı şekilde ve \( B \) olayı \( m \) farklı şekilde gerçekleşiyorsa ve bu iki olay aynı anda gerçekleşemiyorsa, \( A \) veya \( B \) olaylarından biri \( n + m \) farklı şekilde gerçekleşebilir.

• Kural: Ayrık olayların toplamı.

Örnek: Bir sınıfta 15 kız ve 12 erkek öğrenci bulunmaktadır. Bu sınıftan rastgele bir öğrenci kaç farklı şekilde seçilebilir?

Kız öğrenci seçimi \( = 15 \) farklı yol.
Erkek öğrenci seçimi \( = 12 \) farklı yol.
Bir öğrenci seçimi (kız veya erkek) \( = 15 + 12 = 27 \) farklı yol.

Çarpma Yoluyla Sayma \times

İki veya daha fazla olayın art arda veya aynı anda gerçekleştiği durumlarda kullanılır. Eğer birinci olay \( n \) farklı şekilde ve bu birinci olaya bağlı olarak ikinci olay \( m \) farklı şekilde gerçekleşiyorsa, bu iki olay art arda \( n \times m \) farklı şekilde gerçekleşebilir.

• Kural: Ardışık veya eş zamanlı olayların çarpımı.

Örnek: Bir yemekhanede 3 çeşit çorba, 4 çeşit ana yemek ve 2 çeşit tatlı bulunmaktadır. Bir öğrenci bir çorba, bir ana yemek ve bir tatlıyı kaç farklı şekilde seçebilir?

Çorba seçimi \( = 3 \) farklı yol.
Ana yemek seçimi \( = 4 \) farklı yol.
Tatlı seçimi \( = 2 \) farklı yol.
Toplam seçim \( = 3 \times 4 \times 2 = 24 \) farklı yol.

Permütasyon (Sıralama) 🔀

Farklı nesnelerin belirli bir sıraya göre dizilişine permütasyon denir. Permütasyonda sıralama önemlidir. "Kaç farklı şekilde sıralanabilir?" veya "Kaç farklı parola oluşturulabilir?" gibi sorular permütasyon ile çözülür.

Tekrarsız Permütasyon

\( n \) farklı elemanın \( r \) tanesinin yan yana sıralanışına \( n \)'nin \( r \)'li permütasyonu denir ve \( P(n, r) \) veya \( P_n^r \) ile gösterilir.

\[ P(n, r) = \frac{n!}{(n-r)!} \]

Burada \( n! \) (n faktöriyel) ifadesi, \( n \) bir doğal sayı olmak üzere, \( 1 \) den \( n \)'ye kadar olan doğal sayıların çarpımını ifade eder.

\[ n! = n \times (n-1) \times (n-2) \times ... \times 1 \]

Özel olarak \( 0! = 1 \) kabul edilir.

• Önemli Not: Permütasyonda elemanların sırası önemlidir ve elemanlar tekrar kullanılmaz (tekrarsız).

Örnek: 5 farklı kitaptan 3 tanesi bir rafa kaç farklı şekilde sıralanabilir?

Bu, 5'in 3'lü permütasyonudur. Yani \( n=5, r=3 \). \[ P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} = 5 \times 4 \times 3 = 60 \] 60 farklı şekilde sıralanabilir.

Tekrarlı Permütasyon

\( n \) tane elemanın bazıları özdeş (aynı) ise, bu elemanların farklı sıralanışlarının sayısını bulmak için tekrarlı permütasyon formülü kullanılır. Eğer \( n \) elemanın içinde \( n_1 \) tanesi birinci türden, \( n_2 \) tanesi ikinci türden, ..., \( n_k \) tanesi \( k \). türden özdeş elemanlar ise (ve \( n_1 + n_2 + ... + n_k = n \)), bu \( n \) elemanın farklı sıralanış sayısı:

\[ \frac{n!}{n_1! \times n_2! \times ... \times n_k!} \]

Örnek: "KELEBEK" kelimesinin harfleri yer değiştirilerek 7 harfli anlamlı veya anlamsız kaç farklı kelime yazılabilir?

Kelime 7 harfli olduğu için \( n=7 \).
Harflerin tekrar sayıları:
K: 2 tane (\( n_1=2 \))
E: 3 tane (\( n_2=3 \))
L: 1 tane (\( n_3=1 \))
B: 1 tane (\( n_4=1 \))
Toplam harf sayısı \( 2+3+1+1=7 \). \[ \frac{7!}{2! \times 3! \times 1! \times 1!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(2 \times 1) \times (3 \times 2 \times 1) \times 1 \times 1} = \frac{5040}{2 \times 6} = \frac{5040}{12} = 420 \] 420 farklı kelime yazılabilir.

Kombinasyon (Seçme) 🤝

Bir kümedeki elemanlardan bir kısmının veya tamamının seçilmesine kombinasyon denir. Kombinasyonda, permütasyonun aksine, seçilen elemanların sırası önemli değildir. Sadece hangi elemanların seçildiği önemlidir. "Kaç farklı grup oluşturulabilir?" veya "Kaç farklı seçim yapılabilir?" gibi sorular kombinasyon ile çözülür.

\( n \) farklı eleman arasından \( r \) tane elemanın seçilme sayısı \( C(n, r) \) veya \( \binom{n}{r} \) (n'in r'li kombinasyonu) ile gösterilir.

\[ C(n, r) = \binom{n}{r} = \frac{n!}{r! \times (n-r)!} \]

• Kural: Seçimlerde sıra önemli değildir.

Örnek: 10 kişilik bir gruptan 3 kişilik bir komite kaç farklı şekilde seçilebilir?

Bu bir kombinasyon problemidir çünkü komitedeki kişilerin sırası önemli değildir. Yani \( n=10, r=3 \). \[ C(10, 3) = \binom{10}{3} = \frac{10!}{3! \times (10-3)!} = \frac{10!}{3! \times 7!} \] \[ = \frac{10 \times 9 \times 8 \times 7!}{3 \times 2 \times 1 \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120 \] 120 farklı komite seçilebilir.

Kombinasyonun Özellikleri:

• \( \binom{n}{0} = 1 \)
• \( \binom{n}{n} = 1 \)
• \( \binom{n}{1} = n \)
• \( \binom{n}{r} = \binom{n}{n-r} \)
• \( \binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1} \) (Pascal Özelliği)

Binom Açılımı (Kombinasyon İlişkisi) 📐

İki terimli bir ifadenin kuvvetlerinin açılımına binom açılımı denir. Kombinasyon kavramı, binom açılımındaki terimlerin katsayılarını bulmak için kullanılır.

\( (x+y)^n \) ifadesinin açılımı aşağıdaki gibidir:

\[ (x+y)^n = \binom{n}{0}x^n y^0 + \binom{n}{1}x^{n-1} y^1 + \binom{n}{2}x^{n-2} y^2 + ... + \binom{n}{n}x^0 y^n \]

Bu açılımda \( n+1 \) tane terim bulunur. Genel terim \( (k+1) \). terim olarak ifade edilir:

\[ T_{k+1} = \binom{n}{k}x^{n-k}y^k \]

• Not: \( n \) bir doğal sayı olmak üzere, \( (x+y)^n \) açılımındaki katsayılar Pascal üçgeni ile de ilişkilidir.

Örnek: \( (a+b)^3 \) ifadesinin açılımını yapınız.

Burada \( n=3 \). \[ (a+b)^3 = \binom{3}{0}a^3 b^0 + \binom{3}{1}a^2 b^1 + \binom{3}{2}a^1 b^2 + \binom{3}{3}a^0 b^3 \] Kombinasyon değerlerini hesaplayalım:
\( \binom{3}{0} = 1 \)
\( \binom{3}{1} = 3 \)
\( \binom{3}{2} = 3 \)
\( \binom{3}{3} = 1 \)
Yerine yazarsak: \[ (a+b)^3 = 1 \cdot a^3 \cdot 1 + 3 \cdot a^2 \cdot b + 3 \cdot a \cdot b^2 + 1 \cdot 1 \cdot b^3 \] \[ (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 \]