Kettős számlálás
A kombinatorikus matematika , a bizonyítás kettős számlálás , vagy kettős számlálás , vagy akár kettős számlálás , egy kombinatorikus bizonyítéka technikát használják annak bizonyítására, hogy két kifejezés egyenlő, bizonyítva, hogy kétféle módon számítva a elemeinek számát d „ugyanazon szett . Van Lint és Wilson ezt a technikát "a kombinatorika egyik legfontosabb eszközének" írja le.
Különleges eset: egy derékszögű termék egy részének felsorolása
Elv
Hagy két véges halmazok és , és egy részét a ; minden alkalommal, amikor ez tartozik , ezt mondjuk, és incidensek vagyunk.
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}G{\ displaystyle {\ mathcal {G}}}E×F{\ displaystyle {\ mathcal {E}} \ szorzat {\ mathcal {F}}}(x,y){\ displaystyle (x, y)}G{\ displaystyle {\ mathcal {G}}}x{\ displaystyle x}y{\ displaystyle y}
Ne feledje, hogy ez a férgek bináris relációjának grafikonjaként tekinthető , ebben az esetben az " és incidensek" felirat , vagy egy kétoldalas gráf .
G{\ displaystyle {\ mathcal {G}}} R{\ displaystyle R}E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}x{\ displaystyle x}y{\ displaystyle y}xRy{\ displaystyle xRy}
Ha kijelöli a elemek száma esetet , és hogy az elemek esemény , akkor majd a általános néven ismert kettős elszámolás , vagy számlálás a szeletek (vagy a stack) :
nem+(x){\ displaystyle n ^ {+} (x)}y{\ displaystyle y}x{\ displaystyle x}nem-(y){\ displaystyle n ^ {-} (y)}x{\ displaystyle x}y{\ displaystyle y}
∑x∈Enem+(x)=∑y∈Fnem-(y)=|G|=kártya G{\ displaystyle \ sum _ {x \ in E} n ^ {+} (x) = \ sum _ {y \ in F} n ^ {-} (y) = \ left \ vert {\ mathcal {G}} \ right \ vert = {\ text {card}} {\ mathcal {G}}}.
Érdekes konkrét eset, hogy hol és állandóak; a képletet ezután felírják .
nem+{\ displaystyle n ^ {+}}nem-{\ displaystyle n ^ {-}}nem+.|E|=nem-.|F|{\ displaystyle n ^ {+}. \ left \ vert {\ mathcal {E}} \ right \ vert = n ^ {-}. \ left \ vert {\ mathcal {F}} \ right \ vert}
Nyilas diagram ábra
A kettős számlálási képletet ebben a diagramban az értelmezi, hogy a nyilak száma megegyezik az indulások és az érkezések számával.
Incidencia mátrix illusztráció
Ha a grafikon vagy a reláció előfordulási mátrixát definiáljuk azzal, ha tartozik , különben a kettős számlálási képlet azt jelenti, hogy a mátrix feltételeinek összegét vagy sorok sorainak összesítésével, vagy oszlopok oszlopok összegzésével kapjuk. Valójában a társított sorban található helyek száma , és a társított oszlopban található helyek száma .
NÁL NÉL{\ displaystyle A}G{\ displaystyle {\ mathcal {G}}}R{\ displaystyle R}NÁL NÉL(x,y)=1{\ displaystyle A (x, y) = 1}(x,y){\ displaystyle (x, y)}G{\ displaystyle {\ mathcal {G}}}NÁL NÉL(x,y)=0{\ displaystyle A (x, y) = 0}NÁL NÉL{\ displaystyle A}nem+(x){\ displaystyle n ^ {+} (x)}1{\ displaystyle 1}x{\ displaystyle x}nem-(y){\ displaystyle n ^ {-} (y)}1{\ displaystyle 1}y{\ displaystyle y}
Az ellentétes példában az incidencia mátrix az .
NÁL NÉL=(αβγδnál nél1000b1100vs.0011d0100e1001){\ displaystyle A = {\ kezdődik {pmatrix} & \ alfa & \ béta & \ 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}}}
Ebben az értelemben, a képlet a kettős elszámolás egy speciális esete a képlet inverzió összegzés jelek : .
∑(én,j)∈én×Jnál nélén,j=∑én∈én∑j∈Jnál nélén,j=∑j∈J∑én∈énnál nélén,j{\ displaystyle \ sum _ {(i, j) \ I-szeres J} a_ {i, j} = \ sum _ {i \ I-ben} \ sum _ {j \ in J} a_ {i, j} = \ összeg _ {j \ J-ben} \ összeg _ {i \ I} a_ {i, j}}
Példák alkalmazásokra
A fő egész számok összegenem{\ displaystyle n}
Itt a halmazok és megegyeznek az 1 és 2 közötti egészek halmazával és két egész számmal, és akkor fordulnak elő, ha .
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}nem{\ displaystyle n}én{\ displaystyle i}j{\ displaystyle j}én⩽j{\ displaystyle i \ leqslant j}
Tehát ésnem+(én)=nem+1-én{\ displaystyle n ^ {+} (i) = n + 1-i}nem-(én)=én{\ displaystyle n ^ {-} (i) = i}
Ezután megírják a kettős számlálási képletet , amelyből levezetjük a klasszikus képletet .
∑én=1nem(nem+1-én)=∑én=1nemén{\ displaystyle \ sum _ {i = 1} ^ {n} (n + 1-i) = \ sum _ {i = 1} ^ {n} i}∑én=1nemén=nem(nem+1)2{\ displaystyle \ sum _ {i = 1} ^ {n} i = {n (n + 1) \ felett {2}}}
Az elválasztók átlagos száma
Ugyanazok a halmazok és , de és incidensek, ha fel vannak osztva .
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}én{\ displaystyle i}j{\ displaystyle j}én{\ displaystyle i} j{\ displaystyle j}
Ezután a száma többszöröse kisebb, mint vagy egyenlő , ami ahol jelöli egész részét, és az a szám az osztója .
nem+(én){\ displaystyle n ^ {+} (i)}én{\ displaystyle i}nem{\ displaystyle n}⌊nemén⌋{\ displaystyle \ left \ lfloor {\ frac {n} {i}} \ right \ rfloor}⌊.⌋{\ displaystyle \ left \ lfloor. \ right \ rfloor}nem-(én){\ displaystyle n ^ {-} (i)}d(én){\ displaystyle d (i)}én{\ displaystyle i}
Ezután felírják a kettős számlálás képletét ; könnyen levezethetjük ezt ( harmonikus sorozat ), és mivel megkapjuk, hogy az 1 közötti és az ekvivalens szám osztóinak átlagos száma .
∑én=1nemd(én)=∑én=1nem⌊nemén⌋{\ displaystyle \ sum _ {i = 1} ^ {n} d (i) = \ sum _ {i = 1} ^ {n} \ bal \ lfloor {\ frac {n} {i}} \ right \ rfloor }1nem∑én=1nemd(én)∼∑én=1nem1én=Hnem{\ displaystyle {1 \ over n} \ sum _ {i = 1} ^ {n} d (i) \ sim \ sum _ {i = 1} ^ {n} {1 \ over i} = H_ {n} }Hnem∼lnnem{\ displaystyle H_ {n} \ sim \ ln n}nem{\ displaystyle n}lnnem{\ displaystyle \ ln n}
A gráf csúcsainak fokainak összege
Itt a készlet a csúcsok halmaza egy grafikon , a készlet széle és a kapcsolat az előfordulás, hogy a szomszédsági között a csúcsok és az élek. Egy csúcs , értelmezi a mértéke , és egy él , ; a kettős számlálási képletet ezután megírják, ahol a gráf éleinek száma van. Arra következtetünk, hogy a páratlan fokú csúcsok száma páros, ami a kézfogások lemmáját alkotja .
E{\ displaystyle {\ mathcal {E}}}F{\ displaystyle {\ mathcal {F}}}s{\ displaystyle s}nem+(s){\ displaystyle n ^ {+} (s)}s{\ displaystyle s}nál nél{\ displaystyle a}nem-(nál nél)=2{\ displaystyle n ^ {-} (a) = 2}∑deg(s)=2NÁL NÉL{\ displaystyle \ sum \ operátornév {deg} (s) = 2A}NÁL NÉL{\ displaystyle A}
Arra is következtetünk például, hogy egy poliéderben , amelynek minden csúcsa fokozatú , hol van a csúcsok száma.
nem{\ displaystyle n}nemS=2NÁL NÉL{\ displaystyle nS = 2A}S{\ displaystyle S}
Hasonlóképpen, egy sokszögben, ahol minden arcnak éle van, hol van az arcok száma.
o{\ displaystyle p}oF=2NÁL NÉL{\ displaystyle pF = 2A}F{\ displaystyle F}
Képlet a binomiális együtthatókról
Itt a halmaz az elemek halmaza az elemek halmazának és az elemek halmaza az elemek halmazának ; úgy rendelkezett, hogy két részből áll , és esetlegesek, ha azok diszjunkt .
E{\ displaystyle {\ mathcal {E}}}o{\ displaystyle p}nem{\ displaystyle n}F{\ displaystyle {\ mathcal {F}}}q{\ displaystyle q}NÁL NÉL{\ displaystyle A}B{\ displaystyle B}
A grafikon elemeinek száma megéri (választás , majd választás in ). Most itt , ami a több szétbontásait az van , és érdemes . Ezután felírják a kettős számlálás képletét:
G{\ displaystyle {\ mathcal {G}}}(nemo+q)(o+qo){\ displaystyle {\ binom {n} {p + q}} {\ binom {p + q} {p}}}NÁL NÉL∪B{\ displaystyle A \ csésze B}NÁL NÉL{\ displaystyle A}NÁL NÉL∪B{\ displaystyle A \ csésze B}nem+(NÁL NÉL){\ displaystyle n ^ {+} (A)}B{\ displaystyle B}NÁL NÉL{\ displaystyle A}(nem-oq){\ displaystyle {\ binom {np} {q}}}nem-(B){\ displaystyle n ^ {-} (B)}(nem-qo){\ displaystyle {\ binom {nq} {p}}}
(nemo)(nem-oq)=(nemq)(nem-qo)=(nemo+q)(o+qo){\ displaystyle {\ binom {n} {p}} {\ binom {np} {q}} = {\ binom {n} {q}} {\ binom {nq} {p}} = {\ binom {n } {p + q}} {\ binom {p + q} {p}}}.
Például csinál , megkapjuk , ami megváltoztatja az adja a fontos képlet a gyalogot :
q=1{\ displaystyle q = 1}(nem-o)(nemo)=nem(nem-1o)=(o+1)(nemo+1){\ displaystyle (np) {\ binom {n} {p}} = n {\ binom {n-1} {p}} = (p + 1) {\ binom {n} {p + 1}}}o{\ displaystyle p}o-1{\ displaystyle p-1}
(nemo)=nemo(nem-1o-1){\ displaystyle {\ binom {n} {p}} = {n \ over p} {\ binom {n-1} {p-1}}}.
Egyéb példák
Pascal háromszögének egyenesének összege
Keressük meg egy halmaz n elemű részeinek számát .
Első módszer : minden elemre két lehetőség van: vagy benne van a játékban, vagy nincs. Ezért összesen részek vannak.
2×2×...×2(nem idő)=2nem{\ displaystyle 2 \ szor 2x szor \ ldots \ szor 2 \, (n {\ mbox {times}}) = 2 ^ {n}}
Második módszer : egy elemben az elemek száma 0 és 0 közötti egész szám . Az elemekre vonatkozó részek száma a binomiális együttható , tehát az alkatrészek száma .
o{\ displaystyle p}nem{\ displaystyle n}o{\ displaystyle p} (nemo){\ displaystyle {\ binom {n} {p}}}∑o=0nem(nemo){\ displaystyle \ sum _ {p = 0} ^ {n} {\ binom {n} {p}}}
A két kifejezés kiegyenlítése a következőket adja:
∑o=0nem(nemo)=2nem{\ displaystyle \ sum _ {p = 0} ^ {n} {\ binom {n} {p}} = 2 ^ {n}}
Fermat kis tétele
A Fermat-féle kis tétel szerint "ha prímszám, és ha bármilyen egész szám, akkor ennek többszöröse ". Például :
o{\ displaystyle p}nál nél{\ displaystyle a}nál nélo-nál nél{\ displaystyle a ^ {p} -a}o{\ displaystyle p}
4 3 - 4 = 60, amely osztható 3-mal.
Legyen egy prímszám és egy egész szám. Vegyünk egy szimbólumokból álló ábécét . Számoljuk meg azokat a hosszú szavakat , amelyekben legalább két külön szimbólum van.
o{\ displaystyle p}nál nél{\ displaystyle a}nál nél{\ displaystyle a}nem{\ displaystyle n}o{\ displaystyle p}
Első módszer : az ábécében vannak olyan hosszú szavak , amelyekből el kell távolítani az egy és ugyanazon szimbólumból álló szavakat:
nál nélo{\ displaystyle a ^ {p}}o{\ displaystyle p}nál nél{\ displaystyle a}
nem=nál nélo-nál nél{\ displaystyle n = a ^ {p} -a}
Második módszer : ezeket a szavakat szavak halmazába lehet csoportosítani, amelyek kör alakú permutációval levezethetők egymástól . Ezeket a készleteket nyakláncoknak nevezzük (ábra) . Például, ha az ábécé és ha három betűből álló szavakat vesszük figyelembe, akkor a három szót , és ugyanabban a gallérban vannak.
{NÁL NÉL,B,VS,D}{\ displaystyle \ {A, B, C, D \}}NÁL NÉLBD{\ displaystyle ABD}BDNÁL NÉL{\ displaystyle BDA}DNÁL NÉLB{\ displaystyle DAB}
Vannak szimbólum szó minden nyakláncot. Valójában az egyes permutációk más-más szót adnak, mert az elsődleges. Ez nem így lenne, ha nem lenne elsődleges, például a nyakláncban csak 2 szimbólum van, 4 szimbólumból . Tehát:
o{\ displaystyle p}o{\ displaystyle p}o{\ displaystyle p}o{\ displaystyle p}o{\ displaystyle p}NÁL NÉLBNÁL NÉLB{\ displaystyle ABAB}
nem=o.(nyakláncok száma){\ displaystyle n = o. {\ text {(nyakláncok száma)}}}A két kifejezés közötti egyenlőség megírásával azt találjuk, hogy ez osztható .
nem{\ displaystyle n}nem=nál nélo-nál nél{\ displaystyle n = a ^ {p} -a}o{\ displaystyle p}
Színes fák felsorolása
Mennyi a különböző színű fák száma , amelyek különböző magasságok tartományát fedhetik le? A képlet a Cayley megadja a választ:
VSnem{\ displaystyle C_ {n}}nem{\ displaystyle n}
VSnem=nemnem-2{\ displaystyle C_ {n} = n ^ {n-2}}.
Aigner és Ziegler négy különböző bizonyítékot sorol fel ennek az eredménynek. Azt állítják, hogy a négy közül a kettős számlálással végzett demonstrációval tartozunk Jim Pitmannek, amely "közülük a legszebb" .
Ebben a bemutatásban kétféleképpen soroljuk fel a különböző orientált élek sorozatát, amelyek hozzáadhatók egy n csúcsú null gráfhoz (élek nélkül) egy fát alkotva.
Első módszer : a lehetséges nem orientált fák egyikéből indulunk ki, és n csúcsának egyikét választjuk az orientált fa gyökerének, amely orientált fát ad. Vannak módok az első él kiválasztására, majd a következő él kiválasztására stb. Végül az így kialakítható szekvenciák teljes száma:
VSnem{\ displaystyle C_ {n}}nem-1{\ displaystyle n-1}nem-2{\ displaystyle n-2}
VSnemnem!{\ displaystyle C_ {n} n!}.
Második módszer : az éleket egyenként hozzáadjuk az üres grafikonhoz, figyelembe véve az egyes lépésekben rendelkezésre álló lehetőségek számát. Ha már hozzáadtunk egy élkollekciót, hogy k orientált fákból álló erdőt alkossunk (ábra) , akkor választható a következő él. A kezdő csúcsa valóban a gráf n csúcsa lehet, a vége pedig a kezdő csúcsot tartalmazó fa gyökerétől eltérő bármelyik gyökere lehet (ábra) . Végül az első lépésben, a második lépésben stb. Szereplő választások számának szorzásával a választások száma:
nem-k{\ displaystyle nk}nem(k-1){\ displaystyle n (k-1)}k-1{\ displaystyle k-1}
∏k=2nemnem(k-1)=nemnem-1(nem-1)!=nemnem-2nem!{\ displaystyle \ prod _ {k = 2} ^ {n} n (k-1) = n ^ {n-1} (n-1)! = n ^ {n-2} n!}.
A két kifejezés közötti egyenlőség megírásával az élek sorozatainak számához
VSnemnem!=nemnem-2nem!{\ displaystyle C_ {n} n! = n ^ {n-2} n!},
megkapjuk Cayley képletét:
VSnem=nemnem-2{\ displaystyle C_ {n} = n ^ {n-2}}.
Egyéb példák
Megjegyzések és hivatkozások
-
(in) Jacobus H. van Lint és Richard M. Wilson , az Út a kombinatorika , Cambridge University Press ,2001, 602 p. ( ISBN 978-0-521-00601-9 , online olvasás ) , p. 4o. 4 „ A kombinatorika egyik fontos eszköze bizonyos objektumok kétféle módon történő számlálásának módszere ”.
-
Martin Aigner és Günter M. Ziegler , Isteni érvelések , Springer-Verlag ,2013, P. 186.
-
Martin Aigner és Günter M. Ziegler , Isteni érvelések , Springer-Verlag ,2013, P. 187.
-
(in) Martin Aigner és Günter M. Ziegler , igazolásokat a könyv , Springer-Verlag ,1998, P. 145-146.
-
Martin Aigner és Günter M. Ziegler , Isteni érvelések , Springer-Verlag ,2013, P. 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;">