Kombinatoriska principer

När man bevisar kombinatoriska teorem , erkänns och används vanligtvis flera användbara kombinatoriska regler , eller kombinatoriska principer . Exempel:

Additionsregeln , multiplikationsregeln och principen om inkludering och uteslutning används ofta för uppräkningsändamål .
Dirichlets princip anger ofta existensen av något, eller används för att bestämma minsta eller maximala mängd av något i ett diskret sammanhang .
Principiellt bevis används för att säkerställa att två uppsättningar har samma antal element .
Många kombinatoriska identiteter uppstår från dubbelräkningsmetoden eller distinguished element-metoden .
Genererande funktioner och återkommande relationer är kraftfulla verktyg som kan användas för att manipulera sekvenser och kan vara användbara för att utforska många kombinatoriska situationer.

Tilläggsregel

Intuitivt säger additionsregeln att om händelse A har möjliga utfall och händelse B har möjliga utfall, och endast en av dessa händelser kan inträffa, då är det totala antalet möjliga utfall [1] . $a$ $b$ $a+b$

På språket för mängdlära betyder denna regel att storleken på föreningen av två disjunkta mängder är lika med summan av storlekarna på dessa mängder: om , då (hädanefter anger symbolen antalet element i den finita mängden ) . $A\cap B=\varnothing$ $|A\cup B|=|A|+|B|$ $|A|$ $|A|$

Exempel . Låt oss ta reda på hur många tresiffriga tal som innehåller (i decimalnotation) exakt två nior. Det finns tre möjliga format för sådana nummer [2] :

9n9,n=0,1,2,\dots ,8.

Det finns 9 alternativ totalt.

99n,n=0,1,2,\dots ,8.

Det finns 9 alternativ totalt.

n99,n=1,2,3,\dots ,8.

Endast 8 alternativ.

Enligt additionsregeln blir det totala antalet sådana nummer $9+9+8=26.$

Multiplikationsregel

Multiplikationsregeln är en annan intuitiv princip som säger att om det finns sätt att göra något och sätt att självständigt göra något annat, så finns det sätt att göra både och [1] . $a$ $b$ $ab$

Exempel [3] . Det finns 6 röda, 8 blå och 10 gröna tärningar. Låt oss ta reda på hur många sätt de kan ordnas i två lådor. De röda tärningarna kan delas in i två rutor enligt följande:

0+6;1+5;2+4;3+3;4+2;5+1;6+0.

Endast 7 alternativ.

På samma sätt och oberoende ger de blå tärningarna 9 val, de gröna tärningarna 11. Enligt multiplikationsregeln är det totala antalet val lika med vägen. $7\cdot 9\cdot 11=693$

Principen om inkludering och uteslutning

Inklusions-uteslutningsprincipen relaterar storleken på föreningen av flera uppsättningar till storleken på varje uppsättning och storlekarna på deras möjliga skärningspunkter [4] . Det enklaste exemplet: om det finns två mängder, då är antalet element i deras förening lika med summan av antalet element i mängderna minus antalet element i deras skärningspunkt:

|A\cup B|=|A|+|B|-|A\cap B|

Denna formel generaliserar summaregeln ovan. Variant för tre set:

|A\kopp B\kopp C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

I det allmänna fallet säger principen [4] : om det är ändliga mängder , då: $A_{1}\dots A_{n}$

{\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n }\left|A_{i}\right|-\summa _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right| \\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_ {k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{ Justerat}}

Exempel [5] . Det är 40 turister i en grupp. Av dessa talar 20 engelska, 15 talar franska och 11 talar spanska. Sju personer kan engelska och franska, fem personer kan engelska och spanska, och tre personer kan franska och spanska. Två turister talar alla tre språken. Hur många personer i gruppen kan inte något av dessa språk? Med hjälp av inkluderings-exkluderingsformeln beräknar vi det totala antalet turister som kan minst ett av de nämnda språken: Därför är svaret: $20+15+11-7-5-3+2=33.$ $40-33=7.$

Indelningsregel

Kombinatorisk definition: om ett problem löses med hjälp av en procedur som kan utföras på olika sätt, och för varje metod finns resultat som inte går att skilja från den, så finns det olika sätt att slutföra uppgiften. $n$ $d-1$ $n/d$

På mängdteorin: om en finit mängd är föreningen av parvisa disjunkta delmängder, som var och en innehåller element, då $A$ $n$ $d$ $n=|A|/d.$

På funktionsspråket: om en funktion mappar en ändlig mängd till en ändlig mängd och förbilden av varje värde innehåller exakt värden från A, då $f$ $A$ $b,$ $b\i B$ $d$ $|B|=|A|/d.$

Exempel . Hur många olika sätt finns det att sitta fyra personer vid ett runt bord? Metoder anses olika om minst en person har en annan granne till vänster eller höger. Lösning: om vi förkastar villkoret, så finns det sätt, men varje sätt har 3 "tvillingar" som skiljer sig åt i rotation runt bordet, och enligt problemets tillstånd anses de alla vara ett sätt. Som ett resultat har vi olika sätt. $4!=24$ $24/4=6$

Dirichlets princip

Dirichlet-principen i kombinatorik i den enklaste formuleringen säger att om objekt placeras i lådor så kommer åtminstone en låda att innehålla mer än ett objekt [6] . Med hjälp av denna princip och dess generaliseringar kan man till exempel visa att det finns ett element i en mängd med vissa specifika egenskaper. $a$ $b$ $a>b,$

Exempel . En del av sällskapet av människor skakar hand. Bevisa att det finns minst två personer i företaget som har gjort lika många handslag [7] . Bevis . Låt oss definiera "lådorna" och lägga i rutan de medlemmar i företaget som skakade hand. Om lådan inte är tom, har en eller flera medlemmar i företaget inte gjort några handslag, och därför är lådan tom, eftersom antalet handslag då är färre . Det följer att det alltid finns färre som inte är tomma boxar än och därför motsvarar minst en box två eller flera personer. ■ $N$ $(N>1)$ $N$ ${\displaystyle H_{0},H_{1}\dots H_{N-1))$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ $N.$ $N,$

Bijective proof

Bijektiva bevis används för att bevisa att två finita mängder har samma antal element; de är särskilt användbara i fall där antalet element i en uppsättning är lättare att hitta än i en annan. Under bevisets gång konstrueras en bijektiv funktion (en-till-en-korrespondens) mellan dessa uppsättningar.

Exempel . Låt oss bevisa en av varianterna av Pascals regel : där och binomialkoefficienten karakteriserar samtidigt antalet -elementdelmängder av det naturliga intervallet . Låt oss associera varje elementär delmängd av intervallet med denna delmängd själv, om den inte innehåller ett tal, eller om den innehåller det minus . Det är lätt att visa att för var och en erhålls en bijektion av -element delmängder , å ena sidan, och delmängder av längd och , å andra sidan. Detta faktum återspeglar Pascals regel [8] . $C_{n+1}^{k+1}=C_{n}^{k+1}+C_{n}^{k},$ $0\leqslant k\leqslant n-1,$ ${\displaystyle C_{n}^{m))$ $m$ $\mathbb {R_{n}} =\{1,2,\dots n\}$ $(k+1)$ $\mathbb {R_{n+1}}$ $n+1,$ $n+1,$ $k$ $(k+1)$ $\mathbb {R_{n+1}} ,$ $\mathbb {R_{n}}$ $k+1$ $k$

Dubbelräkningsmetod

Dubbelräkning är en metod som sätter likhetstecken mellan två uttryck för storleken på mängden som studeras, erhållna på två olika sätt [9] . Denna metod är extremt användbar, till exempel för att erhålla kombinatoriska identiteter.

Det enklaste exemplet (se figur): att räkna objekt i en rektangulär tabell efter rader och kolumner leder till samma resultat, vilket innebär att multiplikationen är kommutativ .

Vald elementmetod

Den valda elementmetoden markerar något "valdt element" i uppsättningen för att bevisa det önskade resultatet.

Genererande funktion

Den genererande funktionen för en sekvens är en potensserie vars koefficienter motsvarar medlemmarna i en given sekvens. ${\displaystyle \{a_{1},a_{2},a_{3}\dots \))$

G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.

Denna representation gör det ofta möjligt att tillämpa kraftfulla metoder för matematisk analys på kombinatoriska problem [10] .

Återkommande relation

Upprepningsrelationen definierar varje medlem av sekvensen, förutom den initiala, genom de föregående medlemmarna [11] . Exempel: Fibonacci-tal .

Återkommande relationer kan leda till tidigare okända egenskaper hos en sekvens, men vanligtvis är uttryck i sluten form för sekvensmedlemmar mer önskvärda.

Anteckningar

↑ 1 2 Okulov, 2012 , sid. 25.
↑ Combinatorics: Summa och produktregler . Foxford . Hämtad 21 november 2020. Arkiverad från originalet 21 januari 2021. (obestämd)
↑ Okulov, 2012 , sid. 49, 285.
↑ 1 2 Okulov, 2012 , sid. 26-28.
↑ Yakovlev I. V. Formel för inneslutningar och uteslutningar . Hämtad 21 november 2020. Arkiverad från originalet 20 oktober 2019. (obestämd)
↑ Dirichlet-principen, rutor // Mathematical Encyclopedia (i 5 volymer). - M .: Soviet Encyclopedia , 1982. - T. 2. - S. 182.
↑ Dirichletprincipen . Hämtad 30 mars 2020. Arkiverad från originalet 24 september 2020. (obestämd)
↑ Glibichuk et al., 2016 , sid. 9-10.
↑ Glibichuk et al., 2016 , sid. 18-20.
↑ Okulov, 2012 , sid. 90.
↑ Okulov, 2012 , sid. 76.

Litteratur

Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Element av diskret matematik i problem. - M. : MTSNMO, 2016. - 174 sid. — ISBN 978-5-4439-3024-4 .
Okulov S. M. Diskret matematik. Teori och praktik för problemlösning i informatik: lärobok. - 2:a uppl. — M. : BINOM. Kunskapslaboratoriet, 2012. - 422 sid. - (Lärarutbildningen). - ISBN 978-5-9963-0893-4 .
JH van Lint, RM Wilson (2001), A Course in Combinatorics (Paperback), 2:a upplagan, Cambridge University Press. ISBN 0-521-00601-5 .

Länkar

Användbara identiteter i kombinatorik . Tillträdesdatum: 19 november 2020.