Olası kombinasyonlar. Kombinatorik elemanları
Kombinasyon, sonlu bir kümenin elemanlarının, sabit sayıda ve tekrar edilmeden sırasız olarak seçilmesidir. Farklı kombinasyonlar en az bir öğede farklılık göstermelidir ve öğelerin sırası önemli değildir. Örneğin, Latin harflerinin tüm sesli harfleri (AEIOU) kümesinden, aşağıdaki sırasız üçlüleri oluşturan 3 harften oluşan 10 farklı kombinasyon oluşturabilirsiniz:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Aynı beş harften, aynı anda 2 harfi birleştirerek aşağıdaki sırasız çiftleri oluşturduğunuzda 10 farklı kombinasyon elde edebileceğinizi belirtmek ilginçtir:
AE, AI, AO, AU, EI, EO, AB, IO, IU, OU.
Ancak aynı sesli Latin harflerini 4'er kat birleştirirseniz yalnızca aşağıdaki 5 farklı kombinasyonu elde edersiniz:
AEIO, AEIU, AIOU, EIOU, AEOU.
Genel olarak, m elemanın n farklı elemanının kombinasyon sayısını belirtmek için aşağıdaki fonksiyonel, indeks veya vektör (Appel) sembolizmi kullanılır:
Gösterimin biçimi ne olursa olsun, n elemanın m elemana göre kombinasyonlarının sayısı aşağıdaki çarpımsal ve faktöriyel formüller kullanılarak belirlenebilir:
Bu formülleri kullanan hesaplamaların sonucunun, yukarıda Latin harfleriyle sesli harf kombinasyonlarıyla tartışılan örneğin sonuçlarıyla örtüştüğünü kontrol etmek kolaydır. Özellikle n=5 ve m=3 durumunda bu formüller kullanılarak yapılan hesaplamalar aşağıdaki sonucu verecektir:
Genel durumda, kombinasyon sayısına ilişkin formüllerin kombinatoryal bir anlamı vardır ve n > m > 0 olacak şekilde n ve m'nin tüm tamsayı değerleri için geçerlidir. Eğer m > n ve m ise< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Ek olarak, çarpımsal ve faktöriyel formüllere doğrudan ikame edilerek kolayca kontrol edilebilecek aşağıdaki sınırlayıcı kombinasyon sayılarını hatırlamakta fayda vardır:
Ayrıca, m hala bir tamsayı değeri olduğu sürece, n bir gerçel sayı olduğunda bile çarpımsal formülün geçerli kalacağına dikkat edilmelidir. Ancak daha sonra onu kullanan hesaplamanın sonucu, biçimsel geçerliliği korurken kombinatoryal anlamını kaybeder.
KOMBİNASYONLARIN KİMLİKLERİ
N ve m'nin keyfi değerleri için kombinasyon sayısını belirlemek için çarpımsal ve faktöriyel formüllerin pratik kullanımı, pay ve paydalarının faktöriyel ürünlerinin üstel büyümesi nedeniyle çok az üretkenliğe sahiptir. Nispeten küçük n ve m değerleri için bile, bu ürünler çoğu zaman modern bilgi işlem ve yazılım sistemlerinde tam sayıları temsil etme yeteneklerini aşar. Üstelik değerleri, nispeten küçük olabilen kombinasyon sayısının sonuçtaki değerinden önemli ölçüde daha büyük çıkıyor. Örneğin n=10 ile m=8 elemanlarının kombinasyon sayısı sadece 45'tir. Ancak bu değeri faktöriyel formülü kullanarak bulmak için öncelikle 10'dan çok daha büyük değerleri hesaplamanız gerekir! payda ve 8! paydada:
Büyük miktarların işlenmesi için zaman alan işlemleri ortadan kaldırmak, kombinasyon sayısını belirlemek için, doğrudan çarpımsal ve faktöriyel formüllerden çıkan çeşitli yineleme ilişkilerini kullanabilirsiniz. Özellikle, çarpımsal formülden aşağıdaki yineleme ilişkisi çıkar; bu, endekslerinin oranını kombinasyon sayısının işaretinin ötesine almamıza olanak tanır:
Son olarak, alt simgeyi sabit tutmak, kombinasyon sayısı için faktöriyel formülden kolayca elde edilebilecek aşağıdaki yineleme ilişkisini sağlar:
Temel dönüşümlerden sonra ortaya çıkan üç yineleme ilişkisi aşağıdaki formlarda temsil edilebilir:
Şimdi ilk 2 formülün sol ve sağ taraflarını toplarsak ve sonucu n kadar azaltırsak, kombinasyon sayılarının toplamının özdeşliği adı verilen önemli bir yineleme ilişkisi elde ederiz:
Toplama kimliği, n ve m'nin büyük değerleri için kombinasyon sayısını verimli bir şekilde belirlemek için temel bir yineleme kuralı sağlar, çünkü faktöriyel ürünlerdeki çarpma işlemlerinin daha basit toplama işlemleriyle ve daha küçük sayıda kombinasyonlarla değiştirilmesine olanak tanır. Özellikle, toplama kimliğini kullanarak, yukarıda tartışılan n=10'a m=8 elemanlarının kombinasyon sayısını, aşağıdaki yinelenen dönüşüm dizisini gerçekleştirerek belirlemek artık kolaydır:
Ek olarak, sonlu toplamların hesaplanmasına yönelik çeşitli yararlı ilişkiler, toplama özdeşliğinden, özellikle de aşağıdaki forma sahip olan alt simgeye göre toplama formülünden türetilebilir:
Bu ilişki, toplama özdeşliğinde yinelemeyi, alt simgesi 0'dan büyük olan en büyük üst simgeye sahip terim boyunca genişletirsek elde edilir. Aşağıdaki sayısal örnek, bu yinelenen dönüşüm sürecini göstermektedir:
Alt simge toplama formülü genellikle doğal sayıların kuvvetlerinin toplamını hesaplamak için kullanılır. Özellikle, m=1 varsayıldığında, bu formülü kullanarak doğal serinin ilk n sayısının toplamını bulmak kolaydır:
Toplama formülünün başka bir kullanışlı versiyonu, en küçük üst simgeye sahip terim boyunca toplama kimliğinin tekrarını genişleterek elde edilebilir. Aşağıdaki sayısal örnek yinelenen dönüşümlerin bu versiyonunu göstermektedir:
Genel durumda, bu tür dönüşümlerin bir sonucu olarak, her iki endeksi komşu terimlerden birer farklı olan kombinasyon sayılarının toplamı elde edilir ve endekslerdeki fark sabit kalır (göz önünde bulundurulan örnekte, aynı zamanda bire eşittir). Böylece her iki kombinasyon numarası endeksi için aşağıdaki toplama formülünü elde ederiz:
Yukarıda tartışılan yineleme ilişkilerine ve toplama formüllerine ek olarak, kombinatoryal analizde kombinasyon sayıları için birçok başka yararlı özdeşlik elde edilmiştir. Bunların arasında en önemlisi simetri kimliği, şuna benziyor:
Simetri kimliğinin geçerliliği aşağıdaki örnekte 5 elemanın kombinasyonlarının sayısı 2 ve (5 2) = 3 ile karşılaştırılarak doğrulanabilir:
Simetri özdeşliği açık bir kombinatoryal anlama sahiptir, çünkü n öğeden m öğenin seçilmesine yönelik seçeneklerin sayısını belirleyerek, aynı anda kalan seçilmemiş öğelerden elde edilen kombinasyonların sayısını da belirler. Belirtilen simetri, kombinasyon sayısı faktöriyel formülünde m'nin (nm) ile değiştirilmesiyle hemen elde edilir:
Sayılar ve kombinasyon kimlikleri, modern hesaplamalı matematiğin çeşitli alanlarında yaygın olarak kullanılmaktadır. Ancak bunların en popüler uygulamaları Newton binom ve Pascal üçgeni ile ilgilidir.
BİNOM TEOREMİ
Çeşitli matematiksel dönüşümleri ve hesaplamaları gerçekleştirmek için, cebirsel bir binomun (binomun) herhangi bir doğal kuvvetini polinom biçiminde temsil edebilmek önemlidir. Küçük kuvvetler için istenen polinom, binomların doğrudan çarpılmasıyla kolaylıkla elde edilebilir. Özellikle, iki terimin toplamının karesi ve küpü için aşağıdaki formüller, ilköğretim matematik dersinden iyi bilinmektedir:
Genel durumda, bir binomun keyfi bir n derecesi için, polinom biçiminde gerekli temsil, aşağıdaki eşitliğin doğru olduğunu bildiren Newton'un binom teoremi tarafından sağlanır:
Bu eşitliğe genellikle Newton binom adı verilir. Sağ tarafındaki polinom, sol taraftaki binomun n X ve Y terimlerinin çarpımlarının toplamından oluşur ve önlerindeki katsayılara binom denir ve endeksli kombinasyon sayısına eşittir. güçlerinden elde edilir. Newton'un binom formülünün kombinatoryal analizdeki özel popülaritesi göz önüne alındığında, binom katsayısı ve kombinasyon sayısı terimleri genellikle eşanlamlı olarak kabul edilir.
Açıkçası, kare ve küp toplam formülleri sırasıyla n=2 ve n=3 için binom teoreminin özel durumlarıdır. Daha yüksek dereceleri (n>3) ele almak için Newton'un binom formülü kullanılmalıdır. Dördüncü derece binom (n=4) için uygulaması aşağıdaki örnekle gösterilmektedir:
İki terimli formülün Newton'dan önce bile Arap Doğu ve Batı Avrupa'daki ortaçağ matematikçileri tarafından bilindiğini belirtmek gerekir. Bu nedenle genel kabul gören adı tarihsel olarak doğru değildir. Newton'un değeri, bu formülü herhangi bir pozitif veya negatif rasyonel ve irrasyonel değeri alabilen keyfi bir gerçek üstel r durumuna genelleştirmesidir. Genel durumda böyle bir Newton binom formülünün sağ tarafında sonsuz bir toplam bulunur ve genellikle şu şekilde yazılır:
Örneğin, r=1/2 üssünün pozitif kesirli değeri ile, binom katsayılarının değerleri dikkate alınarak aşağıdaki genişleme elde edilir:
Genel durumda, herhangi bir üs için Newton'un binom formülü, Maclaurin formülünün özel bir versiyonudur; bu, keyfi bir fonksiyonun bir kuvvet serisine genişlemesini sağlar. Newton bunu |z| için gösterdi.< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Şimdi Z=X/Y'yi ayarlarsak ve sol ve sağ tarafları Yn ile çarparsak, yukarıda tartışılan Newton binom formülünün bir versiyonunu elde ederiz.
Evrenselliğine rağmen, binom teoremi kombinatoryal anlamını yalnızca binomun negatif olmayan tamsayı kuvvetleri için korur. Bu durumda, binom katsayıları için çeşitli yararlı özdeşlikleri kanıtlamak için kullanılabilir. Özellikle kombinasyon sayılarının alt simgeye ve her iki endekse göre toplanmasına yönelik formüller yukarıda tartışılmıştır. Eksik üst simge toplama kimliği, Newton'un binom formülünden X = Y = 1 veya Z = 1 koyarak kolayca elde edilebilir:
Bir başka yararlı kimlik, binom katsayılarının toplamlarının çift ve tek sayılarla eşitliğini sağlar. X = 1 ve Y = 1 veya Z = 1 ise Newton'un binom formülünden hemen elde edilir:
Son olarak, ele alınan her iki kimlikten, yalnızca çift veya yalnızca tek sayılarla binom katsayılarının toplamının özdeşliğini elde ederiz:
Dikkate alınan kimliklere ve endekslerin kombinasyon sayısı işaretinin altından çıkarılmasına ilişkin yinelenen kurala dayanarak, bir dizi ilginç ilişki elde edilebilir. Örneğin, üst simge toplama formülünde n'yi her yerde (n1) ile değiştirirsek ve her terimdeki indisleri çıkarırsak aşağıdaki ilişkiyi elde ederiz:
Çift ve tek sayılarla binom katsayılarının toplamına yönelik formülde benzer bir teknik kullanılarak, örneğin aşağıdaki ilişkinin geçerliliği kanıtlanabilir:
Başka bir kullanışlı kimlik, aşağıdaki Cauchy formülünü kullanarak, keyfi derece n ve k olan iki binomun simetrik olarak yerleştirilmiş binom katsayılarının çarpımlarının toplamını kolayca hesaplamanıza olanak tanır:
Bu formülün geçerliliği, aşağıdaki özdeş ilişkinin sol ve sağ taraflarında Z değişkeninin herhangi bir m derecesi için katsayıların gerekli eşitliğinden kaynaklanır:
n=k=m olduğu özel durumda, simetri özdeşliği dikkate alınarak, binom katsayılarının karelerinin toplamı için daha popüler bir formül elde edilir:
Binom katsayıları için diğer pek çok yararlı özdeşlik, kombinatoryal analizle ilgili kapsamlı literatürde bulunabilir. Ancak bunların en ünlü pratik uygulaması Pascal üçgeniyle ilgilidir.
PASCAL ÜÇGENİ
Pascal'ın aritmetik üçgeni, binom katsayılarından oluşan sonsuz bir sayısal tablo oluşturur. Çizgileri, binomların kuvvetlerine göre yukarıdan aşağıya doğru sıralanmıştır. Her satırda, binom katsayıları, karşılık gelen kombinasyon numaralarının üst simgelerinin soldan sağa doğru artan sırasına göre düzenlenir. Pascal üçgeni genellikle ikizkenar veya dikdörtgen biçimde yazılır.
Daha görsel ve yaygın olanı, binom katsayılarının kademeli olarak sonsuz bir ikizkenar üçgen oluşturduğu ikizkenar formattır. 4. dereceye kadar (n=4) binomlar için başlangıç parçası aşağıdaki forma sahiptir:
Genel olarak Pascal'ın ikizkenar üçgeni, toplama özdeşliklerine ve sayı kombinasyonlarının simetrisine dayanan binom katsayılarını belirlemek için uygun bir geometrik kural sağlar. Özellikle toplama özdeşliğine göre herhangi bir binom katsayısı, bir önceki satırın kendisine en yakın iki katsayısının toplamıdır. Simetri özdeşliğine göre Pascal'ın ikizkenar üçgeni ortaortaya göre simetriktir. Dolayısıyla, çizgilerinin her biri binom katsayılarının sayısal bir palindromudur. Belirtilen cebirsel ve geometrik özellikler, Pascal'ın ikizkenar üçgenini kolayca genişletmeyi ve keyfi güçlerin binom katsayılarının değerlerini tutarlı bir şekilde bulmayı mümkün kılar.
Ancak Pascal üçgeninin çeşitli özelliklerini incelemek için biçimsel olarak daha katı olan dikdörtgen formatı kullanmak daha uygundur. Bu formatta, sonsuz bir dik üçgen oluşturdukları binom katsayılarının daha düşük bir üçgen matrisi ile belirtilir. 9. dereceye kadar (n=9) binomlar için Pascal dik üçgeninin ilk parçası aşağıdaki forma sahiptir:
Geometrik olarak böyle bir dikdörtgen tablo, Pascal'ın ikizkenar üçgeninin yatay olarak deforme edilmesiyle elde edilir. Sonuç olarak Pascal ikizkenar üçgeninin yan kenarlarına paralel olan sayı serileri Pascal dik üçgeninin düşey ve köşegenlerine dönüşür ve her iki üçgenin yatay çizgileri çakışır. Aynı zamanda, Pascal'ın sağ üçgeni ikizkenar karşılığının görsel simetri özelliğini kaybetmesine rağmen, binom katsayılarının toplama ve simetri kuralları geçerliliğini koruyor. Bunu telafi etmek için Pascal dik üçgeninin yatay, dikey ve köşegenlerine ait binom katsayılarının çeşitli sayısal özelliklerini resmi olarak analiz etmek daha uygun hale gelir.
Pascal dik üçgeninin yataylarını analiz etmeye başladığımızda, binomları üst simge ile toplama formülüne göre n numaralı herhangi bir satırın elemanlarının toplamının 2n'ye eşit olduğunu fark etmek kolaydır. Bundan, n numaralı yatay çizgilerin herhangi birinin üzerindeki elemanların toplamının (2 n 1)'e eşit olduğu sonucu çıkar. Her yatayın elemanlarının toplamının değeri ikili sayı sisteminde yazılırsa bu sonuç oldukça açık hale gelir. Örneğin n=4 için bu toplama şu şekilde yazılabilir:
Burada yatayların ikinin kuvvetleriyle de ilgili birkaç ilginç özelliği daha var. Yatay sayının ikinin katı olması durumunda (n=2 k), o zaman tüm iç elemanlarının (dıştakiler hariç) çift sayı olduğu ortaya çıktı. Aksine, eğer yatay bir doğrunun numarası ikinin üssünden bir eksikse (n=2 k 1) tüm sayılar tek olacaktır. Bu özelliklerin geçerliliği, örneğin yataylarda n=4 ve n=3 veya n=8 ve n=7 gibi dahili binom katsayılarının paritesi kontrol edilerek doğrulanabilir.
Şimdi Pascal dik üçgeninin satır numarası bir asal sayı p olsun. O zaman tüm iç binom katsayıları p'ye bölünebilir. Bu özelliğin asal kontur sayılarının küçük değerlerini kontrol etmesi kolaydır. Örneğin, beşinci yatayın (5, 10 ve 5) tüm iç binom katsayıları açıkça 5'e bölünebilir. Herhangi bir asal yatay sayı p için bu sonucu kanıtlamak için, binom katsayılarının çarpımsal formülünü aşağıdaki gibi yazmanız gerekir:
p bir asal sayı olduğundan ve dolayısıyla m!'ye bölünemediğinden, binom katsayısının tam sayı değerini garanti etmek için bu formülün payının geri kalan faktörlerinin çarpımı m!'ye bölünebilir olmalıdır. Buradan köşeli parantez içindeki oranın bir doğal sayı N olduğu ve istenen sonucun açıkça ortaya çıktığı anlaşılmaktadır:
Bu sonucu kullanarak, iç elemanları belirli bir p asal numarasına bölünebilen Pascal üçgeninin tüm yatay çizgilerinin sayılarının p'nin kuvvetleri olduğunu, yani n=pk biçiminde olduklarını tespit edebiliriz. Özellikle, eğer p=3 ise, p asal sayısı yukarıda belirtildiği gibi sadece 3. satırın tüm iç elemanlarını değil aynı zamanda örneğin 9. yatayı da (9, 36, 84 ve 126) böler. Öte yandan Pascal üçgeninde iç elemanlarının tamamı bileşik bir sayıya bölünebilen yatay bir çizgi bulmak imkansızdır. Aksi takdirde, böyle bir yatay çizginin sayısı aynı anda tüm iç elemanlarının bölündüğü bileşik sayının asal bölenlerinin kuvveti olmalıdır, ancak bu açık nedenlerden dolayı imkansızdır.
Dikkate alınan hususlar, Pascal üçgeninin yatay elemanlarının bölünebilirliği için aşağıdaki genel kriteri formüle etmemize izin verir. Pascal üçgeninin n numaralı herhangi bir yatay çizgisinin tüm iç elemanlarının en büyük ortak böleni (OBB), n=pk ise asal sayı p'ye veya diğer tüm durumlarda 1'e eşittir:
Herhangi bir 0 için OBEB(Cmn) = ( )< m < n .
Yatayların analizinin sonucunda, onları oluşturan binom katsayıları serisinin sahip olduğu ilginç bir özelliği daha dikkate almakta fayda var. N numaralı herhangi bir yatay doğrunun binom katsayıları 10 sayısının ardışık kuvvetleriyle çarpılır ve ardından tüm bu çarpımlar toplanırsa sonuç 11 n olur. Bu sonucun resmi gerekçesi, X=10 ve Y=1 (veya Z=1) değerlerinin Newton binom formülünde ikame edilmesidir. Aşağıdaki sayısal örnek, bu özelliğin n=5 için karşılanmasını göstermektedir:
Pascal'ın dik üçgeninin dikey özelliklerinin analizi, onları oluşturan unsurların bireysel özelliklerinin incelenmesiyle başlayabilir. Resmi olarak, her dikey m, sabit bir üst simge (m) ve alt simgenin bir artışı ile aşağıdaki sonsuz binom katsayıları dizisinden oluşur:
Açıkçası, m=0 olduğunda birler dizisi elde edilir ve m=1 olduğunda bir doğal sayılar dizisi oluşturulur. m=2 olduğunda dikey üçgen sayılardan oluşur. Her üçgen sayı, dama tahtası deseninde düzenlenmiş rastgele nesnelerle (çekirdekler) doldurulmuş eşkenar üçgen biçiminde bir düzlem üzerinde gösterilebilir. Bu durumda, her bir T k üçgen sayısının değeri, temsil eden çekirdeklerin sayısını belirler ve indeks, onu temsil etmek için kaç tane çekirdek satırının gerekli olduğunu gösterir. Örneğin, başlangıçtaki 4 üçgen sayı, karşılık gelen nükleer "@" simgelerinin aşağıdaki konfigürasyonlarını temsil eder:
Benzer şekilde, doğal sayıların karesi alınarak elde edilen kare sayıların (Sk) ve genel olarak düzenli çokgenlerin düzenli olarak doldurulmasıyla oluşturulan çokgen figürlü sayıların dikkate alınabileceği belirtilmelidir. Özellikle, başlangıçtaki 4 kare sayı şu şekilde temsil edilebilir:
Pascal üçgeninin düşeylerinin analizine dönersek, m=3'teki bir sonraki düşeyin tetrahedral (piramidal) sayılarla dolu olduğunu görebiliriz. Bu tür her bir Pk sayısı, bir tetrahedron şeklinde düzenlenebilecek çekirdek sayısını belirtir ve indeks, onu üç boyutlu uzayda tasvir etmek için kaç tane yatay üçgen çekirdek sırası katmanının gerekli olduğunu belirler. Bu durumda tüm yatay katmanların ardışık üçgen sayılar olarak temsil edilmesi gerekir. m>3 için Pascal üçgeninin aşağıdaki dikeylerinin elemanları, düzlemde veya üç boyutlu uzayda görsel bir geometrik yorumu olmayan, ancak resmi olarak üçgen ve dört yüzlü sayıların çok boyutlu analoglarına karşılık gelen hipertetraedal sayılar serisini oluşturur.
Her ne kadar Pascal üçgeninin dikey sayı serileri dikkate alınan bireysel şekilli özelliklere sahip olsa da, onlar için, kombinasyon sayılarını alt simgeye göre toplamak için kullanılan formülü kullanarak, ilk elemanların değerlerinin kısmi toplamlarını aynı şekilde hesaplamak mümkündür. . Pascal üçgeninde bu formül aşağıdaki geometrik yoruma sahiptir. Herhangi bir düşeyin n üst binom katsayısının değerlerinin toplamı, bir satır aşağıda bulunan bir sonraki düşeyin elemanının değerine eşittir. Bu sonuç aynı zamanda üçgen, tetrahedral ve hipertetrahedal sayıların geometrik yapısıyla da tutarlıdır, çünkü bu sayıların her birinin temsili daha düşük dereceli sayıları temsil eden çekirdek katmanlardan oluşur. Özellikle, n'inci üçgen sayısı Tn, doğrusal katmanlarını temsil eden tüm doğal sayıların toplanmasıyla elde edilebilir:
Benzer şekilde, yatay çekirdek katmanlarını oluşturan ilk n üçgensel sayıların aşağıdaki toplamını hesaplayarak dört yüzlü Pn sayısını bulmak zor değildir:
Pascal'ın dik üçgenindeki yatay ve dikeylere ek olarak, özelliklerinin incelenmesi de ilgi çekici olan çapraz eleman sıraları izlenebilir. Bu durumda genellikle alçalan ve yükselen köşegenler arasında bir ayrım yapılır. Aşağıya doğru köşegenler Pascal dik üçgeninin hipotenüsüne paraleldir. Her iki endeksin de artmasıyla bir dizi binom katsayılarından oluşurlar. Simetrinin özdeşliği nedeniyle, azalan köşegenler, elemanlarının değerlerinde Pascal üçgeninin karşılık gelen dikey sıralarıyla çakışır ve bu nedenle yukarıda tartışılan tüm özelliklerini tekrarlar. Belirtilen yazışma, dikey sıfırlar dikkate alınmazsa, azalan köşegen ve dikey öğelerin değerlerinin herhangi bir n sayısıyla çakışması ile izlenebilir:
Artan köşegenler, Pascal dik üçgeninin hipotenüsüne geometrik olarak dik sayı serileri oluşturur. Alttakinin azalması ve üst simgenin artmasıyla binom katsayılarıyla doldurulurlar. Özellikle, üstteki artan 7 köşegen, sondaki sıfırlar dikkate alınmadan aşağıdaki sayısal diziyi oluşturur:
Genel olarak, artan köşegen sayısı n, her birinin endekslerinin toplamı (n1)'e eşit olan aşağıdaki binom katsayılarını içerir:
Kombinasyon numaralarının toplama özdeşliği sayesinde, her bir köşegen eleman, önceki iki artan köşegenden indekslere karşılık gelen iki elemanın toplamına eşittir. Bu, Pascal üçgenini köşegen boyunca sonsuza kadar genişleterek, her bir sonraki artan köşegenin önceki iki köşegendeki bitişik yatay elemanların ikili toplamı ile oluşturulmasına olanak tanır. Aşağıdaki Pascal üçgeni parçası, 6 ve 7 numaralı köşegenler boyunca artan 8 numaralı köşegenin yapısını göstermektedir:
Bu yapım yöntemiyle, 3'üncüden başlayarak herhangi bir yükselen köşegenin elemanlarının toplamı, önceki iki yükselen köşegenin elemanlarının toplamına eşit olacaktır ve ilk 2 köşegen yalnızca bir elemandan oluşur; değer bunlardan 1'dir. İlgili hesaplamaların sonuçları, Pascal'ın dik üçgeninin artan köşegenlerinin dikkate alınan özelliğinin geçerliliğini kontrol edebileceğiniz aşağıdaki sayısal seriyi oluşturur:
Bu sayıları analiz ederek, benzer bir yasaya göre, her bir sonraki sayının önceki iki sayının toplamına eşit olduğu ve ilk iki sayının 1'e eşit olduğu iyi bilinen Fibonacci sayıları dizisinin oluştuğunu görebilirsiniz:
Böylece şu önemli sonuca varabiliriz: Pascal üçgeninin elemanlarının köşegen toplamları Fibonacci dizisini oluşturur. Bu özellik Pascal üçgeninin başka bir ilginç özelliğini ortaya koymamızı sağlar. Fibonacci formülünü yinelemeli olarak genişleterek, ilk n Fibonacci sayısının toplamının (F n+2 1)'e eşit olduğunu kanıtlamak kolaydır.
Dolayısıyla üstteki n köşegeni dolduran binom katsayılarının toplamı da (F n+2 1)'e eşittir. Buradan Pascal üçgeninin ilk n köşegeninin toplamının, (n+2) sayısıyla köşegeninde yer alan binom katsayılarının toplamından 1 eksik olduğu sonucu çıkar.
Sonuç olarak, Pascal üçgeninin yatay, dikey ve köşegenlerinin dikkate alınan özelliklerinin, ilk bakışta hiçbir ortak yanı olmayan çeşitli matematiksel yönleri birbirine bağlayan çok çeşitli olasılıkları tüketmediğine dikkat edilmelidir. Bu tür olağandışı özellikler, Pascal üçgenini, tüm yetenekleri listelenemeyen ve abartılması zor olan en mükemmel sayısal sistemlerden biri olarak görmemize olanak tanır.
Pascal üçgenini kullanarak kombinasyon sayısını hesaplamak için kullanılan algoritma aşağıda sunulmuştur:
Özel Fonksiyon SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) i = 0 To n TT (0, i) = için 1 TT (i, i) = 1 Sonraki i = 2'ye n'ye j için = 1'e i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Sonraki Sonraki SochTT = TT (n, k) Son Fonksiyon
Kombinasyon sayısını birçok kez hesaplamanız gerekiyorsa, Pascal üçgenini bir kez oluşturmak ve ardından diziden veri almak daha uygun olabilir.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j Tamsayı Olarak ReDim TT'yi Koru (bitiş, bitiş) i = başlangıç için bitiş için TT (0, i) = 1 TT (i, i) = 1 Sonraki If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Öncelikle CreateTT prosedürünü çağırmanız gerekir. Daha sonra SochTT fonksiyonunu kullanarak kombinasyon sayısını elde edebilirsiniz. Artık üçgene ihtiyacınız kalmadığında TerminateTT prosedürünü arayın. Yukarıdaki kodda SochTT fonksiyonu çağrılırken üçgen henüz gerekli seviyeye tamamlanmadıysa BuildTT prosedürü kullanılarak tamamlanır. Fonksiyon daha sonra TT dizisinin istenen elemanını alır ve onu döndürür.
Dim X () As Tamsayı Dim Counter () As Tamsayı Dim K As Tamsayı Dim N As Tamsayı Public Sub Soch() Dim i As Tamsayı N = CInt(InputBox("N Girin")) K = CInt(InputBox("K Girin) ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 j = 1 için N için X1(j) ise<>0 Sonra n1 = n1 + 1 Eğer n1 = Counter(i) ise Then Out(i) = X1(j) X1(j) = 0 Çıkış İçin Son If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Sonraki txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
DOĞAL SAYILARIN KOMBİNASYONLARININ LİSTELENMESİ
Birçok pratik problemi çözmek için, belirli bir sonlu kümenin elemanlarından elde edilebilecek tüm sabit önem kombinasyonlarını listelemek ve sadece bunların sayısını belirlemek gerekir. Herhangi bir sonlu kümenin elemanlarının tamsayı numaralandırılmasının her zaman var olan olasılığını hesaba katarsak, çoğu durumda kendimizi doğal sayıların kombinasyonlarını numaralandırmak için algoritmaların kullanımıyla sınırlamamıza izin verilir. Bunlardan en doğal ve basit olanı, doğal sayıların kombinasyonlarını listeleyen algoritmadır. sözlük düzeni.
Bu algoritmayı resmi olarak tanımlamak için, m elemanının tüm kombinasyonlarının listelenmesi gereken ana kümenin, 1'den n'ye kadar ardışık doğal sayılar oluşturduğunu varsaymak uygundur. O halde m'nin herhangi bir kombinasyonu Sıralamanın bir sonucu olarak, böyle bir kombinasyon vektörünün her bir konumundaki değerin, doğal olarak, aşağıdaki gibi yukarıdan ve aşağıdan değer olarak sınırlı olduğu ortaya çıkar: Sözlüksel algoritma, sözlüksel olarak en küçük vektörden başlayarak bu tür kombinasyon vektörlerini sırayla üretir; burada tüm konumlar, endekslerine eşit aşağıdaki minimum olası eleman değerlerini içerir: Her ardışık kombinasyon vektörü, henüz sınır değerine ulaşmamış en sağdaki elemanı bulmak için elemanları soldan sağa doğru tarandıktan sonra mevcut olandan oluşturulur: Böyle bir elemanın değeri 1 artırılmalıdır. Sağındaki her elemana, sol komşusundan 1 büyük olan mümkün olan en küçük değer atanmalıdır. Bu değişikliklerden sonra, bir sonraki kombinasyon vektörü aşağıdaki temel bileşime sahip olacaktır: Böylece, bir sonraki kombinasyon vektörü, ilk (j1) elemanlarının değerleri değer olarak eşit olduğundan ve j konumundaki elemanın değeri bir öncekinden 1 daha büyük olduğundan sözlüksel olarak öncekinden daha büyük olacaktır. . Artan sözlüksel sıranın belirtilen ilişkisinin, algoritmanın tüm yinelemelerinde karşılanması garanti edilir. Sonuç, tüm konumlardaki öğelerin aşağıdaki maksimum değerlere sahip olduğu, sözlükbilimsel olarak en büyük kombinasyon vektörüyle tamamlanan, artan bir sözlüksel dizidir: Dikkate alınan sözlüksel algoritma aşağıdaki örnekte gösterilmektedir; burada n=6 birinci doğal sayıların 15 kombinasyonunun tamamının m=4 sayılarla, yani ana oluşturucunun tüm olası 4 elemanlı alt kümelerinin artan sözlüksel sırayla listelenmesi gerekir. 6 elementten (1, 2, 3, 4, 5, 6) ayarlayın. Hesaplama sonuçları aşağıdaki tabloda sunulmaktadır: Bu örnekte, kombinasyon vektörlerinin konumlarındaki sayıların izin verilen en büyük değerleri sırasıyla 3, 4, 5 ve 6'dır. Sonuçların yorumlanmasını kolaylaştırmak için, her kombinasyon vektöründe en sağdaki öğe, henüz maksimum değerine ulaşmadığının altı çizilmiştir. Kombinasyon vektörlerinin sayısal endeksleri, sayılarını sözlüksel sıraya göre belirler. Genel durumda, n öğenin m ile herhangi bir kombinasyonunun sözlüksel numarası N, aşağıdaki formül kullanılarak hesaplanabilir; burada kozmetik nedenlerden dolayı kombinasyon sayısını belirtmek için Appel sembolizmi kullanılır: Özellikle m=4'ün n=6 elemanının kombinasyon numarası (1, 3, 4, 6) için bu formülün sözlüksel sırayla kullanıldığı aşağıdaki hesaplamalar, yukarıda tartışılan örneğe karşılık gelen N=8 sonucunu verecektir: Genel durumda, her iki indeks için kombinasyon sayılarının toplamı için özdeşlik kullanılarak, bu kullanılarak hesaplandığında sözlükbilimsel olarak en küçük kombinasyonun (1, ... i, ... m) sayısını göstermek mümkündür. formül her zaman 1'e eşit olacaktır: Bu formül kullanılarak hesaplandığında, sözlüksel olarak en büyük kombinasyonun (m, … nm+i, … n) sayısının, m'ye göre n elemanın kombinasyon sayısına eşit olacağı da açıktır: Sözlüksel kombinasyon sayılarını hesaplama formülü, kombinasyon vektörünü sözlüksel sırayla numarasına göre belirlemeniz gereken ters problemi çözmek için kullanılabilir. Böyle bir ters problemi çözmek için, istenen kombinasyonun vektörünün elemanlarının tüm bilinmeyen değerlerinin (C 1, ... C i, ... C m) olduğu bir denklem şeklinde yazılmalıdır. ) sağ tarafındaki kombinasyon sayısında yoğunlaşmıştır ve kombinasyon sayısının bilinen farkı L, her m'de n elemanın ve gerekli kombinasyon N sayısının sol tarafına yazılmıştır: Bu denklemin çözümü, istenen kombinasyonun vektörünün elemanlarının değerlerinin sırayla seçildiği yinelemeler sırasında aşağıdaki "açgözlü" algoritma ile sağlanır. İlk yinelemede, C1'in mümkün olan minimum (sınırlamaları dahilinde) değeri seçilir; burada sağ taraftaki ilk terim, L'yi aşmayan bir maksimum değere sahip olacaktır: Şimdi L'nin sol tarafı, seçilen C 1 değeri ile sağ taraftaki ilk kombinasyon sayısı kadar azaltılmalı ve benzer şekilde ikinci yinelemede C 2'nin değeri belirlenmelidir: Benzer şekilde, istenen kombinasyonun diğer tüm C i elemanlarının değerlerini, son C m elemanına kadar seçmek için sonraki tüm yinelemeler gerçekleştirilmelidir: Açık nedenlerden dolayı, son Cm elemanının değeri, kombinasyon sayısının L'nin sol tarafındaki artık değere eşitliğine dayanarak belirlenebilir: C m kombinasyonunun son elemanının değerinin, olası değerleri numaralandırmadan daha basit bir şekilde bulunabileceğine dikkat edilmelidir: Ele alınan algoritmanın yinelemelerinin uygulanması, eğer n=6 ve m=4 ise, N=8 rakamlı kombinasyonların sözlüksel sırayla belirlenmesinin gerekli olduğu aşağıdaki örnekle gösterilmektedir: Belirli bir sayıya göre bir kombinasyonun sözlüksel sırayla belirlenmesine yönelik algoritmik yetenek, çeşitli yönlerde kullanılabilir. Özellikle kombinasyonları sözlüksel sıraya göre listelerken daha önce elde edilen herhangi bir kombinasyona geri dönüş sağlanması gerekir, sadece numarasını bilmek yeterlidir. Ek olarak, sözlüksel numaralarının keyfi olarak verilen bir dizisiyle düzenlenen herhangi bir sırada kombinasyonlar oluşturmak mümkün hale gelir. Şimdi sözlükbilimsel sıraya göre kombinasyonlar oluşturmak için bir algoritma sunuyoruz: i için 2:= 1'den k'ye A[i] := i; 5 yazmaya başla(A, …, A[k]); 6 eğer A[k] = n ise p:= p 1 değilse p:= k; i için 8:= k'den p'ye kadar do A[i] := A[p] + i p + 1 TEKRAR EDİLEN ELEMANLARLA KOMBİNASYONLAR Tüm öğelerin farklı olduğu klasik bir kombinasyonun aksine, tekrarlı bir kombinasyon, herhangi bir öğenin süresiz olarak sıklıkla görünebildiği ve tek bir kopyada mutlaka mevcut olmadığı sonlu bir kümenin öğelerinin sırasız bir seçimini oluşturur. Bu durumda, elemanların tekrar sayısı genellikle sadece kombinasyonun uzunluğu ile sınırlıdır ve en az bir elemanda farklılık gösteren kombinasyonlar farklı kabul edilir. Örneğin 1, 2 ve 3 numaralı setten isteğe bağlı olarak farklı 4 sayı seçerek aşağıdaki 15 tekrarlı kombinasyonu oluşturabilirsiniz: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Genel olarak tekrarlı kombinasyonlar, n adet rastgele tipte eleman seçilerek oluşturulabilir. Ancak her zaman 1'den n'e kadar ardışık doğal sayılarla ilişkilendirilebilirler. Daha sonra bu aralıktaki m isteğe bağlı olarak farklı sayıların herhangi bir kombinasyonu, soldan sağa azalmayacak şekilde düzenlenerek vektör biçiminde yazılabilir: Doğal olarak, bu notasyon biçiminde, sınırsız tekrar olasılığı nedeniyle herhangi bir komşu öğe eşit olabilir. Bununla birlikte, n elemanın m kadar tekrarına sahip her bir kombinasyon vektörü, (n+m−1) elemanlarının m kadar birleşim vektörü ile ilişkilendirilebilir; bu, aşağıdaki şekilde oluşturulur: F vektörünün elemanlarının herhangi bir değeri için, C vektörünün elemanlarının farklı olacağı ve değerlerinin 1'den (n+m1)'e kadar artan sırasına göre kesin olarak sıralanacağının garanti edildiği açıktır. : F ve C kombinasyon vektörlerinin elemanları arasında bire bir yazışmanın varlığı, n elemanın m'ye göre tekrarlandığı kombinasyonların sistematik olarak listelenmesi için aşağıdaki basit yöntemi önermemize olanak tanır. Yalnızca, örneğin, m'nin (n+m1) elemanlarının tüm C kombinasyonlarını sözlüksel sırayla listelemek, her birinin elemanlarını aşağıdaki formülü kullanarak sırayla f tekrarlarıyla kombinasyonların karşılık gelen elemanlarına dönüştürmek gerekir: Sonuç olarak, elemanların tekrarı olmadan karşılık gelen kombinasyonların listelenmesiyle oluşturulan sıraya göre düzenlenen, elemanların tekrarlarına sahip bir kombinasyon vektörleri dizisi oluşturulur. Özellikle, 4 basamaklı tekrarlarla 3 basamaklı 1, 2 ve 3'ten oluşan yukarıdaki kombinasyon dizisini elde etmek için, 6 basamaklı 1,2,3,4, 5'in tekrarı olmayan tüm kombinasyonların sözlüksel sırayla listelenmesi gerekir. ve 6'nın her biri 4 rakamdır ve belirtildiği gibi dönüştürülür. Aşağıdaki örnek, (1,3,4,6) kombinasyonunun sözlükbilimsel sayı 8 ile böyle bir dönüşümünü göstermektedir: Öğelerin tekrarı olan ve olmayan kombinasyonlar arasında dikkate alınan bire bir uygunluk, bunların kümelerinin eşit derecede güçlü olduğu anlamına gelir. Dolayısıyla genel durumda, n elemanın m kadar tekrarlandığı kombinasyonların sayısı, (n+m1) elemanların m kadar tekrarlandığı kombinasyonların sayısına eşittir. Tekrarları f olan ve tekrarları olmayan C kombinasyonlarının sayısını belirtmek için aynı sembolizmi kullanarak, bu eşitlik şu şekilde yazılabilir: Yukarıda ele alınan örnekte (n=3 ve m=4) tekrar kombinasyonlarının sayısının 15'e eşit olacağını kontrol etmek kolaydır; bu da bunların doğrudan listelenmesinin sonucuyla örtüşür: Klasik versiyonun aksine, n ve m tekrarlı kombinasyon parametrelerinin değerlerinin birbiriyle doğrudan ilişkili olmadığı, dolayısıyla pozitif değerlerinin herhangi bir kombinasyonu için f(n,m)>0 olduğuna dikkat edilmelidir. Karşılık gelen sınır koşulları (n+m1) ve (n1) veya (n+m1) ve m değerleri arasındaki eşitlikten belirlenir: Ayrıca, m 1'e eşitse öğelerin tekrarının mümkün olmayacağı ve dolayısıyla herhangi bir n>0 pozitif değeri için aşağıdaki eşitliğin doğru olacağı da oldukça açık olmalıdır: Ek olarak, n ve m'nin herhangi bir pozitif değeri için tekrarlı kombinasyon sayıları için, elemanların tekrarı olmayan kombinasyon sayıları için toplama kimliğine benzer olan aşağıdaki yineleme ilişkisi geçerlidir: Aslında, karşılık gelen sayıdaki kombinasyonların tekrarlama olmadan sol ve sağ taraflarına biçimsel olarak ikame edilmesiyle belirtilen ekleme kimliğine dönüşür: Dikkate alınan yineleme ilişkisi, faktöriyel ürünlerin hesaplanmasında emek yoğun işlemleri ortadan kaldırmanın ve bunları daha basit toplama işlemleriyle değiştirmenin önemli olduğu durumlarda, tekrarlı kombinasyonların sayısını etkili bir şekilde belirlemek için kullanılabilir. Bu durumda, f(n,m) değerini hesaplamak için, f(1,m) ve f(i,1) formundaki terimlerin toplamını elde edene kadar bu yineleme ilişkisini uygulamanız yeterlidir; burada i n'den 1'e kadar olan aralıktaki değerleri alır. Miktarın tanımı gereği bu tür terimler sırasıyla 1 ve i'ye eşittir. Aşağıdaki örnek, bu dönüştürme tekniğinin n=3 ve m=4 durumu için kullanımını göstermektedir: İKİLİ KOMBİNASYONLARIN LİSTELENMESİ Donanımdaki kombinasyonları veya montaj dilindeki programlamayı uygularken, kombinasyon kayıtlarını ikili formatta işleyebilmek önemlidir. Bu durumda, m'nin n elemanının herhangi bir kombinasyonu, n bitlik bir ikili sayı (B n,...B j,...B 1) biçiminde belirtilmelidir; burada m birim rakamı, m'nin elemanlarını gösterir. kombinasyon ve geri kalan (nm) haneler sıfır değere sahiptir. Açıkçası, bu gösterim biçiminde, 1'lerin rakamlarının düzeni açısından farklı kombinasyonların farklı olması gerekir ve n bitlik bir ikili kümede m birleri veya (nm) sıfırları düzenlemenin yalnızca C(n,m) yolları vardır. Örneğin, aşağıdaki tablo, rastgele bir kümenin (E 1 , E 2 , E 3 , E 4 ) 2'ye kadar 4 öğesinin tüm kombinasyonları için 4 bitlik ikili sayılar sağlayan bu tür 6 ikili kombinasyonun tamamını listeler: Genel durumda, bu tür ikili kombinasyonların numaralandırılması görevi, m bir ve (nm) sıfır bitlerin farklı düzenlemeleriyle tüm n bitlik ikili kümelerin sistematik olarak aranmasına indirgenir. En basit biçimde, bu tür bir arama, bitişik bitlerin bir kaydırmayla yer değiştirmesine yönelik çeşitli yöntemlerle (transpozitif kaydırma algoritmaları) gerçekleştirilir. Bunlar yinelemeli algoritmalardır ve adları her adımda gerçekleştirilen işlemlerin doğasını yansıtır. Transpozitif kaydırma algoritmalarının yinelemeli prosedürleri, bir ikili kümeyle başlayan, tüm birlerin düşük dereceli rakamlarda (sağda) yoğunlaştığı ve tüm 1'lerin yüksek dereceli rakamlarda olduğu zaman biten ikili kombinasyon dizileri oluşturur ( soldaki): Başlangıç ve son kombinasyonlarda eşleşirken bu diziler, ara ikili kümelerin listelenme sırasına göre farklılık gösterir. Bununla birlikte, her durumda, sonraki her ikili kombinasyon, ilgili aktarma ve kaydırma işlemlerinin gerçekleştirilmesinin bir sonucu olarak bir öncekinden oluşturulur. Aynı zamanda, çeşitli transpozitif kaydırma algoritmaları, aktarma için bir çift bit ve kaydırma için bir bit grubu seçme biçimleri açısından farklılık gösterir. Bu özellik aşağıda sola ve sağa kaydırmalı aktarım algoritmaları için tartışılmaktadır. Sola kaydırmalı transpozisyon algoritmasında, her adımda, en soldaki rakam çifti 01'in 10 ile değiştirilmesi (transpozisyon) ve varsa önde gelen birim rakam grubunun 01'e yakın kaydırılmasıyla mevcut kombinasyondan bir sonraki ikili kombinasyon elde edilir. aktarmadan (kaydırma) sonra elde edilen çift 10. Bu durumda mevcut ikili kombinasyonda ön basamaklarda hiç birim yoksa, bu adımda aktarma sonrasında baş birim elde edilse bile kaydırma gerçekleştirilmez. Aktarımdan sonra elde edilen çiftten (10) önce en anlamlı bitlerde sıfır olmadığında da kaydırma yapılmaz. Dikkate alınan eylemler, bu algoritmanın iki ardışık yinelemesinin gerçekleştirilmesine ilişkin aşağıdaki örnekle gösterilmektedir; burada bir yinelemede (15) yalnızca aktarma (T") gerçekleştirilir ve diğer yinelemede (16) aktarma bir kaydırma () ile tamamlanır. T"+S"): Sağa kaydırma algoritmasında kavramsal olarak her adımda benzer adımlar gerçekleştirilir. Yalnızca aktarma, 01'in en sağdaki bitlerinin (en soldakiler yerine) 10 ile değiştirilmesini ve ardından sağındaki tüm bitlerin en az anlamlı bitlere kaydırılmasını sağlar. Daha önce olduğu gibi, kaydırma yalnızca sağa kaydırılabilecek birimler varsa gerçekleştirilir. Dikkate alınan eylemler, bu algoritmanın iki ardışık yinelemesinin gerçekleştirilmesine ilişkin aşağıdaki örnekle gösterilmektedir; burada bir yinelemede (3) yalnızca aktarma (T") gerçekleştirilir ve diğer yinelemede (4) aktarma bir kaydırma () ile tamamlanır. T"+S"): İkili kombinasyonlar 2 tabanlı sayı sisteminde tamsayılar olarak yorumlanırsa, her iki algoritmanın yinelemelerinin toplamalı biçimde yazılabildiğine dikkat edilmelidir. Özellikle sağa kaydırmalı transpozisyon algoritması için, her bir sonraki ikili kombinasyon (B" n) ,…B" j , …B" 1), her zaman geçerli kombinasyondan (B n,…B j,…B 1) aşağıdaki toplama formülü kullanılarak tam sayıların eklenmesi işlemleri gerçekleştirilerek elde edilebilir: Bu toplama formülünde, f ve t ikilerinin kuvvetlerinin üsleri, sırasıyla mevcut ikili kombinasyonun düşük dereceli sıfır basamaklarının sayısını ve bunların solundaki satırdaki birlerin sayısını belirtir. Örneğin, n=6 haneli 4. ikili kombinasyon (001110) için f =1 ve t =3. Bu nedenle, 5. yinelemede toplama formülü kullanılarak bir sonraki ikili kombinasyonun hesaplanması, aktarma ve kaydırma işlemlerinin gerçekleştirilmesine eşdeğer olan aşağıdaki sonucu verecektir: Söz konusu aktarma algoritmalarının sola ve sağa kaydırmalarla karşılaştırmalı bir analizi için, yinelemelerinde ürettikleri ikili kombinasyon dizilerinin karşılaştırılması tavsiye edilir. Aşağıdaki tablo, sırasıyla sol (TSL) ve sağa (TSR) kaydırma algoritmaları tarafından elde edilen, 2'lik 4 öğeden oluşan bu tür iki ikili kombinasyon dizisini göstermektedir: Bu 2 diziyi karşılaştırdığınızda bunların ters ayna olduğunu görebilirsiniz. Bu, dizilerinin karşılıklı zıt uçlarından aynı mesafede bulunan herhangi iki ikili kombinasyonun birbirinin ayna görüntüsü olduğu, yani herhangi birindeki bitlerin indekslenmesi ters çevrildiğinde çakıştıkları anlamına gelir. Örneğin, TSL dizisinin başlangıcından itibaren ikinci ikili model (0101), TSR dizisinin sonundan ikinci olan ikili modelin (1010) ayna görüntüsüdür. Genel olarak, bir dizinin i numarasıyla herhangi bir ikili kombinasyon, başka bir dizinin (ni+1) sayısıyla ikili kombinasyonunun ayna görüntüsüdür. Bu diziler arasındaki bu ilişki, ikili kombinasyonların numaralandırılması için dikkate alınan iki algoritmadaki aktarma ve kaydırma işlemlerinin simetrik doğasının bir sonucudur. İkili formatın, öğelerin tekrarı olan kombinasyonları kaydetmek için de kullanılabileceği belirtilmelidir. Bunun için aşağıdaki gibi oluşturulan tekrarlı kombinasyonlar ile ikili kombinasyonlar arasında birebir yazışmaların kurulması gerekmektedir. Jeneratör grubunun n elemanından isteğe bağlı olarak m farklı elemanın seçilmesiyle elde edilen tekrarlı keyfi bir kombinasyon olsun. İstenilen eşleşmeyi oluşturmak için, önce oluşturma kümesinin (cat) tüm öğelerini kombinasyona eklemeniz ve ardından ortaya çıkan birleştirmeyi (sıralama), tüm özdeş öğelerin yan yana olmasını sağlayacak şekilde sıralamanız gerekir. Sonuç, aynı elementlerden oluşan n grubun bulunduğu (n+m) elementlerden oluşan bir dizidir. Elemanlar arasında toplam (n+m1) boşluk olacaktır; bunlar arasında aynı eleman grupları arasında (n1) boşluk ve gruplar içindeki elemanlar arasında m boşluk olacaktır. Açıklık sağlamak için, belirtilen boşluklara “|” sembollerini yerleştirebilirsiniz. ve buna bağlı olarak. Şimdi 1'i gruplar arasındaki boşluklarla (|) ve 0'ı diğer tüm boşluklarla () eşleştirirsek, ikili bir kombinasyon elde ederiz. (n1)'in bir ve m sıfır bit olduğu, konumu n'den m'ye kadar olan öğelerin tekrarları ile orijinal kombinasyona benzersiz bir şekilde karşılık gelen ikili (n+m1) bit kümesinden oluşur. Dikkate alınan dönüşüm tekniği, elemanları ilk beş Latin harfinin oluşturucu kümesinden seçilen tekrarlı bir kombinasyon (BBD) kullanılarak bir ikili kombinasyonun (1001101) oluşturulmasına ilişkin aşağıdaki örnekle gösterilmektedir: Genel olarak, bu tür ikili kümelerin sayısı, (n1) birleri (veya m sıfırları) (n+m1) ikili basamaklarda düzenlemenin yollarının sayısını belirler. Bu değer açıkça (n+m1)'den (n1)'e veya m'ye kadar olan kombinasyonların sayısına, yani C(n+m1,n1) veya C(n+m1,m)'ye eşittir. her biri m olan n öğenin f( n,m) tekrarlarına sahip kombinasyonların sayısı. Bu nedenle, tekrarlı kombinasyonlar ve ikili kombinasyonlar arasında bire bir yazışma olduğundan, tekrarlı kombinasyonların numaralandırılmasını, örneğin sola veya sağa kaydırmalı transpozisyon algoritmaları kullanılarak ikili kombinasyonların numaralandırılmasına indirgemek meşrudur. Bundan sonra, elde edilen ikili kombinasyonları kullanarak yalnızca gerekli kombinasyonları tekrarlarla geri yüklemeniz gerekir. Bu her zaman aşağıdaki kurtarma tekniği kullanılarak yapılabilir. M tekrarlı kombinasyonların mutlaka farklı elemanlar oluşturmadığı elemanlardan oluşan ana setin, elemanlarının her biri 1'den n'ye kadar belirli bir seri numarasına sahip olacak şekilde keyfi bir şekilde sıralanmasına izin verin. Ayrıca, (n+m1) ikili basamakların (n1) birler ve m sıfır basamaklardan oluşan ikili kombinasyonlarının numaralandırmasını da uygulayalım. Ortaya çıkan her ikili kombinasyon, solda hayali bir birim rakamıyla tamamlanabilir ve tüm birim rakamları, 1'den n'ye kadar tam sayılarla soldan sağa numaralandırılabilir. Daha sonra ikili kombinasyonun her i'inci biriminden sonraki satırdaki sıfırların sayısı, tekrarlarla karşılık gelen kombinasyondaki ana setin i'inci elemanının örneklerinin sayısına eşit olacaktır. Dikkate alınan teknik, aşağıdaki örnekle gösterilmektedir; burada, bir ikili kombinasyon (1001101) kullanılarak, elemanları alfabetik sırayla yazılan ilk beş Latin harfinin oluşturma kümesinden seçilen BBD tekrarlarına sahip bir kombinasyon geri yüklenir. , üst çizgi ise bu kombinasyonda bulunmayan öğeleri belirtir: Bu örneğin koşullarında benzer eylemleri gerçekleştirerek, 4'ü bir ve 3'ü sıfır olan 7 bitlik ikili kümeler oluşturan 35 ikili kombinasyonun tümünü listeleyebilir ve karşılık gelen kombinasyonları, 3'ün 5 öğesinin tekrarıyla geri yükleyebilirsiniz. Kış yaklaşıyordu ve Khoma ile Suslik bezelye stoklamaya karar verdiler. Bütün gün ahıra koştular ve birkaç bakla taşıdılar: Dört tane Khoma ve iki tane Suslik. Akşama doğru topladıkları tüm baklaları saydılar ve bu bezelyeleri şimdi nasıl böleceklerini merak ettiler. Khoma, Suslik'in iki katı kadar sürüklerse iki kat daha fazla bezelye alması gerektiğini savundu. Suslik buna makul bir şekilde itiraz etti; birincisi Khoma'nın hızı Suslik'inkinden gözle görülür derecede düşüktü ve ikincisi, kim bilir belki de Khoma sadece bir veya iki kez kaçtı ve geri kalan zamanlarda boştaydı... Arkadaşlarınızın bu zor durumu en azından biraz anlamalarına yardımcı olun. Suslik'in kaç kapsül ve kaç Khoma getirdiğine ilişkin tüm olası seçenekleri belirleyin. İlk satırda doğal bir çift sayı olan M vardır - çalınan kapsüllerin sayısı, 2 ≤ M ≤ 1000. Suslik ve Khoma tarafından getirilen kapsül miktarlarının tüm olası kombinasyonları, hat başına bir kombinasyon. Her kombinasyon, bir boşlukla ayrılmış, negatif olmayan iki tam sayıyı temsil eder: ilk sayı Suslik tarafından getirilen kapsüllerin sayısıdır, ikincisi ise Khoma tarafından getirilen kapsüllerin sayısıdır. Kombinasyonları ilk sayıya göre azalan şekilde sıralayın. #katmak ad alanı std'yi kullanma; int ana()( int a, b = 0; cin >> a; while (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
a-= 4; b+= 4; 0 değerini döndür; Homa'nın getirdiği bakla sayısı a, Suslik'in getirdiği bakla sayısı b olsun. Sorunun koşullarına göre Khoma yalnızca dört bölme taşıdığından, Suslik ve Khoma tarafından getirilen bölme sayısının tüm olası kombinasyonlarını sıralamak amacıyla a = a-4 ve b = b + 4'ü dikkate alacağız. Ayrıca bir döngü kullanalım sırasında Bu, yukarıda açıklanan eylemi \geq 0'a kadar tekrarlayacaktır. Cevapta, arkadaşlarımızın getirdiği bölme sayılarının tüm olası kombinasyonlarını, her satıra bir tane olacak şekilde, ilk sayıya göre azalan sırada yazdırırız. Örnek // 52 üzerinden 3'ün kombinasyonu for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Burada, çözümü RuNet'te bulamadığım daha karmaşık bir soruna bakacağız (ancak bir bağlantı vereceğim, ancak bu formül açıkça yanlıştır) - kombinasyonun kendisine dayanarak (bu durumda bir dizi üç sayı) dizinini bulun. Kesinlik açısından i1 = 3, i2 = 7, i3 = 12 şeklinde sıraladıktan sonra varsayalım. Tipik bir oluşturma algoritması, 52 üzerinden 2'lik kombinasyonlar üretmemiz ve iç içe geçmiş bir döngüdeki bu tür her kombinasyon için 50 üzerinden 3'lük kombinasyonlar üretmemiz ve iç içe kombinasyondaki endekslerin (i3, i4, i5) doğru olup olmadığını kontrol etmemizdir. harici kombinasyondaki endekslerle (i1, i2) örtüşmüyor: C++ kodu // HARİCİ KOMBİNASYON for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
C++ kodu if (i3 >= i1) --i3; if (i3 >= i2) --i2; // i4, i5 için benzer Dizini 2, 3, 47'ye bölmek için örnek kod int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // 52 üzerinden 2'nin kombinasyonunun indeksi, C(3, 50) ile çarpılır int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // Dahili grubu, numaralandırma 0...49 olacak şekilde "yeniden indeksleyin", eğer (i3 > = i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5 ; if (i5 >= i2) --i5; // Şimdi kombinasyonun indeksini 3 ile ekleyin // 0: // n = 0 için TOPLA by i3-1 KOMBİNASYONLAR (2, 49-n) // = TOPLA için m = 50-i3 x 49 (m * (m-1) / 2) ofset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // n = i3+1'den i4-1'e kadar TOPLA KOMBİNASYONLAR (1, 49-n) ofset += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // n = i4+1 ila i5-1 için TOPLA (1) ofset + = (i5 - i4 - 1); dönüş uzaklığı; ) Genel olarak kombinatoryal algoritmaları aşağıdaki sınıflara ayırırım: Kombinasyon sayısı Kombinasyon itibaren Nİle k set denir k verilerden seçilen öğeler N elementler. Yalnızca öğelerin sırası farklı olan (ancak bileşim açısından farklı olmayan) kümeler aynı kabul edilir; bu nedenle kombinasyonlar yerleşimlerden farklıdır. Kombinasyon sayısı Nİle k
binom katsayısına eşit Sabit bir değer için N tekrarlı kombinasyon sayıları oluşturma fonksiyonu Nİle k dır-dir: Tekrarlı kombinasyon sayılarının iki boyutlu üretme fonksiyonu: Wikimedia Vakfı. 2010. 70 yetmiş 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Çarpanlara ayırma: 2×5×7 Roma notasyonu: LXX İkili: 100 0110 ... Wikipedia Işık numarası, dışsallığı benzersiz bir şekilde ifade eden koşullu bir sayı fotoğraf sırasındaki koşullar (genellikle konunun parlaklığı ve kullanılan fotoğraf malzemesinin ışığa duyarlılığı). E. h.'nin herhangi bir değeri birkaç kez seçilebilir. kombinasyon açıklık numarası... ... Büyük Ansiklopedik Politeknik Sözlüğü İki nesneyi hem tek bir nesneye hem de birçok nesneye göre ayıran bir sayı biçimi. Bu form modern Rusça'da mevcut değildir, ancak etkisinin kalıntıları kalmaktadır. Yani, iki tablonun kombinasyonları (çoğulla karşılaştırın... ... Dilsel terimler sözlüğü Kombinatoryal matematik, kombinatorik, belirli, genellikle sonlu bir kümenin elemanlarını verilen kurallara uygun olarak seçme ve düzenleme problemlerini çözmeye adanmış bir matematik dalı. Bu tür kuralların her biri inşaat yöntemini belirler... ... Matematik Ansiklopedisi Kombinatorikte, by'nin bir kombinasyonu, farklı öğeler içeren belirli bir kümeden seçilen bir öğe kümesidir. Yalnızca öğelerin sırasına göre farklılık gösteren (ancak bileşimde olmayan) kümeler aynı kabul edilir, bu kombinasyonlar ... ... Vikipedi Oluşumu kesin olarak bilinmeyen olayların incelenmesiyle uğraşır. Olayların olasılıklarına sayısal değerler atamak çoğu zaman gereksiz olsa da, bazı olayların gerçekleşmesini beklemenin makul olup olmadığını diğerlerine kıyasla yargılamamıza olanak tanır... ... Collier Ansiklopedisi 1) matematiksel kombinatoryal analizle aynı. 2) Belirli bir sonlu nesne kümesinden oluşturulabilen, belirli koşullara bağlı olarak kombinasyon sayısının incelenmesiyle ilgili temel matematik bölümü... ... Büyük Sovyet Ansiklopedisi - (Yunan paradoksu beklenmedik, tuhaf) geniş anlamda: genel kabul görmüş, yerleşik görüşten keskin bir şekilde ayrılan bir ifade, "kayıtsız şartsız doğru" görünenin reddi; Daha dar anlamda iki karşıt ifade, çünkü... ... Felsefi Ansiklopedi - (veya dahil etme ve hariç tutma ilkesi), genel durumda birbiriyle kesişebilen sonlu sayıda sonlu kümelerin birliğinin önem derecesini belirlemenize olanak tanıyan bir kombinatoryal formül ... Wikipedia Belirli nesneleri bilinen bir sıraya göre dağıtmanın farklı yollarının sayısını belirlemeyle ilgili bir matematik teorisi; denklemler teorisi ve olasılık teorisinde özellikle önemlidir. Bu türden en basit görevler... ... Ansiklopedik Sözlük F.A. Brockhaus ve I.A. EfronGiriş verileri
Çıktı
Testler
Giriş verileri
Çıktı
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Program kodu
Sorunun çözümü
Kombinasyon indeksi
Her kombinasyon, permütasyon, düzenleme ve diğer kombinatoryal nesneler bir indeksle ilişkilendirilebilir; bu, bu algoritmayı yinelerken ortaya çıkan sayıdır.
“Kafa kafaya” arama seçeneği var. Kombinasyon sayacını açıyoruz, yukarıdaki algoritmayı alıyoruz ve istenen seçeneğe ulaşana kadar her şeyi deniyoruz. Bu seçeneğin zaman karmaşıklığı çok yüksektir, dolayısıyla bu seçeneği göz ardı edeceğiz.
Girişin i1, i2, i3 sayılarını içerdiğini varsayalım. Her şeyden önce, bunları artan sırada düzenlememiz gerekir ("kombinasyon" kavramının kendisi keyfi bir sırayı ima etse de, yukarıda verilen üretim algoritmasının kendisinin bunları her zaman sıralı biçimde ürettiğine dikkat edin).
Bu, i1'in 0, 1 ve 2'ye eşit olduğu tüm kombinasyonları "geçtiğimiz" anlamına gelir.
i1 = 0 için C(2, 51) kombinasyonlarını inceledik, çünkü i1, i2 endeksleri 51 sayıdan 2'sinin tüm kombinasyonlarını geçiyor.
i1 = 1 için C(2, 50) kombinasyonlarını inceledik.
i1 = 2 için C(2, 49) kombinasyonlarını inceledik.
Toplamda, SUM'dan geçtik (n = 0'dan n = i1-1'e) C(2, 51-n).
i1 = 3 için, i2 indeksini incelerken karşılaştığımız kombinasyonları ele alalım (ve bizim için i2 = i1+1 = 4 ile başlar).
i2 = 4 olduğunda C(1, 47) kombinasyonları geçti, i2 = 5 olduğunda C(1, 46) kombinasyonları geçti, i2 = 6 olduğunda C(1, 45) kombinasyonları geçti.
Tam bir benzetme yaparak, i2 = 7 için i3 endeksinin içinden geçtiği kombinasyonları dikkate alıyoruz.
Genel formülü elde ederiz:
Gerekli kombinasyon indeksi = TOPLA (n = 0'dan i1-1'e) C(2, 51-n) + TOPLA (n = i1+1'den i2-1'e) C(1, 51-n) + TOPLA (başlangıçtan itibaren) n = i2+1 ila i3-1)C (0, 51-n).Alt küme dizini
Kombinatorikte daha karmaşık bir nesne vardır; alt kümelere bölme. Örneğin, 52 elemanlı bir kümeyi sırasıyla 2, 3 ve 47 elemanlı üç alt kümeye bölmek; burada her bir alt kümedeki öğelerin sırası önemsizdir. (Bu arada, 52 üzerinden 2'nin birleşimi, sırasıyla 2 ve 50 öğeden oluşan iki alt kümeye bölünmenin özel bir durumudur).
Yine, bu tür bölümlerin her birinin kendi dizini vardır.
Kombinasyon indeksini bulmaya yönelik algoritmamızın, bölüm indeksini bulmak için değiştirilebileceği ortaya çıktı.
"Harici kombinasyon" i1, i2'deki endeksleri kendi aralarında ve i3, i4, i5 endekslerini kendi aralarında, ancak ilk ikisinden bağımsız olarak düzenlememiz gerektiğine dikkat edilmelidir.
Şunu da hesaba katmak gerekir ki, "iç içe kombinasyon"da aslında 50 elemanlı bir setle çalışıyoruz, ancak i3, i4, i5 endekslerinin 0'dan değişmemeleri için belirli bir şekilde "kaydırılması" gerekiyor. 51'e kadar, ancak 0'dan 49'a kadar:
(deyim yerindeyse, 52 elemanlı kümemizden i1, i2 endekslerini kesiyoruz ve ardından kalan seti delikleri kapatacak şekilde kaydırıyoruz, bu arada i3-i5 endeksleri kaydırılıyor).
Her bir “harici” kombinasyonun içinde tam olarak C(3, 50) “iç içe” kombinasyonlarımızın olduğu dikkate alınmalıdır.
Daha sonra algoritma aşağıdakine indirgenecektir:
COMBINATION_INDEX (i1, i2 / 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 / 50, indeks kaymasından sonra). Algoritmaların sürekli karmaşıklığa getirilmesi
Örneğin i1 = 0 (n = toplamını 0'dan -1'e kadar sayarız) veya i2 = 1 (toplamı 1'den 0'a kadar sayarız) durumunda formülde bir "hata" oluştuğunu hemen belirtmeliyim. Aslında bu gibi durumlarda karşılık gelen toplamın sıfıra eşit alınması gerekir ve sonuç doğru olacaktır.
Algoritmalarımızın zaman karmaşıklığına da dikkat etmeliyim: C'yi sabit zaman olarak kabul etmeniz koşuluyla, doğrusal karmaşıklığa sahiptirler. Bu zaten kaba kuvvetten çok daha iyi.
Ama aslında (bizim durumumuzda 52) algoritmayı sürekli karmaşıklığa indirgememizi hiçbir şey engellemez. Bunu yapmak için matematik bilgisini uygulayacağız ve tüm miktarları analitik olarak hesaplayacağız.
Örneğin, C(2, K) kombinasyonlarının sayısı, eğer onu K formülü biçiminde “genişletirseniz”! / ((K-2)! * 2!), 2. dereceden bir polinoma indirgenir. Ve bunu toplam işaretinin altında tuttuğumuz için, doğal serideki sayıların N'inci kuvvetlerinin toplamına ilişkin formülleri uygulayabilir (Wikipedia'ya bakın) ve 3. dereceden tek bir polinom elde edebiliriz. Açıkçası sabit zaman karmaşıklığına sahip. (Üstelik alt başlığın başında belirttiğim “hata” hiçbir şekilde kendini göstermiyor; formül doğru kalıyor).
Tekrar ediyorum, bu temel setin sabit boyutu için. Ancak, metaprogramlamanın yardımıyla derleyiciye bu işi sizin için yapmasını "öğretebileceğinizden" eminim. Sonsöz
Poker simülatörümde (Texas Hold'em), el kartlarımın (2 adet) ve tüm flop kartlarımın (masadaki 3 kart) olası tüm kombinasyonları için kazanma olasılıklarını önceden hesaplamak ve saklamak istedim. 52'li set 2, 3, 47'lik alt kümelerden oluşur.
Hesaplandı ve kaydedildi.
Ancak belirli bir kombinasyon için bir dosyadan veri okuma zamanı geldiğinde, gerçekten uzun süre bir şey hesaplamak veya gigabaytlık bir dosyada arama yapmak istemedim. Artık dosyadaki ofseti belirliyorum ve doğrudan ihtiyacım olanı okuyorum.
Permütasyonlar, kombinasyonlar, yerleşimler, alt kümeler, tekrarlı kombinasyonlar, tekrarlı yerleşimler dahil olmak üzere tüm kombinatoryal nesneler için kombinatoryal algoritmalar üzerine bir referans kitabına sahip olmak ilginç olurdu. Açık formüller
Bağlantılar
Diğer sözlüklerde “Kombinasyon sayısı”nın ne olduğuna bakın:
Kitabın