Kombinatorika
A kombinatorika (néha kombinatorikus elemzésnek is nevezik) a matematikának egy olyan ága , amely bizonyos (leggyakrabban véges) halmaz elemeinek adott szabályok szerinti kiválasztásával és elrendezésével kapcsolatos problémák megoldására hivatott. Minden ilyen szabály meghatároz egy bizonyos kiválasztást az eredeti halmaz elemei közül, amelyet kombinatorikus konfigurációnak nevezünk . A kombinatorikus konfigurációk legegyszerűbb példái [1] [2] a permutációk , kombinációk és elhelyezések .
A kombinatorika tipikus problémái [1 ] :
- Határozza meg az adott szabályoknak megfelelő kombinatorikus konfigurációk számát (különösen bizonyítja vagy cáfolja meglétüket).
- Keressen egy gyakorlatilag megfelelő algoritmust a teljes felépítésükhöz.
- Határozza meg a kombinatorikus konfigurációk adott osztályának tulajdonságait!
A kombinatorika szorosan kapcsolódik a matematika sok más területéhez - algebra , geometria , valószínűségszámítás , számelmélet és mások . A tudás legkülönbözőbb területein használják (például genetikában , számítástechnikában , statisztikában , statisztikai fizikában , nyelvészetben ).
A „kombinatorika” kifejezést Leibniz vezette be a matematikai használatba , aki 1666-ban publikálta „Discourses on Combinatorial Art” című munkáját.
Példák kombinatorikus konfigurációkra és problémákra
A kombinatorikai problémák megfogalmazására és megoldására a kombinatorikus konfigurációk különféle modelljeit használják . Példák a kombinatorikus konfigurációkra:
- Az n elemből álló k szerinti elrendezés valamilyen n elemű halmaz k különböző elemének rendezett halmaza .
- Egy n elemből álló permutáció (például az 1, 2, ... n számok ) ezen elemek bármely rendezett halmaza. A permutáció egyben n elem n szerinti elrendezése is .
- Az n - k kombinációja k elemből álló halmaz, amelyet adott n elem közül választunk ki. Azok a halmazok, amelyek csak az elemek sorrendjében (de nem összetételükben) különböznek egymástól, azonosnak számítanak, így különböznek a kombinációk az elhelyezésektől.
- Egy n szám összetétele n tetszőleges reprezentációja pozitív egész számok rendezett összegeként.
- Egy n szám partíciója n tetszőleges reprezentációja pozitív egész számok rendezetlen összegeként.
Példák kombinatorikus problémákra:
- Hányféleképpen lehet n objektumot elhelyezni m dobozban úgy, hogy az adott megszorítások teljesüljenek?
- Hány olyan függvény van egy m elemű halmaztól az n elemű halmazig, amely teljesíti a megadott megszorításokat?
- Hány különböző permutáció létezik 52 játékkártyának? Válasz: 52! (52 faktoriális ), azaz 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 0000
- A kockajátékban két kockával dobnak, és a dobott pontokat összeadják; hány olyan kombináció van, amelyben a felső lapokon lévő pontok összege tizenkettővel egyenlő? Megoldás: Minden lehetséges eredmény egy függvénynek felel meg (a függvény argumentuma a csont száma, értéke a felső lapon lévő pontok). Nyilvánvalóan csak 6 + 6 adja a kívánt 12-es eredményt. Így csak egyetlen olyan kombináció van, amelyben a felső lapokon a pontok összege tizenkettő.
Történelem
Az ókor és a középkor
Az ókori világban megjelentek az alapvető kombinatorikai fogalmak és számítási eredmények . A kombinatorika klasszikus feladatát: „hányféleképpen lehet N -ből kivonni m elemet ” az ókori India szútráiban (Kr. e. 4. századtól kezdődően) szerepel [3] . Úgy tűnik, az indiai matematikusok voltak az elsők, akik felfedezték a binomiális együtthatókat és azok kapcsolatát Newton binomiálisával [3] . A Kr.e. II. században. e. az indiánok tudták, hogy az összes n fokú binomiális együttható összege .
Kombinatorikus motívumok láthatók a kínai „ Változások könyve ” (Kr. e. V. század) szimbolikájában. A szerzők szerint a világon minden a férfi és női princípiumok különféle kombinációiból , valamint nyolc elemből áll: föld, hegyek, víz, szél, zivatar, tűz, felhők és ég [4] . A történészek kombinatorikus problémákat is észleltek a Go és más játékok kézikönyveiben. A matematikusok nagy érdeklődése sok országban az ősidők óta változatlanul felkeltette a varázslatos négyzeteket .
Az ókori görögök különálló kombinatorikai problémákat is fontolgattak, bár ezeknek a kérdéseknek a szisztematikus bemutatása, ha létezett, nem jutott el hozzánk. Chrysippus ( Kr. e. III. század ) és Hipparkhosz ( Kr. e. II. század ) kiszámította, hogy 10 axiómából hány következmény vonható le ; nem ismerjük a számolás módját, de Chrysippus több mint egymilliót kapott, Hipparkhosz pedig több mint 100 000-et [5] . Arisztotelész logikájának bemutatásakor félreérthetetlenül felsorolta a háromtagú szillogizmusok összes lehetséges típusát . Arisztoxenosz a hosszú és rövid szótagok különböző váltakozásait méterben vette figyelembe . [5] A püthagoreusok valószínűleg használtak néhány kombinatorikus szabályt számelméletük és numerológiájuk felépítése során ( tökéletes számok , figuratív számok , pitagoraszi hármasok stb.).
A középkorban a kombinatorika is tovább fejlődött, főleg az európai civilizáción kívül . A 12. században az indiai matematikus , Bhaskara Lilavati fő művében részletesen tanulmányozta a permutációkkal és kombinációkkal kapcsolatos problémákat, beleértve az ismétlődésekkel történő permutációkat is. Egy másik indiai matematikus, Mahavira (9. század közepe) a permutációk és kombinációk számának képleteit publikálta , és ezeket a képleteket az indiai matematikusok már az i.sz. 6. században ismerhették. e. Ábrahám ibn Ezra rabbi filozófus és csillagász (1140 körül) megszámolta az Isten nevének magánhangzóiban előforduló permutációkkal ellátott elhelyezések számát [6] . Megállapította a binomiális együtthatók szimmetriáját is . A pontos képletet később a talmudista és matematikus, Levi ben Gershom (ismertebb nevén Gersonides) tette közzé 1321-ben.
Az Abacus könyve ( Fibonacci , 13. század) számos kombinatorikus problémát tartalmaz . Például azt a feladatot tűzte ki, hogy megtalálja a legkisebb súlyszámot, amely elegendő bármely 1-40 font súlyú termék leméréséhez.
Új idő
Blaise Pascal sokat dolgozott a binomiális együtthatókon, és felfedezett egy egyszerű módszert ezek kiszámítására: " Pascal háromszöge ". Később kiderült, hogy ez a módszer már ismert volt keleten (kb. a 10. századtól), és aritmetikai háromszögnek hívták . Pascal, ellentétben elődeivel, szigorúan megállapította és bizonyította ennek a háromszögnek a tulajdonságait. Az aritmetikai háromszög egy grafikus diagram, amely a binomiális együtthatók közötti kapcsolatokat mutatja. Később, a középkori Angliában a Campanology példákat adott a ma Hamilton - ciklusoknak permutált Cayley-gráfokban .
A reneszánszban más tudományokkal együtt a kombinatorika is gyorsan fejlődött. Gerolamo Cardano egy lényegre törő matematikai tanulmányt írt a kockajátékról , amelyet posztumusz publikáltak. Ennek a játéknak az elméletét Niccolo Tartaglia és Galileo Galilei is tanulmányozta . A valószínűségszámítás története a lelkes játékos, Chevalier de Meret Pierre Fermat -tal és Blaise Pascal - lal folytatott levelezésével kezdődött , ahol több finom kombinatorikus kérdés is felmerült. A szerencsejátékon kívül a kriptográfiában is alkalmaztak (és továbbra is alkalmaznak) kombinatorikus módszereket , mind a rejtjelek fejlesztésére, mind azok feltörésére.
A "kombinatorika" kifejezést Leibniz alkotta meg , őt tartják a modern kombinatorika megalapítójának. 1666-ban (akkor 20 éves volt) kiadta a Discourses on Combinatorial Art című könyvét. Igaz, Leibniz túl tágan értette a "kombinatorika" kifejezést, beleértve az összes véges matematikát , sőt a logikát is [7] . Leibniz tanítványa , Jacob Bernoulli , a valószínűségelmélet egyik megalapítója A sejtések művészete (1713) című könyvében rengeteg információt mutatott be a kombinatorikáról.
Ugyanebben az időszakban alakult ki az új tudomány terminológiája. A " kombináció " ( kombináció ) kifejezés először Pascalban fordul elő (1653, 1665-ben jelent meg). A „ permutáció ” ( permutáció ) kifejezést Jacob Bernoulli használta a megadott könyvben (bár időnként találkozott korábban). Bernoulli is használta az " elrendezés " kifejezést .
A matematikai elemzés megjelenése után szoros kapcsolatot találtak a kombinatorikus és számos analitikai probléma között. Abraham de Moivre és James Stirling képleteket talált a faktoriális közelítésére [8] .
Végül a kombinatorika mint a matematika önálló ága Euler munkáiban öltött testet . Részletesen megvizsgálta például a következő kérdéseket:
- a lovagmozdulat problémája ;
- a hét híd probléma , amely elindította a gráfelméletet ;
- görög-latin terek építése ;
- általánosított permutációk .
A permutációk és kombinációk mellett Euler partíciókat , valamint feltételekkel rendelkező kombinációkat és elhelyezéseket tanulmányozott.
Jelenlegi állapot
Pascal , Newton , Jacob Bernoulli és Euler munkája alapvetővé vált e terület fejlődésében. A modern időkben J. J. Sylvester (19. század vége) és Percy McMahon (20. század eleje) munkái segítettek lerakni az enumeratív és algebrai kombinatorika alapjait . A gráfelmélet iránt is egyre nagyobb az érdeklődés , különösen a négyszín-tétellel és a közgazdasági problémákkal kapcsolatban.
A 20. század második felében a kombinatorika új, robbanásszerű növekedésen ment keresztül, amely a diszkrét matematika, a számítástechnika, a kibernetika és a kísérlettervezés gyors fejlődéséhez kapcsolódott . Ezt a növekedést részben a matematika más területein – algebrában, valószínűségszámításban, funkcionális elemzésben , számelméletben stb. – felfedezett összefüggések és alkalmazások ösztönözték. Ezek az összefüggések elmossák a határokat a kombinatorika és a matematika más területei között, de ugyanakkor az idő bizonyos töredezettséghez vezet a kombinatorika.
A 20. század elején megindult a kombinatorikus geometria fejlődése : Radon , Helly , Young , Blaschke tételeit, és az izoperimetriás tételt is szigorúan igazolták . A Borsuk-Ulam és a Lyusternik-Shnirelman tételeket a topológia, az elemzés és a kombinatorika metszéspontjában igazolták . A 20. század második negyedében felmerült a Borsuk probléma és a Nelson-Erdős-Hadwiger probléma . Az 1940-es években a Ramsey-elmélet formát öltött . A modern kombinatorika atyjának Erdős Pált tartják , aki a valószínűségi elemzést bevezette a kombinatorikába. A véges matematika és különösen a kombinatorika iránti figyelem jelentősen megnőtt a 20. század második fele óta, amikor a számítógépek megjelentek . Ma ez a matematika rendkívül gazdag és gyorsan fejlődő területe.
A kombinatorika módszerei és szakaszai
Enumeratív kombinatorika
Az enumeratív kombinatorika (vagy enumeratív kombinatorika ) a véges halmazok elemei által alkotott különböző konfigurációk (például permutációk ) számbavételének vagy megszámlálásának problémáját veszi figyelembe, amelyekre bizonyos korlátozások vonatkozhatnak, mint például: az elemek megkülönböztethetősége vagy megkülönböztethetősége, a ugyanazon elemek megismétlésének lehetősége stb.
Az összeadás és szorzás szabályai szerint számoljuk meg a halmazon több manipulációval kialakított konfigurációk számát .
A Fibonacci-számok tipikus példái az enumeratív kombinatorika problémáinak, valamint a jól ismert Letter Problem . A duodecimális útvonal egységes szerkezetet biztosít a permutációk , kombinációk és felosztások számlálásához .
Analitikus kombinatorika
Az analitikus kombinatorika a kombinatorikus struktúrák számbavételét jelenti a komplex elemzés és a valószínűségszámítás eszközeivel . Az enumeratív kombinatorikától eltérően, amely explicit kombinatorikus képleteket és sorozatfüggvényeket használ az eredmények leírására, az analitikus kombinatorika célja aszimptotikus képletek származtatása .
Particionálás elmélet
A partícióelmélet a természetes számok particionálásával kapcsolatos különféle numerációs és aszimptotikus problémákat vizsgál , és szorosan kapcsolódik a q sorozatokhoz , speciális függvényekhez és ortogonális polinomokhoz . Eredetileg a számelmélet és -elemzés része volt , ma pedig a kombinatorika részének vagy független területnek tekintik. Tartalmazza a bijektív megközelítést , az elemzés különböző eszközeit és az analitikus számelméletet , valamint kapcsolódik a statisztikai mechanikához is .
Gráfelmélet
A gráfok a kombinatorika alapvető objektumai. A gráfelmélet figyelembe veszi a felsorolásokat (például a gráf k élű csúcsainak n számát ), a létező struktúrákat (például Hamilton-ciklusokat), az algebrai reprezentációkat (például vegyünk egy G gráfot és két x és y számot ). Tatta polinom T G (x, y ) kombinatorikus reprezentáció?). Bár nagyon erős kapcsolat van a gráfelmélet és a kombinatorika között, néha külön tantárgyként kezelik őket. Míg a kombinatorikus módszerek számos gráfelméleti problémára alkalmazhatók, ezt a két tudományágat gyakran használják különféle típusú problémák megoldására.
Sémaelmélet
A sémaelmélet a kombinatorikus sémák tanulmányozása , amelyek bizonyos metszésponti tulajdonságokkal rendelkező részhalmazok halmazai . A blokkdiagramok speciális típusú kombinatorikus diagramok. Ez a terület a kombinatorika egyik legrégebbi része, mint például Kirkman 1850-ben javasolt iskoláslány-problémája . A probléma megoldása a Steiner -rendszer egy speciális esete, amelynek rendszerei fontos szerepet játszanak az egyszerű véges csoportok osztályozásában . Ennek a területnek további kapcsolatai vannak a kódoláselmélettel és a geometriai kombinatorikával.
Véges geometria
A véges geometria olyan geometriai rendszerek tanulmányozása , amelyeknek csak véges számú pontja van. A szerkezetek hasonlóak a folytonos geometriában találhatóakhoz ( euklideszi sík , valós projektív tér stb.), de a kombinatorikusan meghatározottak a fő vizsgált elemek. Ez a terület az áramkörelmélet példáinak gazdag forrása . Nem szabad összetéveszteni a diszkrét geometriával ( kombinatorikus geometriával ).
Rendelmélet
A rendelmélet a részlegesen rendezett halmazok tanulmányozása , mind véges, mind végtelen. A részleges sorrendekre számos példát találunk az algebrában , a geometriában, a számelméletben, valamint a kombinatorikában és a gráfelméletben. A figyelemre méltó osztályok és a részleges sorrendek példái közé tartoznak a rácsok és a Boole-algebrák .
Matroid elmélet
A matroidelmélet elvonatkoztatja a geometria egy részét . Olyan vektorok halmazainak (általában véges halmazainak) tulajdonságait vizsgálja egy vektortérben, amelyek nem függnek bizonyos együtthatóktól, lineárisan függő módon. Nemcsak a szerkezet, hanem a felsorolási tulajdonságok is hozzátartoznak a matroidok elméletéhez. A matroidelméletet Hassler Whitney vezette be, és a rendelmélet részeként tanulmányozta. Jelenleg ez egy független kutatási terület, amely számos kapcsolatban áll a kombinatorika más részeivel.
Extrém kombinatorika
Az extremális kombinatorika a halmazrendszerekkel kapcsolatos extrém kérdéseket vizsgálja . Az ebben az esetben vizsgált kérdéstípusok a lehető legnagyobb gráfra vonatkoznak, amely bizonyos tulajdonságokat kielégít. Például a legnagyobb gráf háromszögek nélkül 2n csúcson egy teljes kétrészes gráf K n, n . Gyakran túl nehéz megtalálni az f(n) extrém választ még pontosan, és csak aszimptotikus becslést lehet adni a -ra .
Ramsey elmélet
A Ramsey-elmélet az extremális kombinatorika másik része. Azt állítja, hogy minden kellően nagy konfiguráció tartalmazni fog bizonyos rendet, és megvizsgálja a szabályos struktúrák jelenlétét az elemek véletlenszerű konfigurációiban. Ez Dirichlet elvének ("galamb és doboz elv") kiterjesztett általánosítása. Ramsey elméletének egy állítása a következő:
6 fős csoportban mindig találhat három embert, akik vagy párban ismerik egymást, vagy párban nem ismerik egymást.A szerkezeti kombinatorika vonatkozásában ugyanez az állítás a következőképpen fogalmazódik meg:
minden 6 csúcsú gráfban van egy klikk vagy egy független 3-as méretű halmaz.Valószínűségi kombinatorika
Ez a rész olyan kérdésekre ad választ, mint: Mi a valószínűsége annak, hogy egy adott tulajdonság jelen van egy véletlenszerű diszkrét objektumban, például egy véletlen gráfban ? Például mennyi a háromszögek átlagos száma egy véletlenszerű gráfban? Valószínűségi módszereket is használnak bizonyos adott tulajdonságokkal rendelkező kombinatorikus objektumok létezésének meghatározására (amelyekre nehéz lehet konkrét példát találni), egyszerűen csak megfigyelve, hogy egy ilyen tulajdonságú objektum véletlenszerű kiválasztásának valószínűsége nagyobb, mint 0 . Ez a megközelítés (gyakran valószínűségi módszerként emlegetve ) rendkívül hatékonynak bizonyult az extremális kombinatorika és a gráfelmélet alkalmazásaiban. Egy szorosan kapcsolódó terület a véges Markov-láncok tanulmányozása , különösen kombinatorikus objektumok esetében. Itt is valószínűségi eszközöket használnak a keverési idő becslésére .
A témában úttörő munkát végző Erdős Pállal gyakran kapcsolatban álló valószínűségi kombinatorikát hagyományosan a kombinatorika más részeinek problémáinak tanulmányozására szolgáló eszköztárnak tekintik. Azonban az algoritmusok elemzésére szolgáló alkalmazások terjedésével a számítástechnikában , valamint a klasszikus valószínűségszámításban, az additív számelméletben és a valószínűségi számelméletben a terület a közelmúltban a kombinatorika önálló területévé nőtte ki magát.
Algebrai kombinatorika
Az algebrai kombinatorika a matematikának egy olyan ága, amely az absztrakt algebra módszereit , különösen a csoportelméletet és a reprezentációelméletet használja különféle kombinatorikus összefüggésekben, és fordítva, kombinatorikus módszereket alkalmaz az algebrai problémákra . Az algebrai kombinatorika folyamatosan bővíti hatókörét, mind tematikus irányokban, mind módszerekben, és a matematika olyan területeként tekinthető, ahol különösen erős és jelentős a kombinatorikus és algebrai módszerek kölcsönhatása.
A szavak kombinatorikája
A szavak kombinatorikája a formális nyelvekkel foglalkozik . A matematika több területén önállóan merült fel, beleértve a számelméletet , a csoportelméletet és a valószínűségszámítást . Alkalmazásai vannak a felsorolásos kombinatorikákban, a fraktálanalízisben , az elméleti számítástechnikában , az automataelméletben és a nyelvészetben. Bár sok alkalmazás új, a formális nyelvtanok klasszikus Chomsky - osztályú hierarchiája talán a legismertebb eredmény ezen a területen.
Kombinatorikus geometria
A geometriai kombinatorika a konvex és diszkrét geometriához kapcsolódik , különösen a poliéderek kombinatorikájához . Például megkérdezi, hogy az egyes dimenzióknak hány lapja lehet egy konvex poliédernek . Fontos szerepet játszanak a poliéderek metrikus tulajdonságai is, például a konvex poliéderek merevségére vonatkozó Cauchy-tétel . Speciális poliédereket is figyelembe kell venni, például permutációs poliédereket , asszociaédereket és Birkhoff poliédereket . A kombinatorikus geometria a diszkrét geometria régimódi neve.
Topológiai kombinatorika
A topológiai kombinatorika a kombinatorika gondolatait és módszereit alkalmazza a topológiában , a gráfszínek , a tisztességes osztás , a particionálás , a döntési fák , a részlegesen rendezett halmazok , a nyaklánc-feladatok és a diszkrét Morse-elmélet tanulmányozásában . Nem szabad összetéveszteni a kombinatorikus topológiával , amely az algebrai topológia régebbi neve .
Aritmetikai kombinatorika
Az aritmetikai kombinatorika a számelmélet , a kombinatorika, az ergodikus elmélet és a harmonikus elemzés kölcsönhatásából jött létre . Az aritmetikai műveletekhez (összeadás, kivonás, szorzás és osztás) kapcsolódó kombinatorikus kiértékelésekről van szó. Az additív számelmélet (néha additív kombinatorikának is nevezik) egy speciális esetre utal, amikor csak összeadásról és kivonásról van szó. Az aritmetikai kombinatorika egyik fontos módszere a dinamikus rendszerek ergodikus elmélete .
Végtelen kombinatorika
Végtelen kombinatorika - a kombinatorika gondolatainak és módszereinek alkalmazása végtelen (beleértve a megszámlálhatatlan ) halmazokra. A halmazelmélet része, a matematikai logika területe , de mind a halmazelmélet, mind az extremális kombinatorika eszközeit és gondolatait használja.
Gian-Carlo Rota a folytonos kombinatorika nevet használta a geometriai valószínűség leírására , mivel sok analógia létezik a szám és a mérték között.
Kapcsolódó területek
Kombinatorikus optimalizálás
A kombinatorikus optimalizálás diszkrét és kombinatorikus objektumok optimalizálásának tanulmányozása. A kombinatorika és a gráfelmélet részeként kezdődött, de ma már az alkalmazott matematika és számítástechnika olyan ágának tekintik, amely a műveletek kutatásához , az algoritmuselmélethez és a számítási komplexitás elméletéhez kapcsolódik .
Kódoláselmélet
A kódoláselmélet az áramkörelmélet részeként kezdődött, a hibajavító kódok korai kombinatorikus konstrukcióival . A tantárgy fő gondolata az adatátvitel hatékony és megbízható módszereinek kidolgozása. Ma ez a kutatás nagy területe, az információelmélet része .
Diszkrét és számítási geometria
A diszkrét geometria (más néven kombinatorikus geometria) szintén a kombinatorika részeként indult meg, a konvex poliéderek és a kontaktszámok korai eredményeivel . A diszkrét geometriának a számítási geometriában való alkalmazásának megjelenésével a két terület részben egyesült, és külön tudományterületté vált. Sok kapcsolat maradt fenn a geometriai és topológiai kombinatorikával, amelyek önmagukban is a korai diszkrét geometria alkotásainak tekinthetők.
Kombinatorika és dinamikus rendszerek
A dinamikus rendszerek kombinatorikus vonatkozásai egy másik feltörekvő terület. Itt a dinamikus rendszerek kombinatorikus objektumokkal definiálhatók. Lásd például a dinamikus gráfrendszert .
Kombinatorika és fizika
Egyre erősebb a kapcsolat a kombinatorika és a fizika , különösen a statisztikai fizika között. Ilyen például az Ising-modell pontos megoldása , valamint egyrészt a Potts-modell , másrészt a kromatikus polinomok és a Tattet -polinomok közötti kapcsolat.
Nyitott kérdések
A kombinatorika (különösen a Ramsey-elmélet) sok jól ismert nyitott problémát tartalmaz , néha nagyon egyszerű megfogalmazással. Például nem tudni, hogy bármelyik embercsoportban hány fő lesz minimum 5 ember, vagy páronként ismerősök, vagy páronként ismeretlenek (bár ismert, hogy 49 fő is elég) [9] .
Vannak más megoldatlan problémák és nem bizonyított hipotézisek is:
- Hadamard sejtése (1893): Minden 4-gyel osztható természeteshez létezik egy valós Hadamard-mátrix . Magyarázat: ismert, hogy a 4-gyel való oszthatóság csak szükséges feltétele a Hadamard-mátrix létezésének. Különféle módszerek léteznek valós sorrendű Hadamard-mátrixok felépítésére 4-gyel osztható végtelen természetes számok sorozatára, de ezek nem teszik lehetővé a Hadamard-sejtés bizonyítását. A legkisebb 4-gyel osztható sorrend, amelyre a Hadamard-mátrix ismeretlen, [10] .
- Természetes rendű véges projektív sík létezése, amely nem egy prímszám hatványa.
- Az Erdős-Renyi hipotézis. Ha egy fix egész szám , akkor for from . Itt van a mátrix állandója – az összes – c egyes sorrendű mátrix halmaza minden sorban és minden oszlopban [11] .
- Az eset Ramsey-számait szinte nem tanulmányozták [12] .
- A duplán sztochasztikus mátrix állandójának minimumának megtalálása általános esetben nem megoldott [13] .
- Nem ismertek azok a szükséges és elégséges feltételek, amelyek mellett létezik közös transzverzális három részhalmaz családra [14] .
Kombinatorika a nyelvészetben
A kombinatorika (nyelvészet) a nyelvi egységek és a hozzájuk tartozó beszédegységek azon tulajdonsága, hogy szintagmatikai, azaz kompatibilitási viszonyokba lépnek.
Jegyzetek
- ↑ 1 2 Sachkov V. N. Kombinatorikus elemzés // Mathematical Encyclopedia (5 kötetben). - M .: Szovjet Enciklopédia , 1979. - T. 2. - S. 974-979. — 1104 p.
- ↑ BRE .
- ↑ 1 2 Amulya Kumar táska . Binomiális tétel az ókori Indiában. Archivált : 2021. augusztus 3., a Wayback Machine Indian J. History Sci., 1:68-74, 1966.
- ↑ Vilenkin N. Ya., 1975 , p. 7.
- ↑ 1 2 Vilenkin N. Ya., 1975 , p. 9.
- ↑ Rövid kommentár a 2Mózes 3:13-hoz.
- ↑ Vilenkin N. Ya., 1975 , p. 19.
- ↑ O'Connor, John; Edmund Robertson. Abraham de Moivre . A MacTutor matematikatörténeti archívuma . Hozzáférés dátuma: 2010. május 31. Az eredetiből archiválva : 2012. április 27.
- ↑ Weisstein, Eric W. Ramsey számok (angolul) a Wolfram MathWorld weboldalán .
- ↑ ADAMAR MATRICES . Az eredetiből archiválva : 2022. január 21.
- ↑ Mink X. Permanens .. - Világ. - 1982. - 211 p.
- ↑ Rybnikov, 1972 , p. 96.
- ↑ Rybnikov, 1972 , p. 110.
- ↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Előadások a diszkrét matematikáról. - Szentpétervár. : BHV-Petersburg, 2004. - S. 530. - 624 p. — ISBN 5-94157-546-7 .
Irodalom
- Anderson, James. Diszkrét matematika és kombinatorika = Discrete Mathematics with Combinatorics. - M . : "Williams" , 2006. - 960 p. — ISBN 0-13-086998-8 .
- Vilenkin N. Ya. Népszerű kombinatorika . - M .: Nauka, 1975.
- Vyalyi MN Lineáris egyenlőtlenségek és kombinatorika . M.: MTsNMO, 2003. 32 p.
- Erosh I. L. Diszkrét matematika. Kombinatorika - Szentpétervár: SPbGUAP, 2001. - 37 p.
- Leontiev VK A kombinatorikus elemzés válogatott problémái. - M .: MSTU kiadó im. N. E. Bauman, 2001. - 179, [3] p.; 20 cm; ISBN 5-7038-1862-1
- Leontiev V.K. Kombinatorika és információk: tankönyv. település ... az "Alkalmazott matematika és fizika" irányába. - Moszkva: MIPT, 2015. - 21 cm; ISBN 978-5-7417-0518-6
- Leontiev VK, Gordeev EN Az információelmélet kombinatorikus vonatkozásai . M.: MIPT, 2019.
- Lipsky V. Kombinatorika a programozónak. — M .: Mir, 1988. — 213 p.
- Raigorodsky A. M. Lineáris-algebrai és valószínűségi módszerek a kombinatorikában . — Nyári iskola „Modern matematika” . – Dubna, 2006.
- Reiser G. J. Kombinatorikus matematika. - per. angolról. - M. , 1966.
- Reingold E., Nivergelt Yu., Deo N. Kombinatorikus algoritmusok. Elmélet és gyakorlat. - M . : Mir, 1980. - 476 p.
- Riordan J. Bevezetés a kombinatorikus elemzésbe. - per. angolról. - M. , 1963.
- Rybnikov K. A. Bevezetés a kombinatorikus elemzésbe. - M. : MGU, 1972. - S. 96. - 308 p.
- Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. - M . : "Mir" , 1990. - 440 p. — ISBN 5-03-001348-2 .
- Stanley R. Enumeratív kombinatorika. Függvényeket és szimmetrikus függvényeket előállító fák = Enumerative Combinatorics. 2. kötet - M . : "Mir" , 2009. - 767 p. — ISBN 978-5-03-003476-8 .
Linkek
- Belesko D. Kombinatorika . 2004.
- Kombinatorikus elemzés / Sachkov V. N. // Nagy Orosz Enciklopédia : [35 kötetben] / ch. szerk. Yu. S. Osipov . - M . : Nagy orosz enciklopédia, 2004-2017.
- Valószínűségi elmélet. 3. A kombinatorika elemei
 Szótárak és enciklopédiák | ||||
|---|---|---|---|---|
| ||||
| A matematika ágai | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| "Tudomány" portál | ||||||||||
| A matematika alapjai halmazelmélet matematikai logika logikai algebra | ||||||||||
| Számelmélet ( aritmetika ) | ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||