Çift sayım kanıtı
Olarak kombinatoryal matematik , bir çift sayımı ile izolasyon veya çift sayma ya da çift sayma , a, birleştirici geçirmez tekniği iki ifade elemanlarının sayısının sayılması için iki yol vardır kanıtlayarak eşittir 'aynı d kanıtlamak için kullanılan bir dizi . Van Lint ve Wilson bu tekniği "kombinatorikteki en önemli araçlardan biri" olarak tanımlar.
Özel durum: Kartezyen bir ürünün parçasının numaralandırılması
Prensip
İki sonlu kümeler olsun ve ve bir alt kümesi arasında ; ait olduğu her seferinde , bunu söylüyoruz ve olaylardır.
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}G{\ displaystyle {\ mathcal {G}}}E×F{\ displaystyle {\ mathcal {E}} \ times {\ mathcal {F}}}(x,y){\ displaystyle (x, y)}G{\ displaystyle {\ mathcal {G}}}x{\ displaystyle x}y{\ displaystyle y}
Not a grafik olarak görülmektedir ikili ilişki içinde solucan , bu durumda "olarak, ve yazılır olaylar" ya da bir şekilde bipartit grafik .
G{\ displaystyle {\ mathcal {G}}} R{\ displaystyle R}E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}x{\ displaystyle x}y{\ displaystyle y}xRy{\ displaystyle xRy}
Eğer işaret etmektedir elemanlarının sayısı olaydan ve bu elemanları için olay , o zaman bilinen formüle sahip çift sayma veya sayma dilimleri (veya yığın olarak) :
değil+(x){\ displaystyle n ^ {+} (x)}y{\ displaystyle y}x{\ displaystyle x}değil-(y){\ displaystyle n ^ {-} (y)}x{\ displaystyle x}y{\ displaystyle y}
∑x∈Edeğil+(x)=∑y∈Fdeğil-(y)=|G|=kart G{\ displaystyle \ toplamı _ {x \ E içinde} n ^ {+} (x) = \ toplamı _ {y \ F} n ^ {-} (y) = \ sol \ vert {\ mathcal {G}} \ right \ vert = {\ text {kart}} {\ mathcal {G}}}.
İlginç bir özel durum, nerede ve sabit olduğudur; formül daha sonra yazılır .
değil+{\ displaystyle n ^ {+}}değil-{\ displaystyle n ^ {-}}değil+.|E|=değil-.|F|{\ displaystyle n ^ {+}. \ sol \ vert {\ mathcal {E}} \ sağ \ vert = n ^ {-}. \ sol \ vert {\ mathcal {F}} \ sağ \ vert}
Sagital diyagram çizimi
Çifte sayma formülü bu diyagramda ok sayısının hem gidiş hem de geliş sayılarına eşit olmasıyla yorumlanmıştır.
İnsidans matrisi çizimi
Biz tanımlarsak insidansı matrisi grafik ya da ilişkinin göre eğer ait , aksi halde, bir matris açısından toplamı olduğu çift sayısı formül aracı veya sütunları toplanmasıyla sıraları ile satır toplanmasıyla ile elde edilen. Gerçekten de sayısıdır bulunan satır ile bağlantılı ve sayısı bulunan sütun ile ilişkili .
AT{\ displaystyle A}G{\ displaystyle {\ mathcal {G}}}R{\ displaystyle R}AT(x,y)=1{\ displaystyle A (x, y) = 1}(x,y){\ displaystyle (x, y)}G{\ displaystyle {\ mathcal {G}}}AT(x,y)=0{\ displaystyle A (x, y) = 0}AT{\ displaystyle A}değil+(x){\ displaystyle n ^ {+} (x)}1{\ displaystyle 1}x{\ displaystyle x}değil-(y){\ displaystyle n ^ {-} (y)}1{\ displaystyle 1}y{\ displaystyle y}
Karşıdaki örnekte, insidans matrisi şeklindedir .
AT=(αβγδ-de1000b1100vs0011d0100e1001){\ displaystyle A = {\ begin {pmatrix} & \ alpha & \ beta & \ gamma & \ delta \\ a & 1 & 0 & 0 & 0 \\ b & 1 & 1 & 0 & 0 \\ c & 0 & 0 & 1 & 1 \\ d & 0 & 1 & 0 & 0 \\ e & 1 & 0 & 0 & 1 \ end {pmatrix}}}
Bu anlamda, çift sayma formülü formül özel bir durumudur inversiyon toplamıdır işaretleri : .
∑(ben,j)∈ben×J-deben,j=∑ben∈ben∑j∈J-deben,j=∑j∈J∑ben∈ben-deben,j{\ displaystyle \ sum _ {(i, j) \ in I \ times J} a_ {i, j} = \ sum _ {i \ in I} \ sum _ {j \ in J} a_ {i, j} = \ sum _ {j \ in J} \ sum _ {i \ in I} a_ {i, j}}
Uygulama örnekleri
Asal tam sayıların toplamıdeğil{\ displaystyle n}
Burada, kümeler ve 1 ila tamsayılar kümesine eşittir ve iki tamsayılar ve olay eğer vardır .
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}değil{\ displaystyle n}ben{\ displaystyle i}j{\ displaystyle j}ben⩽j{\ displaystyle i \ leqslant j}
Öyleyse vedeğil+(ben)=değil+1-ben{\ displaystyle n ^ {+} (i) = n + 1-i}değil-(ben)=ben{\ displaystyle n ^ {-} (i) = i}
Daha sonra , klasik formülü çıkardığımız çift sayma formülü yazılır .
∑ben=1değil(değil+1-ben)=∑ben=1değilben{\ displaystyle \ toplamı _ {i = 1} ^ {n} (n + 1-i) = \ toplam _ {i = 1} ^ {n} i}∑ben=1değilben=değil(değil+1)2{\ displaystyle \ toplamı _ {i = 1} ^ {n} i = {n (n + 1) \ üzeri {2}}}
Ortalama bölücü sayısı
Aynı setleri ve ancak ve eğer olaylar vardır bölünmüş .
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}ben{\ displaystyle i}j{\ displaystyle j}ben{\ displaystyle i} j{\ displaystyle j}
Daha sonra birçok sayısı için eşit ya da daha az olan, burada tamsayı kısmını temsil eder, ve sayısı arasında Bölen .
değil+(ben){\ displaystyle n ^ {+} (i)}ben{\ displaystyle i}değil{\ displaystyle n}⌊değilben⌋{\ displaystyle \ sol \ kat {\ frac {n} {i}} \ sağ \ rfloor}⌊.⌋{\ displaystyle \ sol \ kat. \ sağ \ rfloor}değil-(ben){\ displaystyle n ^ {-} (i)}d(ben){\ displaystyle d (i)}ben{\ displaystyle i}
Çift sayma formülü daha sonra yazılır ; Bunu kolayca çıkarabiliriz ( harmonik seriler ) ve 1 ile arasındaki bir sayının ortalama bölen sayısının eşit olduğunu anlıyoruz .
∑ben=1değild(ben)=∑ben=1değil⌊değilben⌋{\ displaystyle \ toplamı _ {i = 1} ^ {n} d (i) = \ toplamı _ {i = 1} ^ {n} \ sol \ lfloor {\ frac {n} {i}} \ sağ \ rfloor }1değil∑ben=1değild(ben)∼∑ben=1değil1ben=Hdeğil{\ displaystyle {1 \ over n} \ sum _ {i = 1} ^ {n} d (i) \ sim \ sum _ {i = 1} ^ {n} {1 \ over i} = H_ {n} }Hdeğil∼lndeğil{\ displaystyle H_ {n} \ sim \ ln n}değil{\ displaystyle n}lndeğil{\ displaystyle \ ln n}
Bir grafiğin köşelerinin derecelerinin toplamı
Burada, resim , bir köşe setidir grafik , kenarlarından grubu ve sıklığı ilişkisi bu köşeler ve kenarlar arasındaki adjacency taşımaktadır. Bir zirve için , derecesi olarak tefsir edilir ve bir kenar , ; çift sayma formülü daha sonra grafiğin kenar sayısı nerede yazılır . El sıkışmalarının lemmasını oluşturan tek dereceli köşe sayısının çift olduğunu anlıyoruz .
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}s{\ displaystyle s}değil+(s){\ displaystyle n ^ {+} (s)}s{\ displaystyle s}-de{\ displaystyle a}değil-(-de)=2{\ displaystyle n ^ {-} (a) = 2}∑derece(s)=2AT{\ displaystyle \ toplamı \ operatöradı {deg} (s) = 2A}AT{\ displaystyle A}
Biz de bir o, örneğin, anlamak polyhedron bütün çıkıntılar hangi derecesi vardır , köşe sayısıdır.
değil{\ displaystyle n}değilS=2AT{\ displaystyle nS = 2A}S{\ displaystyle S}
Aynı şekilde, tüm yüzlerin kenarlara sahip olduğu bir çokyüzlüde , yüzlerin sayısı burada .
p{\ displaystyle p}pF=2AT{\ displaystyle pF = 2A}F{\ displaystyle F}
Binom katsayıları üzerindeki formül
Burada küme , bir dizi öğenin öğelerinin parçalarının ve öğelerin parçalarının kümesidir ; iki parça olduğu ve ayrık olmaları halinde tesadüfi olduğu hükme bağlanmıştır .
E{\ displaystyle {\ mathcal {E}}}p{\ displaystyle p}değil{\ displaystyle n}F{\ displaystyle {\ mathcal {F}}}q{\ displaystyle q}AT{\ displaystyle A}B{\ displaystyle B}
Grafiğin eleman sayısıdır değer (seçimi , daha sonra seçimi olarak ). Şimdi burada , sayısı hangi bir kopukluklar , bir ve bir değer . Çift sayma formülü daha sonra yazılır:
G{\ displaystyle {\ mathcal {G}}}(değilp+q)(p+qp){\ displaystyle {\ binom {n} {p + q}} {\ binom {p + q} {p}}}AT∪B{\ displaystyle A \ fincan B}AT{\ displaystyle A}AT∪B{\ displaystyle A \ fincan B}değil+(AT){\ displaystyle n ^ {+} (A)}B{\ displaystyle B}AT{\ displaystyle A}(değil-pq){\ displaystyle {\ binom {np} {q}}}değil-(B){\ displaystyle n ^ {-} (B)}(değil-qp){\ displaystyle {\ binom {nq} {p}}}
(değilp)(değil-pq)=(değilq)(değil-qp)=(değilp+q)(p+qp){\ displaystyle {\ binom {n} {p}} {\ binom {np} {q}} = {\ binom {n} {q}} {\ binom {nq} {p}} = {\ binom {n } {p + q}} {\ binom {p + q} {p}}}.
Örneğin, yaparak , biz elde değiştirerek, hangi, için önemli verir piyon formülünü :
q=1{\ displaystyle q = 1}(değil-p)(değilp)=değil(değil-1p)=(p+1)(değilp+1){\ displaystyle (np) {\ binom {n} {p}} = n {\ binom {n-1} {p}} = (p + 1) {\ binom {n} {p + 1}}}p{\ displaystyle p}p-1{\ displaystyle p-1}
(değilp)=değilp(değil-1p-1){\ displaystyle {\ binom {n} {p}} = {n \ p} {\ binom {n-1} {p-1}}} üzerinden.
Diğer örnekler
Pascal üçgeninin bir çizgisinin toplamı
N elemanlı bir kümenin parça sayısını bulalım .
Birinci yöntem : Her öğe için iki olasılık vardır: ya oyunda ya da değil. Bu nedenle, toplam parça var.
2×2×...×2(değil zaman)=2değil{\ displaystyle 2 \ times 2 \ times \ ldots \ times 2 \, (n {\ mbox {times}}) = 2 ^ {n}}
İkinci yöntem : Bir parçadaki elemanların sayısı, 0 ile . Elemanların parçalarının sayısı iki terimli katsayıdır , dolayısıyla parça sayısıdır .
p{\ displaystyle p}değil{\ displaystyle n}p{\ displaystyle p} (değilp){\ displaystyle {\ binom {n} {p}}}∑p=0değil(değilp){\ displaystyle \ toplam _ {p = 0} ^ {n} {\ binom {n} {p}}}
İki ifadenin eşitlenmesi şunu verir:
∑p=0değil(değilp)=2değil{\ displaystyle \ toplam _ {p = 0} ^ {n} {\ binom {n} {p}} = 2 ^ {n}}
Fermat'ın küçük teoremi
Fermat'ın küçük teoremi "eğer devletler asal sayıdır ve eğer herhangi bir tamsayı, daha sonra katları ." Örneğin :
p{\ displaystyle p}-de{\ displaystyle a}-dep--de{\ displaystyle a ^ {p} -a}p{\ displaystyle p}
4 3 - 4 = 60, 3'e bölünebilir.
Izin vermek bir asal sayı ve bir tam sayı. Sembollerden oluşan bir alfabe düşünün . En az iki farklı sembolün bulunduğu uzunluktaki kelimeleri sayalım .
p{\ displaystyle p}-de{\ displaystyle a}-de{\ displaystyle a}değil{\ displaystyle n}p{\ displaystyle p}
Birinci yöntem : Alfabede, bir ve aynı sembolden oluşan kelimelerin çıkarılması gereken herhangi bir uzunlukta kelime vardır :
-dep{\ displaystyle a ^ {p}}p{\ displaystyle p}-de{\ displaystyle a}
değil=-dep--de{\ displaystyle n = a ^ {p} -a}
İkinci yöntem : Bu kelimeler, birbirlerinden dairesel permütasyonla çıkarılabilen kelime grupları halinde gruplandırılabilir . Bu setlere kolye adı verilir (resim) . Örneğin, alfabe ise ve biz üç harf, üç kelimelik kelime düşünülürse , ve aynı yaka içindedir.
{AT,B,VS,D}{\ displaystyle \ {A, B, C, D \}}ATBD{\ displaystyle ABD}BDAT{\ displaystyle BDA}DATB{\ displaystyle DAB}
Her kolyede sembol kelimeler vardır . Aslında, permütasyonların her biri farklı bir kelime verir, çünkü asaldır. Asal olmasaydı durum böyle olmazdı, örneğin kolyede 4 sembolden oluşan sadece 2 farklı kelime var . Böylece sahibiz :
p{\ displaystyle p}p{\ displaystyle p}p{\ displaystyle p}p{\ displaystyle p}p{\ displaystyle p}ATBATB{\ displaystyle ABAB}
değil=p.(kolye sayısı){\ displaystyle n = p. {\ text {(kolye sayısı)}}}İçin bu iki ifade arasındaki eşitliği yazarak, bunun ile bölünebilir olduğunu buluyoruz .
değil{\ displaystyle n}değil=-dep--de{\ displaystyle n = a ^ {p} -a}p{\ displaystyle p}
Renkli ağaçların numaralandırılması
Numarası nedir ait ağaçların bir dizi kapsayabilir farklı renk , farklı yüksekliklerde? Cayley formülü cevap verir:
VSdeğil{\ displaystyle C_ {n}}değil{\ displaystyle n}
VSdeğil=değildeğil-2{\ displaystyle C_ {n} = n ^ {n-2}}.
Aigner ve Ziegler, bu sonucun dört farklı ispatını listeliyor. Dördünden, Jim Pitman'a borçlu olduğumuz şeyin, "en güzeli" olan çifte sayma ile gösteri olduğunu iddia ediyorlar .
Bu gösterimde, bir ağaç oluşturmak için n köşeli bir boş grafiğe (kenarsız) eklenebilecek farklı yönlendirilmiş kenar serilerini iki şekilde sıraladık .
İlk yöntem : yönelimli olmayan olası ağaçlardan birinden başlıyoruz ve yönlendirilmiş bir ağaç veren yönlendirilmiş ağacın kökü olarak n köşesinden birini seçiyoruz . Orada o zaman, birinci kenarı almayı yollar vb sonraki kenar seçmek ve yollarını. Son olarak, bu şekilde oluşturulabilecek toplam dizi sayısı:
VSdeğil{\ displaystyle C_ {n}}değil-1{\ displaystyle n-1}değil-2{\ displaystyle n-2}
VSdeğildeğil!{\ displaystyle C_ {n} n!}.
İkinci yöntem : Her adımda mevcut olan seçeneklerin sayısını göz önünde bulundurarak kenarları boş grafiğe birer birer ekleriz. K yönelimli ağaçlardan oluşan bir orman oluşturmak için zaten bir kenar koleksiyonu eklediysek (resim) , eklenecek bir sonraki kenar için bir seçenek vardır . Aslında, başlangıç köşesi grafiğin n köşesinden herhangi biri olabilir ve bitiş köşesi , başlangıç köşesini içeren ağacın kökü dışındaki köklerden herhangi biri olabilir (resim) . Son olarak, birinci adımdaki, ikinci adımdaki vb. Seçeneklerin sayısını çarparak, toplam seçenek sayısı:
değil-k{\ displaystyle nk}değil(k-1){\ displaystyle n (k-1)}k-1{\ displaystyle k-1}
∏k=2değildeğil(k-1)=değildeğil-1(değil-1)!=değildeğil-2değil!{\ displaystyle \ prod _ {k = 2} ^ {n} n (k-1) = n ^ {n-1} (n-1)! = n ^ {n-2} n!}.
Kenar dizilerinin sayısı için bu iki ifade arasındaki eşitliği yazarak,
VSdeğildeğil!=değildeğil-2değil!{\ displaystyle C_ {n} n! = n ^ {n-2} n!},
Cayley'in formülünü alıyoruz:
VSdeğil=değildeğil-2{\ displaystyle C_ {n} = n ^ {n-2}}.
Diğer örnekler
Notlar ve referanslar
- Bu makale, kısmen veya tamamen , iki nicelik arasındaki eşitliği sağlamak için bir eşlemeyle birbirine bağlanmış iki grubu ayrı ayrı saydığımız "İki hedefli kanıt " başlıklı makaleden alınmıştır (yazarların listesine bakınız ) .
-
(in) Jacobus H. van Lint ve Richard M. Wilson , Kombinatorikte Bir Kurs , Cambridge University Press ,2001, 602 s. ( ISBN 978-0-521-00601-9 , çevrimiçi okuyun ) , s. 4, s. 4 “ Kombinasyondaki önemli araçlardan biri, belirli nesneleri iki farklı şekilde sayma yöntemidir ”.
-
Martin Aigner ve Günter M. Ziegler , Divine Reasonings , Springer-Verlag ,2013, s. 186.
-
Martin Aigner ve Günter M. Ziegler , Divine Reasonings , Springer-Verlag ,2013, s. 187.
-
(in) Martin Aigner ve Günter M. , Ziegler , The Book kanıtlar, , Springer-Verlag ,1998, s. 145-146.
-
Martin Aigner ve Günter M. Ziegler , Divine Reasonings , Springer-Verlag ,2013, s. 229-230.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">