Faktöriyel

Seçilen faktöriyeller; bilimsel gösterimdeki değerler yuvarlanmıştır ⓘ

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
11	39916800
12	479001600
13	6227020800
14	87178291200
15	1307674368000
16	20922789888000
17	355687428096000
18	6402373705728000
19	121645100408832000
20	2432902008176640000
25	1.551121004×1025
50	3.041409320×1064
70	1.197857167×10100
100	9.332621544×10157
450	1.733368733×101000
1000	4.023872601×102567
3249	6.412337688×1010000
10000	2.846259681×1035659
25206	1.205703438×10100000
100000	2.824229408×10456573
205023	2.503898932×101000004
1000000	8.263931688×105565708
10100	1010101.9981097754820

Matematikte, negatif olmayan bir tamsayının faktöriyeli $n$ile gösterilir. $n!$'den küçük veya eşit tüm pozitif tamsayıların çarpımıdır. $n$. Faktöriyel $n$ 'nin çarpımına da eşittir. $n$ bir sonraki daha küçük faktöriyel ile:

$${\begin{aligned}n!&=n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1\\&=n\times (n-1)!\\\end{aligned}}$$

Örneğin,

$$5!=5\times 4\times 3\times 2\times 1=5\times 24=120.$$

Boş çarpım kuralına göre 0! değeri 1'dir. ⓘ

Faktöriyeller birçok eski kültürde, özellikle de Hint matematiğinde Jain edebiyatının kanonik eserlerinde ve Yahudi mistikler tarafından Talmud'un Sefer Yetzirah kitabında keşfedilmiştir. Faktöriyel işlemine matematiğin birçok alanında, özellikle de en temel kullanımının olası farklı dizileri - permütasyonları - saydığı kombinatorikte rastlanır. $n$ farklı nesneler vardır $n!$. Matematiksel analizde, faktöriyeller üstel fonksiyon ve diğer fonksiyonlar için güç serilerinde kullanılır ve ayrıca cebir, sayı teorisi, olasılık teorisi ve bilgisayar biliminde de uygulamaları vardır. ⓘ

Faktöriyel fonksiyonunun matematiğinin çoğu 18. yüzyılın sonları ve 19. yüzyılın başlarından itibaren geliştirilmiştir. Stirling'in yaklaşımı, büyük sayıların faktöriyeline doğru bir yaklaşım sağlar ve üstel büyümeden daha hızlı büyüdüğünü gösterir. Legendre'nin formülü, faktöriyellerin asal çarpanlarına ayrılmasında asal sayıların üslerini tanımlar ve faktöriyellerin sondaki sıfırlarını saymak için kullanılabilir. Daniel Bernoulli ve Leonhard Euler faktöriyel fonksiyonunu, negatif tamsayılar hariç, karmaşık sayıların sürekli bir fonksiyonu olan (ofset) gamma fonksiyonuna interpole etmiştir. ⓘ

Binom katsayıları, çift faktöriyeller, düşen faktöriyeller, primoriyeller ve alt faktöriyeller de dahil olmak üzere diğer birçok önemli fonksiyon ve sayı dizisi faktöriyellerle yakından ilişkilidir. Faktöriyel fonksiyonunun uygulamaları genellikle farklı bilgisayar programlama stillerinin bir örneği olarak kullanılır ve bilimsel hesap makinelerinde ve bilimsel hesaplama yazılım kütüphanelerinde yer alır. Çarpım formülü veya yineleme kullanarak büyük faktöriyelleri doğrudan hesaplamak verimli olmasa da, aynı basamak sayısına sahip sayılar için hızlı çarpma algoritmalarının süresini sabit bir faktörle eşleştiren daha hızlı algoritmalar bilinmektedir. ⓘ

Faktöriyel, matematikte, sağına ünlem işareti konulmuş sayıya verilen isim, daha genel olan Gama fonksiyonunun tam sayılarla sınırlanmış özel bir durumudur. 1'den başlayarak belirli bir sayma sayısına kadar olan sayıların çarpımına o sayının faktöriyeli denir. Basit bir şekilde faktöriyel, n tane ayrık elemanın kaç farklı şekilde sıralanabileceğidir. ⓘ

Tarihçe

Faktöriyel kavramı birçok kültürde birbirinden bağımsız olarak ortaya çıkmıştır:

• Hint matematiğinde, faktöriyellerin bilinen en eski tanımlarından biri, Jain edebiyatının kanonik eserlerinden biri olan ve MÖ 300 ile MS 400 arasında değişen tarihler verilen Anuyogadvāra-sūtra'dan gelmektedir. Bir dizi öğenin sıralanmış ve tersine çevrilmiş düzenini diğer ("karışık") düzenlerden ayırır ve faktöriyel için olağan çarpım formülünden iki çıkararak karışık düzenlerin sayısını değerlendirir. Permütasyonlar için çarpım kuralı MS 6. yüzyılda yaşamış Jain rahip Jinabhadra tarafından da tanımlanmıştır. Hindu bilginler, Bhāskara II'nin Līlāvatī adlı eserinde Vishnu'nun dört karakteristik nesnesini (deniz kabuğu, diskus, topuz ve lotus çiçeği) dört elinde kaç şekilde tutabileceğine dair bir problemle ve on elli bir tanrı için benzer bir problemle bağlantılı olarak faktöriyellerden bahsettiği en az 1150 yılından beri faktöriyel formüllerini kullanmaktadır.
• Orta Doğu matematiğinde, Talmudik döneme (MS 200 ila 500) ait İbranice mistik yaratılış kitabı Sefer Yetzirah, İbrani alfabesinden oluşturulabilecek kelime sayısına ilişkin bir araştırmanın parçası olarak 7'ye kadar faktöriyelleri listeler! Faktöriyeller 8. yüzyıl Arap gramercisi Al-Khalil ibn Ahmad al-Farahidi tarafından da benzer nedenlerle incelenmiştir. Arap matematikçi İbn el-Heysem (Alhazen olarak da bilinir, yaklaşık 965 - yaklaşık 1040) faktöriyelleri asal sayılarla ilişkilendiren Wilson teoremini formüle eden ilk kişidir.
• Avrupa'da, Yunan matematiği bazı kombinatorikleri içermesine ve Platon'un kısmen bölünebilirlik özellikleri nedeniyle ideal bir topluluğun nüfusu olarak 5040'ı (bir faktöriyel) kullanmasına rağmen, antik Yunan'da faktöriyeller üzerine çalışıldığına dair doğrudan bir kanıt yoktur. Bunun yerine, Avrupa'da faktöriyeller üzerine ilk çalışma, Sefer Yetzirah pasajını açıklayan Shabbethai Donnolo gibi Yahudi akademisyenler tarafından yapılmıştır. 1677'de İngiliz yazar Fabian Stedman, faktöriyellerin birkaç akortlu çanın çalınmasını içeren bir müzik sanatı olan değişim ziline uygulanmasını tanımlamıştır. ⓘ

15. yüzyılın sonlarından itibaren faktöriyeller batılı matematikçilerin çalışma konusu haline gelmiştir. İtalyan matematikçi Luca Pacioli, 1494 tarihli bir çalışmasında, yemek masası düzenlemeleriyle ilgili bir problemle bağlantılı olarak 11'e kadar faktöriyelleri hesaplamıştır. Christopher Clavius, Johannes de Sacrobosco'nun çalışması üzerine 1603 tarihli bir yorumda faktöriyelleri tartıştı ve 1640'larda Fransız polimat Marin Mersenne, Clavius'un çalışmasına dayanarak 64'e kadar büyük (ancak tamamen doğru olmayan) faktöriyel tabloları yayınladı! Üstel fonksiyon için güç serisi, katsayıları için faktöriyellerin karşılıkları ile birlikte, ilk olarak 1676 yılında Isaac Newton tarafından Gottfried Wilhelm Leibniz'e yazılan bir mektupta formüle edilmiştir. Erken dönem Avrupa matematiğinde faktöriyeller üzerine yapılan diğer önemli çalışmalar arasında John Wallis'in 1685 tarihli bir çalışmasında geniş yer verilen, faktöriyellerin büyük değerleri için yaklaşık değerlerinin incelendiği $n$ Abraham de Moivre tarafından 1721'de, James Stirling'in de Moivre'e Stirling'in yaklaşımı olarak bilinen şeyi belirten 1729 tarihli mektubu ve aynı zamanda Daniel Bernoulli ve Leonhard Euler'in faktöriyel fonksiyonunun gama fonksiyonuna sürekli uzantısını formüle eden çalışmaları. Adrien-Marie Legendre, 1808 yılında sayılar teorisi üzerine yazdığı bir metne, faktöriyellerin asal kuvvetlere çarpanlara ayrılmasındaki üsleri tanımlayan Legendre formülünü dahil etmiştir. ⓘ

Gösterim $n!$ faktöriyeller için 1808 yılında Fransız matematikçi Christian Kramp tarafından tanıtılmıştır. Başka birçok gösterim de kullanılmıştır. Faktöriyelin argümanının bir kutunun sol ve alt taraflarıyla yarı kapalı olduğu daha sonraki bir başka gösterim, İngiltere ve Amerika'da bir süre popüler olmuş, ancak belki de dizgisi zor olduğu için kullanımdan düşmüştür. "Faktöriyel" (orijinali Fransızca: factorielle) kelimesi ilk kez 1800 yılında Louis François Antoine Arbogast tarafından Faà di Bruno'nun formülü üzerine yapılan ilk çalışmada kullanılmış, ancak aritmetik ilerlemelerin çarpımlarına ilişkin daha genel bir kavrama atıfta bulunulmuştur. Bu ismin atıfta bulunduğu "faktörler", faktöriyel için çarpım formülünün terimleridir. ⓘ

Tanım

Pozitif bir tamsayının faktöriyel fonksiyonu $n$ çarpımı ile tanımlanır

$$n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n.$$

Bu, çarpım gösteriminde daha kısa olarak şu şekilde yazılabilir

$$n!=\prod _{i=1}^{n}i.$$

ⓘ

Bu çarpım formülü, son terim hariç tüm terimler korunacak şekilde değiştirilirse, daha küçük bir faktöriyel için aynı formda bir çarpım tanımlayacaktır. Bu, faktöriyel fonksiyonunun her değerinin bir önceki değerle çarpılarak elde edilebileceği bir yineleme ilişkisine yol açar $n$:

$$n!=n\cdot (n-1)!.$$

Örneğin, $5!=5\cdot 4!=5\cdot 24=120$. ⓘ

Sıfırın faktöriyeli

Faktöriyel $0$ o $1$veya sembollerle, $0!=1$. Bu tanım için çeşitli motivasyonlar vardır:

• Şunlar için $n=0$'nin tanımı $n!$ Bir çarpım olarak hiçbir sayının çarpımını içermez ve bu nedenle boş çarpımın, hiçbir çarpanın çarpımının çarpımsal özdeşliğe eşit olduğu şeklindeki daha geniş konvansiyonun bir örneğidir.
• Sıfır nesnenin tam olarak bir permütasyonu vardır: permütasyon için hiçbir şey olmadığında, tek yeniden düzenleme hiçbir şey yapmamaktır.
• Bu kural, kombinatorikteki birçok özdeşliği, parametrelerinin tüm geçerli seçenekleri için geçerli kılar. Örneğin, tüm parametreleri seçmenin yollarının sayısı $n$ kümesinden öğeler $n$ o ${\textstyle {\tbinom {n}{n}}={\tfrac {n!}{n!0!}}=1,}$ ile geçerli olabilecek bir binom katsayısı özdeşliği $0!=1$.
• ile $0!=1$'de faktöriyel için yineleme ilişkisi geçerli kalır. $n=1$. Bu nedenle, bu konvansiyonla, faktöriyelin özyinelemeli bir hesaplamasının temel durum olarak yalnızca sıfır değerine sahip olması gerekir, bu da hesaplamayı basitleştirir ve ek özel durumlara olan ihtiyacı ortadan kaldırır.
• Ayar $0!=1$ üstel fonksiyon gibi birçok formülün kuvvet serisi olarak kompakt bir şekilde ifade edilmesini sağlar: ${\textstyle e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.}$
• Bu seçim gama fonksiyonuyla eşleşir $0!=\Gamma (0+1)=1$ve gamma fonksiyonunun sürekli bir fonksiyon olması için bu değere sahip olması gerekir. ⓘ

Uygulamalar

Faktöriyel fonksiyonunun en eski kullanımları permütasyonların sayılmasını içerir $n!$ farklı düzenleme yolları $n$ farklı nesneleri bir dizi haline getirir. Faktöriyeller, nesnelerin farklı sıralamalarını hesaba katmak için kombinatorikteki birçok formülde daha geniş bir şekilde görünür. Örneğin binom katsayıları ${\tbinom {n}{k}}$ saymak $k$-eleman kombinasyonları (alt kümeleri $k$ elemanları) ile bir kümeden $n$ elemanlarıdır ve aşağıdaki formül kullanılarak faktöriyellerden hesaplanabilir

$${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$$

Birinci tür Stirling sayıları faktöriyellerin toplamıdır ve aşağıdaki permütasyonları sayar $n$ aynı sayıda döngüye sahip alt kümeler halinde gruplandırılır. Bir başka kombinatoryal uygulama da, hiçbir elemanı orijinal konumunda bırakmayan permütasyonların sayılmasıdır. $n$ öğelerine en yakın tamsayıdır. $n!/e$. ⓘ

Cebirde faktöriyeller, toplamların kuvvetlerini genişletmek için binom katsayılarını kullanan binom teoremi aracılığıyla ortaya çıkar. Ayrıca, simetrik polinomlar için Newton'un özdeşlikleri gibi belirli polinom ailelerini birbirleriyle ilişkilendirmek için kullanılan katsayılarda da ortaya çıkarlar. Permütasyonların sayılmasında kullanımları cebirsel olarak da yeniden ifade edilebilir: faktöriyeller sonlu simetrik grupların mertebeleridir. Kalkülüste, faktöriyeller Faà di Bruno'nun yüksek türevleri zincirleme formülünde ortaya çıkar. Matematiksel analizde, faktöriyeller sıklıkla kuvvet serilerinin paydalarında, özellikle de üstel fonksiyon serilerinde ortaya çıkar,

$$e^{x}=1+{\frac {x}{1}}+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+\cdots =\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}},$$

ve diğer Taylor serilerinin katsayılarında (özellikle trigonometrik ve hiperbolik fonksiyonların katsayılarında) $n!$ gelen $n$'nin üçüncü türevi $x^{n}$. Güç serilerinde faktöriyellerin bu kullanımı, üstel üreten fonksiyon aracılığıyla analitik kombinatoriğe geri bağlanır; bu fonksiyon, aşağıdaki özelliklere sahip bir kombinatorik sınıf için $n_{i}$ boyut elemanları $i$ kuvvet serisi olarak tanımlanır

$$\sum _{i=0}^{\infty }{\frac {x^{i}n_{i}}{i!}}.$$

ⓘ

Sayılar teorisinde, faktöriyellerin en göze çarpan özelliği, faktöriyellerin bölünebilirliğidir. $n!$ 'e kadar olan tüm pozitif tamsayılarla $n$Legendre formülü ile asal çarpanlar için daha kesin olarak tanımlanmıştır. Buradan, keyfi olarak büyük asal sayıların, sayıların asal çarpanları olarak bulunabileceği sonucu çıkar $n!\pm 1$Bu da Öklid'in asal sayıların sonsuz olduğuna dair teoreminin kanıtlanmasına yol açar. Ne zaman $n!\pm 1$ kendisi asal ise faktöriyel asal olarak adlandırılır; bununla bağlantılı olarak, yine Srinivasa Ramanujan tarafından ortaya atılan Brocard problemi, aşağıdaki formdaki kare sayıların varlığıyla ilgilidir $n!+1$. Buna karşılık, sayılar $n!+2,n!+3,\dots n!+n$ hepsi bileşik olmalıdır, bu da keyfi olarak büyük asal boşlukların varlığını kanıtlar. Bertrand'ın aşağıdaki formdaki herhangi bir aralıkta bir asalın varlığına ilişkin postülasının temel bir kanıtı $[n,2n]$Paul Erdős'ün ilk sonuçlarından biri, faktöriyellerin bölünebilirlik özelliklerine dayanıyordu. Faktöriyel sayı sistemi, her bir basamağın yer değerlerinin faktöriyel olduğu sayılar için karışık bir radiks gösterimidir. ⓘ

Faktöriyeller olasılık teorisinde, örneğin Poisson dağılımında ve rastgele permütasyonların olasılıklarında yaygın olarak kullanılır. Bilgisayar biliminde, permütasyonlar üzerinde kaba kuvvet aramalarının analizinde ortaya çıkmanın ötesinde, faktöriyeller $\log _{2}n!=n\log _{2}n-O(n)$ kümesini karşılaştırmalı olarak sıralamak için gereken karşılaştırma sayısına $n$ öğeleri ve hücre başına anahtar dağılımının Poisson dağılımı ile doğru bir şekilde yaklaştırılabildiği zincirleme karma tabloların analizinde. Dahası, faktöriyeller doğal olarak kuantum ve istatistiksel fizik formüllerinde ortaya çıkar ve burada genellikle bir dizi parçacığın tüm olası permütasyonları dikkate alınır. İstatistiksel mekanikte, Boltzmann'ın entropi formülü veya Sackur-Tetrode denklemi gibi entropi hesaplamaları, Gibbs paradoksundan kaçınmak için her bir ayırt edilemeyen parçacık türünün sayılarının faktöriyellerine bölünerek mikro durumların sayısını düzeltmelidir. Kuantum fiziği, bu düzeltmelerin neden gerekli olduğunun altında yatan nedeni sağlar. ⓘ

Özellikler

Büyüme ve yaklaşma

Faktöriyel, Stirling yaklaşımı ve daha basit yaklaşımın karşılaştırılması $(n/e)^{n}$, çift logaritmik ölçekte ⓘ

Kesilmiş bir Stirling serisinde terim sayısına karşı göreli hata ⓘ

Bir fonksiyonu olarak $n$faktöriyel, üstel büyümeden daha hızlıdır, ancak çift üstel fonksiyondan daha yavaş büyür. Büyüme oranı şuna benzer $n^{n}$ancak üstel bir faktörle daha yavaştır. Bu sonuca yaklaşmanın bir yolu, çarpım formülünü bir toplama dönüştüren faktöriyelin doğal logaritmasını almak ve ardından toplamı bir integral ile tahmin etmektir:

$$\ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.$$

Sonucun üsselleştirilmesi (ve ihmal edilebilir $+1$ terimi) yaklaşık olarak $n!$ olarak $(n/e)^{n}$. Yamuk kuralını kullanarak toplamın hem üstünü hem de altını bir integralle daha dikkatli bir şekilde sınırlandırmak, bu tahminin aşağıdakiyle orantılı bir düzeltme terimine ihtiyaç duyduğunu gösterir ${\sqrt {n}}$. Bu düzeltme için orantılılık sabiti, aşağıdakileri ifade eden Wallis çarpımından bulunabilir $\pi$ faktöriyellerin ve ikinin kuvvetlerinin sınırlayıcı bir oranı olarak. Bu düzeltmelerin sonucu Stirling'in yaklaşımıdır:

$$n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.$$

Burada $\sim$ sembolü, şu anlama gelir $n$ sonsuza gittiğinde, sol ve sağ taraflar arasındaki oran limitte bire yaklaşır. Stirling'in formülü, daha fazla sayıda terime ulaşıldığında daha da doğru hale gelen asimptotik bir serideki ilk terimi sağlar:

$$n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).$$

Alternatif bir versiyon, düzeltme terimlerinde yalnızca tek üsler kullanır:

$$n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).$$

Bu formüllerin birçok başka varyasyonu da Srinivasa Ramanujan, Bill Gosper ve diğerleri tarafından geliştirilmiştir. ⓘ

Karşılaştırma sıralamasını analiz etmek için kullanılan faktöriyelin ikili logaritması, Stirling'in yaklaşımı kullanılarak çok doğru bir şekilde tahmin edilebilir. Aşağıdaki formülde $O(1)$ terimi büyük O gösterimini çağrıştırır.

$$\log _{2}n!=n\log _{2}n-(\log _{2}e)n+{\frac {1}{2}}\log _{2}n+O(1).$$

ⓘ

Bölünebilirlik ve basamaklar

Faktöriyel için çarpım formülü şu anlama gelir $n!$ 'den büyük olan tüm asal sayılara bölünebilir. $n$ve daha büyük asal sayılarla bölünemez. Bölünebilirliği hakkında daha kesin bilgi, her asalın üssünü veren Legendre formülü ile verilir $p$ 'in asal çarpanlarına ayrılmasında $n!$ olarak

$$\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ={\frac {n-s_{p}(n)}{p-1}}.$$

İşte $s_{p}(n)$ baz toplamını ifade eder-$p$ rakamları $n$ve bu formülle verilen üs, ileri matematikte faktöriyelin p-adik değerlemesi olarak da yorumlanabilir. Legendre formülünün binom katsayıları için çarpım formülüne uygulanması, bir binom katsayısının çarpanlarına ayrılmasındaki her bir asalın üssüne ilişkin benzer bir sonuç olan Kummer teoremini üretir. ⓘ

Legendre formülünün özel durumu $p=5$ faktöriyellerin ondalık gösteriminde sondaki sıfırların sayısını verir. Bu formüle göre, sıfırların sayısı faktöriyellerin 5. taban basamaklarının çıkarılmasıyla elde edilebilir. $n$ itibaren $n$ve sonucu dörde bölmek. Legendre'nin formülü, asalın üssünün $p=2$ için üs her zaman daha büyüktür. $p=5$Bu nedenle, beşin her bir faktörü, bu sondaki sıfırlardan birini üretmek için ikinin bir faktörü ile eşleştirilebilir. Faktöriyellerin baştaki rakamları Benford yasasına göre dağıtılır. Herhangi bir tabandaki her rakam dizisi, o tabandaki bazı faktöriyel sayıların ilk rakamlarının dizisidir. ⓘ

Faktöriyellerin bölünebilirliği ile ilgili bir başka sonuç olan Wilson teoremi şunu ifade eder $(n-1)!+1$ ile bölünebilir $n$ eğer ve sadece $n$ bir asal sayıdır. Verilen herhangi bir tamsayı için $x$'nin Kempner fonksiyonu $x$ en küçük tarafından verilir $n$ bunun için $x$ böler $n!$. Neredeyse tüm sayılar için (asimptotik yoğunluğu sıfır olan istisnaların bir alt kümesi hariç hepsi), en büyük asal çarpanı ile çakışır. $x$. ⓘ

İki faktöriyelin çarpımı, $m!\cdot n!$, her zaman eşit olarak böler $(m+n)!$. Diğer faktöriyellerin çarpımına eşit olan sonsuz sayıda faktöriyel vardır: eğer $n$ kendisi faktöriyellerin herhangi bir çarpımı ise, o zaman $n!$ aynı çarpımın bir faktöriyel ile çarpımına eşittir, $(n-1)!$. Diğer faktöriyellerin çarpımı olan ancak bu "önemsiz" formda olmayan faktöriyellerin bilinen tek örnekleri şunlardır $9!=7!\cdot 3!\cdot 3!\cdot 2!$, $10!=7!\cdot 6!=7!\cdot 5!\cdot 3!$ve $16!=14!\cdot 5!\cdot 2!$. Abc varsayımından, sadece sonlu sayıda önemsiz örnek olduğu sonucu çıkar. ⓘ

Dereceden ilkel bir polinomun değerlerinin en büyük ortak böleni $d$ tam sayılar üzerinde eşit olarak böler $d!$. ⓘ

Sürekli enterpolasyon ve tamsayı olmayan genelleme

Gama fonksiyonu (faktöriyellerle eşleşmesi için bir birim sola kaydırılmıştır) faktöriyeli sürekli olarak tamsayı olmayan değerlere enterpole eder ⓘ

Pozitif olmayan tamsayılardaki kutupları gösteren karmaşık gama fonksiyonunun mutlak değerleri ⓘ

Faktöriyelleri sürekli bir fonksiyona genişletmenin sonsuz sayıda yolu vardır. Bunlardan en yaygın kullanılanı, pozitif reel sayılar için integral olarak tanımlanabilen gamma fonksiyonunu kullanır

$$\Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx.$$

Elde edilen fonksiyon negatif olmayan bir tamsayının faktöriyeliyle ilişkilidir $n$ denklemi ile

$$n!=\Gamma (n+1),$$

tamsayı olmayan argümanlar için faktöriyel tanımı olarak kullanılabilir. Tüm değerlerde $x$ her ikisi için de $\Gamma (x)$ ve $\Gamma (x-1)$ tanımlandığında, gama fonksiyonu fonksiyonel denkleme uyar

$$\Gamma (n)=(n-1)\Gamma (n-1),$$

faktöriyeller için yineleme ilişkisini genelleştirir. ⓘ

Aynı integral herhangi bir karmaşık sayı için daha genel olarak yakınsar $z$ reel kısmı pozitif olan. Euler'in yansıma formülü çözülerek karmaşık düzlemin geri kalanındaki tamsayı olmayan noktalara genişletilebilir

$$\Gamma (z)\Gamma (1-z)={\frac {\pi }{\sin \pi z}}.$$

Ancak, bu formül tam sayılarda kullanılamaz çünkü onlar için $\sin \pi z$ teriminin sıfıra bölünmesine neden olur. Bu genişletme işleminin sonucu, gama fonksiyonu için integral formülünün analitik devamı olan analitik bir fonksiyondur. Basit kutuplara sahip olduğu pozitif olmayan tam sayılar hariç, tüm karmaşık sayılarda sıfır olmayan bir değere sahiptir. Buna paralel olarak, negatif tam sayılar dışındaki tüm karmaşık sayılarda faktöriyel için bir tanım sağlar. Gama fonksiyonunu faktöriyellerin diğer sürekli interpolasyonlarından ayıran bir özellik, gama fonksiyonunun (bir ofset) pozitif reel sayılar üzerinde faktöriyelleri interpole eden ve aynı fonksiyonel denkleme uyan tek log-konveks fonksiyon olduğunu belirten Bohr-Mollerup teoremi tarafından verilir. Helmut Wielandt'ın ilgili teklik teoremi, karmaşık gama fonksiyonunun ve skaler katlarının, pozitif karmaşık yarı düzlemde fonksiyonel denkleme uyan ve gerçel kısmı 1 ile 2 arasında olan karmaşık sayılar için sınırlı kalan tek holomorfik fonksiyonlar olduğunu belirtir. ⓘ

Faktöriyel değerleri enterpole eden diğer karmaşık fonksiyonlar arasında, pozitif olmayan tam sayılar da dahil olmak üzere tüm karmaşık sayılar üzerinde tam bir fonksiyon olan Hadamard'ın gama fonksiyonu bulunur. p-adik sayılarda, faktöriyel fonksiyonunu doğrudan sürekli olarak enterpole etmek mümkün değildir, çünkü büyük tamsayıların faktöriyelleri (p-adiklerin yoğun bir alt kümesi) Legendre formülüne göre sıfıra yakınsar ve değerlerine yakın olan herhangi bir sürekli fonksiyonu her yerde sıfır olmaya zorlar. Bunun yerine, p-adik gama fonksiyonu, faktöriyeldeki p ile bölünebilen faktörleri çıkararak, faktöriyelin değiştirilmiş bir formunun sürekli bir enterpolasyonunu sağlar. ⓘ

Digamma fonksiyonu, gamma fonksiyonunun logaritmik türevidir. Tıpkı gama fonksiyonunun faktöriyellerin sürekli bir interpolasyonunu sağlayarak bir ile dengelenmesi gibi, digamma fonksiyonu da harmonik sayıların sürekli bir interpolasyonunu sağlayarak Euler-Mascheroni sabiti ile dengelenmesini sağlar. ⓘ

Hesaplama

TI SR-50A, faktöriyel tuşu olan 1975 model bir hesap makinesi (üçüncü sıra, orta sağ) ⓘ

Faktöriyel fonksiyonu bilimsel hesap makinelerinde yaygın olarak kullanılan bir özelliktir. Ayrıca Python matematiksel fonksiyonlar modülü ve Boost C++ kütüphanesi gibi bilimsel programlama kütüphanelerinde de yer almaktadır. Verimlilik bir endişe kaynağı değilse, faktöriyelleri hesaplamak önemsizdir: sadece $1$ 'e kadar olan tamsayılar tarafından $n$. Bu hesaplamanın basitliği, onu farklı bilgisayar programlama stilleri ve yöntemlerinin kullanımında yaygın bir örnek haline getirmektedir. ⓘ

Hesaplama $n!$ yineleme kullanılarak sözde kodda şu şekilde ifade edilebilir

faktöriyel(n) tanımlar:
  f := 1
  i := 1, 2, 3, ..., n için:
    f := f × i
  dönüş f

veya yineleme ilişkisine dayalı olarak özyineleme kullanarak

faktöriyel(n) tanımlar:
  if n = 0 return 1
  n × faktöriyel(n - 1) döndürür

Hesaplanması için uygun olan diğer yöntemler arasında memoizasyon, dinamik programlama ve fonksiyonel programlama yer almaktadır. Bu algoritmaların hesaplama karmaşıklığı, her aritmetik işlemin sabit zaman aldığı ve her sayının sabit miktarda depolama alanı kullandığı birim maliyetli rastgele erişimli hesaplama makinesi modeli kullanılarak analiz edilebilir. Bu modelde, bu yöntemler şunları hesaplayabilir $n!$ zaman içinde $O(n)$ve yinelemeli sürüm uzay kullanır $O(1)$. Kuyruk özyinelemesi için optimize edilmediği sürece, özyinelemeli sürüm çağrı yığınını depolamak için doğrusal alan kullanır. Ancak, bu hesaplama modeli yalnızca şu durumlarda uygundur $n$ izin verecek kadar küçüktür $n!$ bir makine sözcüğüne sığdırmak için. 12! ve 20! değerleri, sırasıyla 32 bit ve 64 bit tamsayılarda saklanabilen en büyük faktöriyellerdir. Kayan nokta daha büyük faktöriyelleri temsil edebilir, ancak tam olarak değil yaklaşık olarak temsil edebilir ve aşağıdakilerden daha büyük faktöriyeller için taşmaya devam edecektir $170!$. ⓘ

Daha büyük faktöriyellerin tam olarak hesaplanması keyfi hassasiyetli aritmetik içerir ve süresi sonuçtaki basamak veya bit sayısının bir fonksiyonu olarak analiz edilebilir. Stirling'in formülüne göre, $n!$ var $b=O(n\log n)$ bit. Schönhage-Strassen algoritması bir $b$-zaman içinde bit ürün $O(b\log b\log \log b)$ve zaman alan daha hızlı çarpma algoritmaları $O(b\log b)$ bilinmektedir. Ancak faktöriyelin hesaplanması tek bir çarpım yerine tekrarlanan çarpımları içerir, bu nedenle bu zaman sınırları doğrudan geçerli değildir. Bu ortamda, hesaplama $n!$ 1'den 1'e kadar olan sayıları çarparak $n$ sırayla verimsizdir, çünkü $n$ çarpmalar, bunların sabit bir kısmı zaman alır $O(n\log ^{2}n)$ her biri, toplam süreyi verir $O(n^{2}\log ^{2}n)$. Daha iyi bir yaklaşım, çarpma işlemlerini, bir dizi çarpma işlemini gerçekleştiren bir böl ve fethet algoritması olarak gerçekleştirmektir. $i$ sayılarını iki alt diziye bölerek $i/2$ sayılarını hesaplar, her bir alt diziyi çarpar ve sonuçları son bir çarpma işlemiyle birleştirir. Faktöriyel için bu yaklaşım toplam zaman alır $O(n\log ^{3}n)$Bir logaritma faktöriyeldeki bit sayısından, ikincisi çarpma algoritmasından ve üçüncüsü böl ve fethet işleminden gelir. ⓘ

Daha da iyi bir verimlilik, kare alma yoluyla üs alma işleminin bir üssü bir çarpıma genişletmekten daha hızlı olduğu ilkesine dayanarak, asal çarpanlara ayırma işleminden n! hesaplanarak elde edilir. Bunun için Arnold Schönhage tarafından geliştirilen bir algoritma, aşağıdakilere kadar olan asal sayıların listesini bulmakla başlar $n$Örneğin Eratosthenes'in eleğini kullanarak ve her asalın üssünü hesaplamak için Legendre formülünü kullanır. Ardından, aşağıdaki gibi özyinelemeli bir algoritma kullanarak bu üslerle asal güçlerin çarpımını hesaplar:

• Üsleri tek olan asalların çarpımını hesaplamak için böl ve yönet yöntemini kullanın
• Tüm üsleri ikiye bölün (bir tam sayıya yuvarlayın), asal kuvvetlerin çarpımını bu küçük üslerle özyinelemeli olarak hesaplayın ve sonucun karesini alın
• Önceki iki adımın sonuçlarını birbiriyle çarpın

'ye kadar olan tüm asal sayıların çarpımıdır. $n$ bir $O(n)$-bit sayı, asal sayı teoremine göre, bu nedenle ilk adım için zaman $O(n\log ^{2}n)$Bir logaritma böl ve yönetten, diğeri ise çarpma algoritmasından gelmektedir. Algoritmanın özyinelemeli çağrılarında, karşılık gelen çarpımlardaki bit sayılarının her özyineleme seviyesinde sabit bir faktörle azaldığını kanıtlamak için asal sayı teoremine tekrar başvurulabilir, böylece tüm özyineleme seviyelerinde bu adımlar için toplam süre geometrik bir seride $O(n\log ^{2}n)$. İkinci adımdaki kare alma ve üçüncü adımdaki çarpma işlemlerinin süreleri yine $O(n\log ^{2}n)$çünkü her biri bir sayının bir sayı ile tek bir çarpımıdır. $O(n\log n)$ bit. Yine, özyinelemenin her seviyesinde, ilgili sayıların bit sayısı kadar sabit bir kesri vardır (çünkü aksi takdirde tekrar tekrar karelerini almak çok büyük bir nihai sonuç üretecektir), bu nedenle özyinelemeli çağrılardaki bu adımlar için zaman miktarları geometrik bir seride $O(n\log ^{2}n)$. Sonuç olarak, tüm algoritma zaman alır $O(n\log ^{2}n)$sonucundaki aynı bit sayısına sahip tek bir çarpma işlemiyle orantılıdır. ⓘ

İlgili diziler ve fonksiyonlar

Diğer birkaç tamsayı dizisi faktöriyellere benzer veya onlarla ilişkilidir:

Alternatif faktöriyel

Değişen faktöriyel, ilk faktöriyelin değişen toplamının mutlak değeridir. $n$ faktöriyeller, ${\textstyle \sum _{i=1}^{n}(-1)^{n-i}i!}$. Bunlar esas olarak asallıklarıyla bağlantılı olarak incelenmiştir; sadece sonlu sayıda asal olabilir, ancak bu formdaki asalların tam bir listesi bilinmemektedir.

Bhargava faktöriyel

Bhargava faktöriyelleri, Manjul Bhargava tarafından tanımlanan ve faktöriyellere benzer sayı teorisi özelliklerine sahip bir tamsayı dizileri ailesidir ve faktöriyellerin kendileri de özel bir durumdur.

Çift faktöriyel

Bazı tek pozitif tamsayılara kadar olan tüm tek tamsayıların çarpımı $n$ 'nin çift faktöriyeli olarak adlandırılır. $n$ile gösterilir ve $n!!$. İşte bu,

$$(2k-1)!!=\prod _{i=1}^{k}(2i-1)={\frac {(2k)!}{2^{k}k!}}.$$

Örneğin, 9!!! = 1 × 3 × 5 × 7 × 9 = 945. Çift faktöriyeller trigonometrik integrallerde, yarım tamsayılarda gamma fonksiyonu ve hiper kürelerin hacimleri için ifadelerde ve ikili ağaçların ve mükemmel eşleşmelerin sayılmasında kullanılır.

Üstel faktöriyel

Tıpkı üçgen sayıların aşağıdaki sayıları toplaması gibi $1$ için $n$ve faktöriyeller çarpımlarını alır, üstel faktöriyel üstelleşir. 'nin üstel faktöriyeli $n$olarak gösterilir. $n\$$, özyinelemeli olarak şu şekilde tanımlanır $n^{(n-1)\$}$temel durum ile $0\$=1$. Örneğin,

$$4\$=4^{3^{2^{1}}}=262144.$$

Bu sayılar normal faktöriyellerden çok daha hızlı büyür.

Düşen faktöriyel

Notasyonlar $(x)_{n}$ veya $x^{\underline {n}}$ çarpımını temsil etmek için bazen kullanılır. $n$ 'ye kadar ve dahil olmak üzere tam sayılar $x$, eşittir $x!/(x-n)!$. Bu aynı zamanda düşen faktöriyel veya geriye doğru faktöriyel olarak da bilinir ve $(x)_{n}$ gösterimi bir Pochhammer sembolüdür. Düşen faktöriyeller, farklı dizilerin sayısını sayar $n$ bir evrenden çekilebilecek farklı öğeler $x$ öğeler. Polinomların yüksek türevlerinde ve rastgele değişkenlerin faktöriyel momentlerinde katsayı olarak ortaya çıkarlar.

Hiperfaktöriyeller

'nin hiperfaktöriyel $n$ üründür $1^{1}\cdot 2^{2}\cdots n^{n}$. Bu sayılar Hermite polinomlarının diskriminantlarını oluşturur. K-fonksiyonu tarafından sürekli olarak interpole edilebilirler ve Stirling formülü ve Wilson teoreminin benzerlerine uyarlar.

Jordan-Pólya sayıları

Jordan-Pólya sayıları faktöriyellerin çarpımıdır ve tekrarlara izin verir. Her ağacın simetri sayısı bir Jordan-Pólya sayısı olan bir simetri grubu vardır ve her Jordan-Pólya sayısı bazı ağaçların simetrilerini sayar.

Primorial

Primorial $n\#$ 'den küçük veya eşit asal sayıların çarpımıdır. $n$Bu yapı onlara faktöriyellere benzer bazı bölünebilirlik özellikleri verir, ancak faktöriyellerin aksine karesizdirler. Faktöriyel asallarda olduğu gibi $n!\pm 1$araştırmacılar primorial primes üzerinde çalışmışlardır $n\#\pm 1$.

Alt Faktöriyel

Alt faktör, bir kümenin sapma sayısını verir. $n$ nesneler. Bazen şu şekilde gösterilir $!n$'ye en yakın tamsayıya eşittir. $n!/e$.

Süperfaktöriyel

Süper faktörü $n$ ilkinin çarpımıdır $n$ faktöriyeller. Süper faktöriyeller Barnes G-fonksiyonu tarafından sürekli olarak enterpole edilir. ⓘ

Fonksiyon

Problem çözümünde kullanımı

Örnekler

Sual: Ali'nin üç çeşit gömleği, dört çeşit pantolonu, iki çeşit ayakkabısı vardır. Bir gömlek, bir pantolon ve bir ayakkabıyı kaç farklı şekilde giyer? ⓘ

Cevap: $4!=4\cdot 3\cdot 2=24$ farklı şekilde giyer. ⓘ

Kodla çözümü

Programlama dillerinde de sıklıkla karşılaşılan bir kavram olan faktöriyel, özyineli (kendi kendini çağıran) ya da tekrarlamalı (iteratif) fonksiyonlarla hesaplanabilir. ⓘ

Java programlama dilinde yazılmış özyineli ve tekrarlamalı fonksiyonlara birer örnek verecek olursak: ⓘ

// n! hesabi - Ozyineli

Public Function Faktoriyel_Oz(n) {

       IF n <= 1 Then
           Faktoriyel_Oz = 1
       Else
           Faktoriyel_Oz = n*Faktoriyel_Oz(n - 1)
       End IF
   End Function ⓘ

// n! hesabi - tekrarlamali

static double faktoriyelIt(double n) {

       double f = 1;
       for (double i = n; i >= 1; --i) {
           f *= i; 
       }
       return f;
   } ⓘ