Faktöriyel fonksiyonu

Özyinelemenin ilk örneği olarak, faktöriyel fonksiyonunu nasıl hesaplayacağımıza bakalım. $n$‍nin faktöriyelini $n!$‍ şeklinde gösteririz. Bu, sadece 1'den $n$‍'ye tam sayıların çarpımıdır. Örneğin 5!, $1\cdot 2\cdot 3\cdot 4\cdot 5$‍ veya 120'ye eşittir. (Not: Faktöriyel fonksiyonundan bahsederken, ünlem işaretleri vurgu için değildir, faktöriyel fonksiyonuyla ilgilidir.)

Faktöriyel fonksiyonunun neden önemli olduğunu merak ediyor olabilirsiniz. Bazı şeyleri sıralamak için veya birleştirmek için kaç yol olduğunu saymaya çalışırken çok faydalıdır. Örneğin, $n$‍ şeyi kaç değişik şekilde sıralayabiliriz? Birinci şey için $n$‍ seçeneğimiz var. Bu $n$‍ seçeneğin her biri için, ikinci şeye $n-1$‍seçenek kalır; yani sırasıyla, ilk iki şey için $n\cdot (n-1)$‍ seçenek olur. Şimdi, bu ilk iki seçeneğin her biri için, üçüncü şeye $n-2$‍ seçenek kalır, böylece, ilk üç şey için sırasıyla $n\cdot (n-1)\cdot (n-2)$‍ seçenek olur. Sadece iki şey ve sonra da bir şey kalana kadar böyle devam ederiz. Hepsi birlikte, $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$‍ yolla $n$‍ şeyi sıralayabiliriz. Bu çarpım, $n!$‍ ($n$‍ faktöriyeldir), ama çarpım 1'den $n$‍'ye gitmek yerine, $n$‍'den 1'e gider.

Faktöriyel fonksiyonunun başka bir kullanımı, bir şeylerin oluşturduğu gruptan bazı şeyleri kaç şekilde seçebileceğinizi saymaktır. Örneğin, bir yolculuğa gittiğinizi ve yanınızda hangi tişörtleri götüreceğinizi seçmek istediğinizi düşünün. Diyelim ki, $n$‍ tişörtünüz var, ama bunların sadece $k$‍ tanesi için bavulunuzda yer var. $n$‍ tişörtlük bir gruptan, $k$‍ tişörtü kaç değişik şekilde seçebiliriz? (Burada ispatlamaya çalışmasak da) cevap $n!/(k!\cdot (n-k)!)$‍ olur. Bu yüzden, faktöriyel fonksiyonu çok faydalı olabilir. Burada permütasyon ve kombinasyonla ilgili daha fazla bilgi alabilirsiniz, ama faktöriyel algoritmasını uygulamak için bunları anlamak zorunda değilsiniz.

Faktöriyel fonksiyonu, 0 ile birlikte, tüm pozitif tam sayılar için tanımlıdır. 0! hangi değere sahip olmalıdır? Bu, 1'den büyük veya eşit ve 0'dan küçük veya eşit tüm tam sayıların çarpımıdır. Ama böyle bir tam sayı yoktur. Dolayısıyla, 0! 'i çarpmanın birim elemanı yani 1 olarak tanımlarız. (0! = 1 tanımı, $n$‍ şeyden $k$‍ şey seçme formülüyle iyi uyuşur. Diyelim ki, $n$‍ şeyden $n$‍ şeyi nasıl seçebileceğimizi bilmek istiyoruz. Bu kolay, çünkü sadece bir yol vardır: $n$‍ şeyin hepsini seçmek. Artık formülümüzü kullandığımızda, $n!/(n!\cdot (n-n)!)$‍ 'in 1'e eşit olması gerektiğini biliyoruz. Ancak $(n-n)!$‍ 0!'dir, dolayısıyla artık $n!/(n!\cdot 0!)$‍ 'in 1'e eşit olması gerektiğini biliyoruz. Pay ve paydada $n!$‍'i sadeleştirirsek, $1/(0!)$‍ 'in 1'e eşit olması gerektiğini biliyoruz, ve öyledir çünkü 0! 1'e eşittir.)

Artık $n!$‍'i düşünmek için bir yolumuz var. $n=0$‍ olduğunda 1'e eşit olur, ve $n$‍ pozitif olduğunda $1\cdot 2\cdots (n-1)\cdot n$‍'e eşit olur.

Bu içerik Dartmouth Bilgisayar Bilimleri öğretim görevlileri Thomas Cormen ve Devin Balkcom ile Khan Academy bilgisayar bölümü içeriklerini hazırlayan takımın işbirliği ile hazırlanmıştır. İçerik CC-BY-NC-SA lisanslıdır.