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, tüm sesli harfler kümesinden Latin harfleri(AEIOU) 3 harften oluşan 10 farklı kombinasyon oluşturarak aşağıdaki sırasız üçlüleri 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.
İÇİNDE genel durum 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çimine bakılmaksızın, n öğenin m öğeye 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 çarpımsal formülün n olduğunda bile geçerli kaldığı unutulmamalıdır. gerçek sayı, m ile aynı tamsayı değerine sahip. 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 hesaplamalarda tam sayıları temsil etme yeteneklerini aşar ve yazılım sistemleri. Ü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:
Sonrasında temel dönüşümler 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 çarpımlardaki ç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, toplama kimliğinden, sonlu toplamların hesaplanmasına yönelik çeşitli yararlı ilişkiler, özellikle aşağıdaki forma sahip olan alt simgeye göre toplama formülü türetilebilir:
Bu ilişki, toplama özdeşliğinde yinelemeyi, alt indisi 0'dan büyük olduğu sürece en büyük üst simgeye sahip terim boyunca genişletirsek elde edilir. Aşağıdaki sayısal örnek, göstermektedir. belirtilen süreç tekrarlanan dönüşümler:
Alt simge toplama formülü genellikle kuvvetlerin toplamını hesaplamak için kullanılır doğal sayılar. Ö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 yaygın olarak kullanılmaktadır. çeşitli alanlar modern hesaplamalı matematik. 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 kurstan ilköğretim matematikİki terimin toplamının karesi ve küpü için aşağıdaki formüller 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 fazlasını işlemek için yüksek dereceler(n>3) 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 Doğu Arap Orta Çağ matematikçileri tarafından bilindiğini belirtmek gerekir. Batı Avrupa. Bu nedenle ona ortak ad tarihsel olarak adil değil. Newton'un başarısı, bu formülü herhangi bir pozitif veya negatif rasyonel ve negatif alabilen keyfi bir gerçek üstel r durumuna genelleştirmesidir. irrasyonel değerler. 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: aşağıdaki gibi:
Ö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 binom formülü, Maclaurin formülünün özel bir versiyonudur; bu, genişlemeyi verir. keyfi işlev bir kuvvet serisinde. Newton bunu |z| için gösterdi.< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой doğal derece Sağ taraftaki r = n aynı zamanda (n+1) birinci terimlerin sonlu toplamı ile sonuçlanır, çünkü tüm C(n, k>n) = 0'dır. Şimdi Z=X/Y ayarlayıp 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, şunu elde edebiliriz: bütün bir seri ilginç ilişkiler. Ö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 yararlı kimlik, n ve k derecelerinin keyfi iki binomunun simetrik olarak yerleştirilmiş binom katsayılarının çarpımlarının toplamını kolayca hesaplamanıza olanak tanır. aşağıdaki formül Cauchy:
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, binom katsayılarını belirlemek için toplama kimliklerine ve kombinasyon sayısı simetrilerine dayanan 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 bu dikdörtgen masa yatay deformasyonla elde edilir ikizkenar üçgen Pascal. Sonuç olarak Pascal ikizkenar üçgeninin yan kenarlarına paralel olan sayı serileri Pascal dik üçgeninin dikey ve köşegenlerine dönüşür ve her iki üçgenin yatayları ç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 çeşitli şekilleri resmi olarak analiz etmek daha uygun hale gelir. sayısal özellikler Pascal dik üçgeninin yatay, dikey ve köşegenleri için binom katsayıları.
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:
İşte birkaç tane daha ilginç özellikler yatay çizgiler de ikinin kuvvetleriyle ilişkilendirilir. 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, yatay bir doğrunun tüm sayıları tek sayı ise tek olacaktır. daha az derece ikişerli (n=2 k 1). 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 bu nedenle 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 şu oran çıkıyor: köşeli parantezler bir N doğal sayısıdır ve istenen sonuç açıkça ortaya çıkar:
Bu sonucu kullanarak, iç elemanları belirli bir p asal numarasına bölünebilen Pascal üçgeninin tüm yatay 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. İÇİNDE aksi takdirde böyle bir yatay çizginin sayısı aynı zamanda asal bölenlerin kuvveti olmalıdır bileşik sayı, tüm iç unsurlarının bölünmüş olduğu, ancak bu şuna göre: bariz nedenler imkansız.
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. En büyük ortak bölen(GCD) n numaralı Pascal üçgeninin herhangi bir yatayının tüm iç elemanları şuna eşittir: asal sayı p eğer n=pk veya diğer tüm durumlarda 1 ise:
Herhangi bir 0 için OBEB(Cmn) = ( )< m < n .
Yatayların analizini sonuçlandırmak için, 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 dik üçgeninin dikeylerinin özelliklerinin analizi, onları oluşturan elemanların bireysel özelliklerinin incelenmesiyle başlatılabilir. 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ı bir düzlemde şu şekilde temsil edilebilir: eşkenar üçgen dama tahtası şeklinde düzenlenmiş rastgele nesnelerle (çekirdekler) doludur. 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 S k kare sayılarının ve genel olarak düzenli doldurmayla oluşturulan çokgen figürlü sayıların dikkate alınabileceği belirtilmelidir. düzenli çokgenler. Özellikle 4 başlangıç kare sayılarşu şekilde tasvir 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 karşılık gelir geometrik yapıüçgen, tetrahedral ve hipertetraedal sayılar, çünkü bu sayıların her birinin temsili daha düşük dereceli sayıları temsil eden nükleer katmanlardan oluşur. özellikle, n'inci üçgen T n sayısı, 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 7 artan köşegen aşağıdakileri oluşturur: sayısal dizi sondaki sıfırlar hariç:
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. Pascal üçgeninin aşağıdaki 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 başka bir ayar yapmanızı sağlar ilginç özellik Pascal üçgeni. 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 çıkıyor.
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 yüzden olağandışı özellikler Pascal üçgenini, tüm yetenekleri listelenemeyen ve abartılması zor olan en mükemmel sayısal sistemlerden biri olarak görmemize izin verin.
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 şeyi çözmek için pratik problemler belirli bir sonlu kümenin elemanlarından elde edilebilecek tüm sabit önem kombinasyonlarının listelenmesi ve sadece bunların sayısının belirlenmesi gerekli değildir. Herhangi bir sonlu kümenin elemanlarının her zaman tamsayı olarak numaralandırılması 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ırlamaya 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 bir sonraki 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 fazla 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 olarak, n öğenin m ile herhangi bir kombinasyonunun sözlüksel sayısı 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 kombinasyon sayısının (1, ... i, ... m) olduğunu 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 yinelemelerde 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 kadar 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: Ayrıca herhangi bir tekrarlı kombinasyon sayısı için pozitif değerler n ve m, 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 çarpımların hesaplanmasında zaman alıcı 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 basamağı, 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çimiyle, birlerin 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 haliyle böyle bir arama uygulanır çeşitli yöntemler bitişik bitlerin kaydırmayla yer değiştirmeleri (transpozitif kaydırma algoritmaları). 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 sona eren 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 yakına kaydırılmasıyla mevcut olandan bir sonraki ikili kombinasyon elde edilir. aktarımdan (kaydırma) sonra elde edilen çift 10. Bu durumda mevcut ikili kombinasyonda ön basamaklarda hiç birim yoksa, o zaman baş birim aktarımdan sonra elde edilse bile kaydırma yapılmaz. bu adım. Aktarma sonrasında 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 toplama biçiminde 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), aşağıdaki toplama formülü kullanılarak tam sayıların eklenmesi işlemleri gerçekleştirilerek her zaman geçerli kombinasyondan (B n,…B j,…B 1) 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: İçin karşılaştırmalı analiz Dikkate alınan sol ve sağ kaydırmalı aktarma algoritmalarının yinelemelerinde oluşturdukları 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ı olarak 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 farklı m adet 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 aralıklar"|" sembollerini yerleştirebilirsiniz ve "" sırasıyla. Ş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 öğ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) tekrarlı kombinasyonlarını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 her birinden sonraki satırdaki sıfırların sayısı i'inci birim ikili kombinasyon, ana kümenin i'inci elemanının tekrarlarla karşılık gelen kombinasyondaki ö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, BBD'nin tekrarları olan bir kombinasyon geri yüklenir; elemanları, alfabetik olarak yazılan ilk beş Latin harfinin oluşturma kümesinden seçilir. alfabetik sıra ve üst çizgi bu kombinasyonda eksik olan öğeleri gösterir: Koşullarda benzer eylemlerin gerçekleştirilmesi bu örnek ile, 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. Kombinatorikte, belirli nesnelerden (elemanlardan) belirli bir türden kaç tane kombinasyonun yapılabileceğiyle ilgili sorular incelenir. Kombinatoriklerin bir dal olarak doğuşu, B. Pascal ve P. Fermat'ın kumar teorisi üzerine çalışmalarıyla ilişkilidir. Kombinatoryal yöntemlerin geliştirilmesine büyük katkı G.V. Leibniz, J. Bernoulli ve L. Euler. Fransız filozof, yazar, matematikçi ve fizikçi Blaise Pascal (1623-1662) olağanüstü çalışmalarını gösterdi. matematik becerileri. Pascal'ın matematiksel ilgi alanları çok çeşitliydi. Pascal bir şeyi kanıtladı Gottfried Wilhelm Leibniz (1646–1716) Alman filozof, matematikçi, fizikçi ve mucit, avukat, tarihçi ve dilbilimciydi. Matematikte I. Newton ile birlikte diferansiyel ve integral hesabını geliştirdi. Önemli Katkı Kombinatoriklere katkıda bulundu. Onun adı özellikle sayı teorisi problemleriyle ilişkilidir. Gottfried Wilhelm Leibniz'in pek etkileyici bir görünümü yoktu ve bu nedenle oldukça sade görünüşlü bir insan izlenimi veriyordu. Bir gün Paris'te tanıdığı bir filozofun kitabını satın almak umuduyla bir kitapçıya gitti. Bir ziyaretçi bu kitabı sorduğunda kitapçı onu tepeden tırnağa inceleyerek alaycı bir şekilde şöyle dedi: “Buna neden ihtiyacın var? Gerçekten bu tür kitapları okuyabiliyor musun?” Bilim adamının cevap vermesine fırsat kalmadan kitabın yazarı şu sözlerle dükkâna girdi: "Büyük Leibniz'e selamlar ve saygılar!" Satıcı, bunun gerçekten de kitapları bilim adamları arasında büyük talep gören ünlü Leibniz olduğunu anlayamadı. Gelecekte aşağıdakiler önemli bir rol oynayacaktır: Lemma. Bir dizi öğeye ve bir dizi öğeye izin verin. Daha sonra tüm farklı çiftlerin sayısı eşit olacaktır. Kanıt. Gerçekten de, bir kümedeki bir öğeyle bu kadar farklı çiftler oluşturabiliriz ve toplamda bir öğe kümesi oluşturabiliriz. Yerleştirmeler, permütasyonlar, kombinasyonlar Üç elemanlı bir kümemiz olsun. Bu unsurlardan ikisini hangi yollarla seçebiliriz? . Tanım. Farklı öğelerden oluşan bir kümenin öğelere göre düzenlenmesi, belirli öğelerden > öğelerden oluşan ve öğelerin kendisinde veya öğelerin sırasında farklılık gösteren kombinasyonlardır. Bir dizi öğenin öğelere göre tüm yerleşimlerinin sayısı ('den) ile gösterilir. ilk harf Fransızca kelime“düzenleme”, yani yerleştirme anlamına gelir), nerede ve . Teorem. Bir dizi öğenin öğelere göre yerleşim sayısı eşittir Kanıt. Diyelim ki elementlerimiz var. Olası yerleşimler olsun. Bu yerleşimleri sırasıyla oluşturacağız. Öncelikle ilk yerleştirme elemanını tanımlayalım. Belirli bir öğe kümesinden seçilebilir çeşitli şekillerde. İlk öğeyi seçtikten sonra, ikinci öğeyi vb. seçmenin hâlâ yolları vardır. Bu tür seçimlerin her biri yeni bir yerleşim sağladığından, tüm bu seçenekler birbiriyle serbestçe birleştirilebilir. Bu nedenle elimizde: Örnek. Bir bayrak üç yatay çizgiden kaç farklı biçimde oluşabilir? çeşitli renkler beş renkli malzeme varsa? Çözüm. Gerekli sayıda üç bantlı bayrak: Tanım. Bir dizi elementin permütasyonu, elementlerin belirli bir sıraya göre düzenlenmesidir. Böylece, üç elemanlı bir kümenin tüm farklı permütasyonları Elementlerin tüm permütasyonlarının sayısı belirtilir (Fransızca "permütasyon" kelimesinin ilk harfinden, "permütasyon", "hareket" anlamına gelir). Bu nedenle hepsinin sayısı çeşitli permütasyonlar formülle hesaplanır Örnek. Kaleler birbirlerine saldırmayacak şekilde satranç tahtasına kaç farklı şekilde yerleştirilebilir? Çözüm. Gerekli sayıda kale Tanım gereği! Tanım. Farklı elementlerin elementlerle kombinasyonları, belirli elementlerin elementlerden oluşan ve en az bir elementte farklılık gösteren (başka bir deyişle, belirli bir element kümesinin -element alt kümeleri) kombinasyonlarıdır. Gördüğünüz gibi kombinasyonlarda yerleşimlerden farklı olarak elemanların sırası dikkate alınmıyor. Her birindeki elementlerin tüm kombinasyonlarının sayısı belirtilir (Fransızca "kombinasyon" kelimesinin ilk harfinden, "kombinasyon" anlamına gelir). Sayılar İkili setin tüm kombinasyonları . Sayıların özellikleri (\sf C)_n^k Gerçekte, belirli bir -elemanlı kümenin her -elemanlı alt kümesi, aynı kümenin bir ve yalnızca bir -elemanlı alt kümesine karşılık gelir. Aslında elemanların alt kümelerini şu şekilde seçebiliriz: bir elemanı sabitleyin; bu öğeyi içeren öğe altkümelerinin sayısı eşittir; bu elemanı içermeyen -element altkümelerinin sayısı eşittir. Pascal üçgeni Bu üçgende her satırdaki ekstrem sayılar 1'e, ekstrem olmayan her sayı ise bir önceki satırın üstündeki iki sayının toplamına eşittir. Böylece bu üçgen sayıları hesaplamanıza olanak sağlar. Teorem. Kanıt. Bir dizi öğeyi ele alalım ve aşağıdaki problemi iki şekilde çözelim: belirli bir öğenin öğelerinden kaç tane dizi oluşturulabilir? 1 yol. Dizinin ilk üyesini, ardından ikinci, üçüncü vb.'yi seçiyoruz. üye Yöntem 2. Önce belirli bir kümeden öğeleri seçelim, sonra bunları belirli bir sıraya göre düzenleyelim. Bu kesrin payını ve paydasını şu şekilde çarpın: Örnek.“Sportloto” oyununda 36 sayıdan 5 tanesini kaç farklı şekilde seçebilirsiniz? Gerekli sayıda yol Görevler. 1.
Araç plakaları Rus alfabesinin 3 harfinden (33 harf) ve 4 rakamdan oluşmaktadır. Kaç farklı plaka numarası var? Bölümler sayıca veya terimlerin sırasına göre farklılık gösteriyorsa farklı kabul edilir. Bir sayının terimlere kaç farklı bölümü vardır? Kombinasyon sayısı Kombinasyon itibaren Nİle k set denir k verilerden seçilen öğeler N unsurlar. 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şu: Tekrarlı kombinasyon sayılarının iki boyutlu üretme fonksiyonu: Wikimedia Vakfı. 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 biçim 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üğü Kombinatorik matematik, kombinatorik, belirli, genellikle sonlu bir kümenin elemanlarının belirli kurallara uygun olarak seçilmesi ve düzenlenmesiyle ilgili problemlerin çözümüne 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. Her ne kadar atıf yapılsa da, bazı olayların gerçekleşmesini beklemenin makul olup olmadığını diğerlerine kıyasla yargılamamıza olanak tanır. sayısal değerler olayların olasılıkları çoğu zaman gereksizdir... ... Collier Ansiklopedisi 1) matematiksel kombinatoryal analizle aynı. 2) Belirli koşullar altında, belirli bir sonlu nesne kümesinden oluşturulabilecek kombinasyon sayısının incelenmesiyle ilgili temel matematiğin bir bölümü... ... Büyük Sovyet ansiklopedisi
- (Yunan paradoksları 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), bir kombinasyonun gücünü belirlemenizi sağlayan kombinatoryal bir formül sonlu sayı Genel olarak birbirleriyle kesişebilen sonlu kümeler ... 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. Brockhaus ve I.A. Efron Numeroloji en eski ezoterik sistemlerden biridir. Oluşma zamanını doğru bir şekilde belirlemek imkansızdır. Ancak… Bu makalede konuşacağız Kombinatorik adı verilen matematiğin özel bir dalı hakkında. Formüller, kurallar, problem çözme örnekleri - tüm bunları burada makaleyi sonuna kadar okuyarak bulabilirsiniz. Peki nedir bu bölüm? Kombinatorik herhangi bir nesneyi sayma meselesiyle ilgilenir. Ama içinde bu durumda Kombinatoryal konfigürasyonlar Kombinatoriklerin temel kavramları ve formülleri konusunu göz önüne aldığımızda, kombinatoryal konfigürasyonlara dikkat etmeden duramayız. Sadece formüle etmek için değil aynı zamanda çözmek için de kullanılırlar.çeşitli örnekler bir sayıyı bölmek. İlk üçünden daha sonra detaylı olarak bahsedeceğiz ancak kompozisyon ve bölümlemeye dikkat edeceğiz. bu bölüm . Belirli bir sayının (örneğin a) bileşiminden bahsettiklerinde, a sayısının belirli sayıların sıralı toplamı biçiminde temsilini kastediyorlar. pozitif sayılar Bölümler sonsuz. İlk durumda Matematik kombinatorikleri ile ilgili problemler, kümelerin elemanları tarafından oluşturulan farklı konfigürasyonların numaralandırılmasını veya sayılmasını içerir. Kural olarak bu kümelere bazı kısıtlamalar (ayırt edicilik, ayırt edilemezlik, tekrarlanma ihtimali vb.) getirilmektedir. Ve bu konfigürasyonların sayısı, biraz sonra konuşacağımız toplama veya çarpma kuralları kullanılarak hesaplanır. Yapısal kombinatorik, grafik ve matroid teorilerini içerir. Ekstremal kombinatorik problemine bir örnek, aşağıdaki özellikleri sağlayan bir grafiğin en büyük boyutunun ne olduğudur... Dördüncü paragrafta, varlığı rastgele konfigürasyonlarda inceleyen Ramsey teorisinden bahsetmiştik. düzenli yapılar. Olasılıksal kombinatorik şu soruyu cevaplayabilir: belirli bir kümenin olasılığı nedir? belirli özellik. Tahmin edebileceğiniz gibi, topolojik kombinatorik Topolojideki yöntemleri uygular. Ve son olarak, yedinci nokta - sonsuz kombinatorik, kombinatorik yöntemlerin sonsuz kümelere uygulanmasını inceler. Kombinatorik formüller arasında uzun zamandır aşina olduğumuz oldukça basit olanları bulabilirsiniz. Bir örnek toplam kuralıdır. Bize iki eylemin (C ve E) verildiğini, eğer bunlar birbirini dışlıyorsa, C eylemi birkaç yolla (örneğin a) gerçekleştirilebilir ve E eylemi b-yollarında gerçekleştirilebilir, o zaman bunlardan herhangi biri ( C veya E) a+b yollarıyla gerçekleştirilebilir. Teorik olarak bunu anlamak oldukça zordur; basit bir örnek kullanarak tüm konuyu aktarmaya çalışacağız. Bir sınıftaki ortalama öğrenci sayısını alalım; diyelim ki yirmi beş. Bunların arasında on beş kız ve on erkek var. Her sınıfa her gün bir görevli atanmaktadır. Bugün sınıf gözetmeni atamanın kaç yolu var? Sorunun çözümü oldukça basit; toplama kuralına başvuracağız. Sorunun metni sadece erkeklerin veya sadece kızların görevde olabileceğini söylemiyor. Bu nedenle on beş kızdan herhangi biri ya da on erkekten herhangi biri olabilir. Toplama kuralını uyguladığımızda bir okul çocuğunun kolayca halledebileceği oldukça basit bir örnek elde ederiz. birincil sınıflar: 15 + 10. Saydıktan sonra cevabı alıyoruz: yirmi beş. Yani bugün için bir sınıfı görevlendirmenin yalnızca yirmi beş yolu vardır. Kombinatoriklerin temel formülleri aynı zamanda çarpma kuralını da içerir. Teoriyle başlayalım. Diyelim ki birkaç eylem gerçekleştirmemiz gerekiyor: ilk eylem 1 şekilde, ikincisi 2 şekilde, üçüncüsü 3 şekilde gerçekleştirilir ve bu şekilde devam eder. son eylem, aynı şekillerde gerçekleştirilir. O zaman tüm bu eylemler (toplamına sahip olduğumuz) N şekilde gerçekleştirilebilir. Bilinmeyen N nasıl hesaplanır? Formül bu konuda bize yardımcı olacaktır: N = c1 * c2 * c3 *…* ca. Yine teoride hiçbir şey net değil, hadi değerlendirmeye geçelim basit örnekçarpma kuralını uygulamak için. On beş kız ve on erkek çocuğun bulunduğu yirmi beş kişilik aynı sınıfı ele alalım. Ancak bu sefer görev için iki kişiyi seçmemiz gerekiyor. Sadece erkek ya da kız olabilirler ya da bir erkek ve bir kız olabilirler. Sorunun temel çözümüne geçelim. Son paragrafta kararlaştırdığımız gibi, ilk görevdeki kişiyi seçiyoruz, elimizde yirmi beş olası seçenek var. Görevli ikinci kişi kalan kişilerden herhangi biri olabilir. Yirmi beş öğrencimiz vardı, birini seçmiştik, yani ikinci görevli geri kalan yirmi dört kişiden herhangi biri olabilirdi. Son olarak çarpma kuralını uyguluyoruz ve görevdeki iki memurun altı yüz farklı şekilde seçilebildiğini görüyoruz. Bu sayıyı yirmi beş ile yirmi dördü çarparak elde ettik. Şimdi başka bir kombinatorik formülüne bakacağız. Yazının bu bölümünde permütasyonlardan bahsedeceğiz. Bir örnek kullanarak sorunu hemen ele almayı öneriyoruz. Bilardo toplarını alalım, elimizde n'inci sayıda var. Bunları arka arkaya düzenlemek yani sıralı bir küme oluşturmak için kaç seçenek olduğunu saymamız gerekiyor. Hadi başlayalım, eğer toplarımız yoksa yerleştirme seçeneğimiz de sıfırdır. Ve eğer bir topumuz varsa, o zaman düzenleme de aynıdır (matematiksel olarak bu şu şekilde yazılabilir: P1 = 1). İki top iki farklı şekilde yerleştirilebilir: 1,2 ve 2,1. Bu nedenle P2 = 2. Üç top altı şekilde düzenlenebilir (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Peki ya böyle üç top değil de on ya da on beş top varsa? Her şeyi listeleyin olası seçeneklerçok uzun bir süre sonra kombinatorik yardımımıza gelir. Permütasyon formülü bizi ilgilendiren sorunun cevabını bulmamıza yardımcı olacaktır. Pn = n *P (n-1). Formülü basitleştirmeye çalışırsak şunu elde ederiz: Pn = n* (n - 1) *…* 2 * 1. Ve bu, ilk doğal sayıların çarpımıdır. Bu sayıya faktöriyel denir ve n! Sorunu ele alalım. Danışman her sabah ekibini (yirmi kişi) sıraya koyar. Kadroda üç kişi var en iyi arkadaş- Kostya, Sasha ve Lesha. Yan yana durma olasılıkları nedir? Sorunun cevabını bulmak için "iyi" bir sonuç olasılığını toplam sonuç sayısına bölmeniz gerekir. Toplam permütasyon sayısı 20'dir! = 2,5 kentilyon. “İyi” sonuçların sayısı nasıl sayılır? Kostya, Sasha ve Lesha'nın bir süpermen olduğunu varsayalım. O halde yalnızca on sekiz konumuz var. Bu durumda permütasyon sayısı 18 = 6,5 katrilyondur. Bütün bunlarla birlikte Kostya, Sasha ve Lesha, bölünmez üçlüsü halinde kendi aralarında keyfi olarak hareket edebilirler ve bu 3 tane daha! = 6 seçenek. Bu, toplamda 18 "iyi" düzenlememiz olduğu anlamına geliyor! * 3! Tek yapmamız gereken istenen olasılığı bulmak: (18! * 3!) / 20! Bu yaklaşık olarak 0,016'ya eşittir. Yüzdeye çevrildiğinde ise sadece %1,6 çıkıyor. Şimdi çok önemli ve gerekli başka bir kombinatorik formüle bakacağız. Yerleştirme, sizi makalenin bu bölümünde değerlendirmeye davet ettiğimiz bir sonraki konumuzdur. Komplikasyonlara gidiyoruz. Varsayalım ki tüm kümeden (n) değil, daha küçük bir kümeden (m) olası permütasyonları dikkate almak istiyoruz. Yani, n öğenin m'ye göre permütasyonlarını düşünüyoruz. Kombinatoriklerin temel formülleri yalnızca ezberlenmemeli, aynı zamanda anlaşılmalıdır. Her ne kadar daha karmaşık hale gelseler de elimizde bir değil iki parametre var. Diyelim ki m = 1, sonra A = 1, m = 2, sonra A = n * (n - 1). Formülü daha da basitleştirirsek ve faktöriyelleri kullanarak gösterime geçersek, tamamen kısa ve öz bir formül elde ederiz: A = n! / (n - m)! Temel kombinatorik formüllerin neredeyse tamamını örneklerle inceledik. Şimdi temel kombinatorik dersini düşünmenin son aşamasına geçelim - kombinasyonları tanıma. Şimdi elimizdeki n taneden m tanesini seçeceğiz ve herkesi seçeceğiz olası yollar. Peki bunun yerleştirmeden farkı nedir? Siparişi dikkate almayacağız. Bu sırasız set bir kombinasyon olacaktır. Hemen C notasyonunu tanıtalım. n'den m topun yerleşimini alıyoruz. Sıralamaya dikkat etmekten vazgeçip tekrarlanan kombinasyonlarla karşı karşıya kalırız. Kombinasyon sayısını elde etmek için yerleşim sayısını m'ye bölmemiz gerekir! (m faktöriyel). Yani C = A/m! Bu nedenle, n top arasından seçim yapmanın yalnızca birkaç yolu vardır ve bu da neredeyse tümünü seçme yollarının sayısına yaklaşık olarak eşittir. Bu var mantıksal ifade: Biraz seçmek neredeyse her şeyi atmak anlamına gelir. Bu noktada şunu da belirtmekte fayda var. maksimum sayıöğelerin yarısını seçmeye çalışarak kombinasyonlar elde edilebilir. Kombinatoriklerin temel formüllerini ayrıntılı olarak inceledik: yerleştirme, permütasyon ve kombinasyon. Şimdi görevimiz seçimi kolaylaştırmak gerekli formül Bir kombinatorik problemini çözmek için. Aşağıdaki oldukça basit şemayı kullanabilirsiniz: Kombinatorik unsurlarına, formüllere ve diğer bazı konulara baktık. Şimdi asıl soruna geçelim. Önünüzde bir kivi, bir portakal ve bir muz olduğunu hayal edin. Birinci soru: Kaç farklı şekilde yeniden düzenlenebilirler? Bunu yapmak için permütasyon formülünü kullanacağız: P = 3! = 6 yol. İkinci soru: Bir meyveyi kaç farklı şekilde seçebilirsiniz? Bu çok açık, sadece üç seçeneğimiz var; kivi, portakal veya muzu seçin, ama gelin kombinasyon formülünü uygulayalım: C = 3! / (2! * 1!) = 3. Üçüncü soru: İki meyveyi kaç farklı şekilde seçebilirsiniz? Hangi seçeneklere sahibiz? Kivi ve portakal; kivi ve muz; portakal ve muz. Yani üç seçenek var, ancak bunu kombinasyon formülünü kullanarak kontrol etmek kolaydır: C = 3! / (1! * 2!) = 3 Dördüncü soru: Üç meyveyi kaç farklı şekilde seçebilirsiniz? Gördüğünüz gibi üç meyveyi seçmenin tek bir yolu var: kivi, portakal ve muz alın. C = 3! / (0! * 3!) = 1. Beşinci soru: En az bir meyveyi kaç farklı şekilde seçebilirsiniz? Bu durum meyvelerden birini, ikisini veya üçünü birden alabileceğimiz anlamına gelir. Bu nedenle C1 + C2 + C3 = 3 + 3 + 1 = 7'yi ekliyoruz. Yani sofradan en az bir meyve almanın yedi yolu var. MS EXCEL'de n öğenin kombinasyon sayısını k'ya kadar sayalım. Formülleri kullanarak, tüm kombinasyon seçeneklerini sayfada görüntülüyoruz ( İngilizce çeviri terim: Tekrarı olmayan kombinasyonlar). K elementin n farklı elementinden oluşan kombinasyonlar, en az bir elementte farklılık gösteren kombinasyonlardır. Örneğin, aşağıda 5 elementten (1; 2; 3; 4; 5) oluşan bir kümeden alınan TÜM 3 elementli kombinasyonlar verilmiştir: (1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5) Not: Bu, MS EXCEL kullanarak kombinasyon sayısını saymayla ilgili bir makaledir. Teorik temellerÖzel bir ders kitabında okumanızı öneririz. Bu makaleden kombinasyonları öğrenmek kötü bir fikir. Örnek dosyada, verilen n ve k için tüm Kombinasyonları görüntüleyecek formüller oluşturulmuştur. Kümenin eleman sayısını (n) ve ondan seçtiğimiz eleman sayısını (k) belirterek formülleri kullanarak tüm Kombinasyonları görüntüleyebiliriz. Bir araba taşıyıcı 4 araba taşıyabilir. 7 farklı arabanın (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus) taşınması gerekiyor. Birinci araba taşıyıcısı kaç farklı şekilde doldurulabilir? Arabanın araba taşıyıcısındaki spesifik yeri önemli değildir. Sayıyı belirlememiz gerekiyor Kombinasyonlar Bir araba taşıyıcısının 4 yerinde 7 araba. Onlar. n=7 ve k=4. Bu tür 35 seçeneğin olduğu ortaya çıktı =NUMCOMB(7,4).
Projektif geometrinin temel teoremlerinden (Pascal teoremi), bir toplama makinesi tasarladı (Pascal'ın toplama makinesi), binom katsayılarını (Pascal üçgeni) hesaplamak için bir yöntem verdi ve kanıtlama yöntemini doğru bir şekilde tanımlayan ve uygulayan ilk kişi oldu. matematiksel tümevarım, sonsuz küçük analizin geliştirilmesinde önemli bir adım attı, oynadı önemli rol Olasılık teorisinin kökenlerinde. Hidrostatikte Pascal, temel yasasını (Pascal yasası) oluşturdu. Pascal'ın "Bir Taşraya Mektuplar"ı Fransız klasik düzyazısının başyapıtıydı.
Her birinde hiçbir öğenin iki kez bulunmadığı kümeler var mı?
2.
Piyanoda 88 tuş bulunmaktadır. 6 sesi art arda kaç farklı şekilde üretebilirsiniz?
3.
5'e bölünebilen altı basamaklı kaç sayı vardır?
4.
7 farklı madeni para üç cebe kaç farklı şekilde yerleştirilebilir?
5.
Ondalık gösteriminde en az bir kez 5 rakamı bulunan kaç tane beş basamaklı sayı yapabilirsiniz?
6.
20 kişi kaç farklı şekilde oturabilir? yuvarlak masa Bir daire içinde hareket ederek birbirlerinden elde edilebiliyorsa, yöntemlerin aynı olduğunu mu düşünüyorsunuz?
7.
5'e bölünebilen ve rakamları aynı olmayan kaç tane beş basamaklı sayı vardır?
8.
Açık kareli kağıt hücre kenarı 1 cm olacak şekilde hücrelerin üst kısımlarından geçmeyen ve hücrelerin kenarlarına değmeyen 100 cm yarıçaplı bir daire çizilir. Bu daire kaç hücreyle kesişebilir?
9.
Sayılar bitişik ve artan sırada olacak şekilde kaç farklı şekilde sıralanabilir?
10.
Her rakam yalnızca bir kez kullanılabilen rakamlardan kaç tane beş basamaklı sayı oluşturulabilir?
11.
ROT kelimesinden harfleri yeniden düzenleyerek şu kelimeleri elde edebilirsiniz: TOP, ORT, OTR, TRO, RTO. Bunlara anagram denir. LOGARITHM kelimesinden kaç tane anagram yapabilirsiniz?
12.
hadi arayalım bölme doğal sayı, doğal sayıların toplamı olarak gösterimi. Örneğin burada bir sayının tüm bölümleri verilmiştir:
13.
Kaç tane var üç basamaklı sayılar artmayan basamak sırası ile?
14.
Rakamları artmayan dört basamaklı kaç sayı vardır?
15.
17 kişi yan yana olacak şekilde kaç farklı şekilde sıralanabilir?
16.
kızlar ve erkekler rastgele bir sıra koltukta oturuyorlar. İki kız yan yana oturmamak şartıyla kaç farklı şekilde oturabilirler?
17.
kızlar ve erkekler rastgele bir sıra koltukta oturuyorlar. Bütün kızlar yan yana oturacak şekilde kaç farklı şekilde oturabilirler?Açık formüller
Bağlantılar
2010.
Kitaplar
nesneler erik, armut veya elma değil, başka bir şeydir. Kombinatorik bir olayın olasılığını bulmamıza yardımcı olur. Örneğin, kart oynarken rakibin koz sahibi olma olasılığı nedir? Veya şu örnek: Yirmi bilyeden oluşan bir torbadan beyaz bir bilye çıkma olasılığı nedir? Bu tür problemler için en azından matematiğin bu dalının temellerini bilmemiz gerekir.
. Ve bir bölüm sıralanmamış bir toplamdır.
Ekleme kuralı
Çarpma kuralı
Yeniden düzenleme
Konaklama
Kombinasyon
Bir sorunu çözmek için bir formül nasıl seçilir?
Örnek
Kombinasyonlar ve Yerleştirmeler Arasındaki Fark
Kombinasyonların tüm kombinasyonları görüntüleniyor
Görev