Олар комбинаторика мен ықтималдықтар теориясының элементтерін құрудың негізгі алғышарты адамдардың лотереяға, сүйектерге, карталарға және басқа да кездейсоқ ойындарға тәуелділігі екенін айтады. Көне заманда құмар ойындардың маңызы зор болған. Кейбіреулер байлық, жер, әйел алды. Басқалары соңғы жейдеге дейін барын жоғалтты. Шынында да, тәуекел ойындарының немесе кездейсоқ ойындардың әсері орын алды. Дегенмен, ғылымның қарқынды дамуын қоса алғанда, іргелі себептер болды: эксперименттер, эксперименттер сериясының барысын болжау және нәтижелердегі қатені бағалау қажеттілігі. Мұның бәрі және тағы басқалар комбинаторика мен ықтималдық теориясының элементтерінің пайда болуына әкелді.
Бернулли теоремасы
Комбинаторика 17 ғасырда Кардано, Паскаль, Галилео, Ферма, Лейбниц, Бернулли сияқты ғалымдардың еңбектерінің арқасында пайда болды деп есептеледі. Олар нақты терминдерді енгіздібұл ғылым үшін және бірқатар іргелі заңдар мен комбинаториканың алғашқы формулаларын дәлелдеді. Мысалы, Бернулли теоремасы, ол тек бір-бірінен тәуелсіз және бірдей шарттарда кез келген рет қайталануы мүмкін кездейсоқ тәжірибелер мен тәжірибелерді қарастырған жөн. Бұл теорема комбинаторика мен ықтималдықтар теориясының ғылым ретінде одан әрі дамуын анықтады деп жалпы қабылданған.
Жиілік тұрақтылығы
Комбинаторика элементтерін зерттеуге көшпес бұрын, белгілі бір ойларды ұсынатын нақты мысал келтірейік – сүйек лақтыру. Қарапайымдылық үшін бір сүйекті қарастырайық. Бұл алты қырлы текше, оның әр жағы нөмірленген. Егер біз n лақтырылатын тәжірибелер қатарын жүргізсек және Г1 – 1 саны бар жиектің тамшыларының саны деп есептесек, Г2 - 2 санымен және т.б. лақтыру санының ұлғаюымен n жиілігі Г1/n, Г2 /n, …, Г 6/n, эксперимент басында кездейсоқ болып көрінетін, әбден белгілі мәндерге ие болады. Жақсы теңдестірілген сүйек үшін әр қырының жиілігі үлкен дәлдікпен бірдей болады.
Тағы бір мысал – монета тәжірибесі. Сонымен, ғалым Пирсон 24 000 тиын лақтыруды жүргізгеннен кейін монеталардың бір жағының құлау жиілігі 0,5-ке жақындаған сайын, соғұрлым дәлірек лақтырылады деген қорытындыға келді. Осылайша ол елтаңбаның жоғалуы үшін 0,5005 ықтималдық алды. Бұл принципжиілік тұрақтылығы да теорияның негіздерінің бірі болып табылады.
Тарихи жазба
Ықтималдықтар теориясы мен комбинаторика 20 ғасырда ең белсенді түрде дамыды. Бұл мәселеге орыс және кеңес математиктері үлкен үлес қосты. Олардың ішінде, мысалы, Колмогоров, Чебышев, Ляпунов, Марков. Олар қолдану аясын едәуір кеңейтті, үлкен сандар заңын, орталық шек теоремасын, ықтималдықтар теориясының аксиоматикасын зерттеді және сипаттады. Мұның бәрі тұтас бір ғылымға негіз болды. Бүгінгі таңда физика, химия, биология және басқа да көптеген салаларда, әсіресе олардың практикалық саласында комбинаторика мен ықтималдықтар теориясы элементтерінің маңыздылығын асыра бағалау қиын.
Комбинаторика есептерінің мысалдары
Комбинаторика - белгілі бір шарттарды ескере отырып, кез келген элементтер жиынынан тұратын мүмкін комбинациялар санын бағалау. Ол үшін қажетті есепті ыңғайлы және жылдам шешуге мүмкіндік беретін комбинаторикада формулалар алынды. Бірақ бұл формулаларды көрсетпес бұрын, оларға әкелген сұрақтардың кейбір мысалдарын қарастырайық.
1-тапсырма. Әлем чемпионатының плей-офф кезеңіне 16 команда қатысады. Олар бір-біріне неше жолмен орындарды бөле алады? Мысалы:
- (3, 1, 2, 4..16) - №3 команда бірінші орында, №1 команда екінші орында, т.б.
- (16, 1, 2, 3, 4..15) - №16 команда бірінші орында, …
- (1..7, 9, 8, 10..16) - команданың бірінші орындарында 1, 2, 3, …
Мұның барлығы опциялардың мысалдары. Бұл мәселенің айқын шешімі - бәрін жазумүмкін комбинациялар. Дегенмен, бұл көп уақытты қажет етеді, өйткені олардың саны бірдей болады, өйткені 16 цифрды орындарда қайта реттеу жолдары бар. Комбинаторика элементтері осы сияқты мысалдарды бірден шешеді.
2-мәселе. Осы 16 команданың ішінде тек үшеуі ғана жүлде ала алады. Жеңімпаздар қанша әдіспен анықталады? Бұл жағдайда тапсырманың алдыңғы тапсырмадан айырмашылығы - турнирлік кестенің қандай болатыны және финалға шыққандардың реті қандай екендігі мүлдем маңызды емес. Шынында да, барлық командалардың арасынан жүлделі орындарға таласатын тек үшеуін табу маңызды. Яғни, жиындар {3, 2, 1}, {5, 12, 7}, {8, 1, 2}, т.б. сияқты болуы мүмкін.
3-мәселе. Сұрақты сәл басқаша қойсақ ше: плей-оффқа қатысатын 16 командаға медальдарды бөлудің қанша жолы бар? Екінші тапсырмадан айырмашылық толығымен анық болмауы мүмкін. Дегенмен, енді жүлделі орындарға таласатын үш команданы таңдап қана қоймай, олардың қайсысы қандай орын алатынын анықтауымыз керек. Басқаша айтқанда, егер екінші тапсырма үшін, мысалы, жиындар (5, 12, 1) және (1, 12, 5) баламалы болса, енді командалар реті салмаққа ие болады. Шынында да, бірінші жағдайда №5 команда алтынды алады, ал екінші жағдайда №1 команда.
Төменде әрбір тапсырма комбинаторика бөлімдерінің қайсысына жататынын қарастырамыз және оларды шешу жолын егжей-тегжейлі сипаттаймыз. Әзірше қойылған сұрақтар бойынша өз бетіңізше ойлануға болады.
Тапсырыссыз комбинациялар немесе комбинациялар
Бар болғаны n-элемент бөлігінің комбинациясыk 1-ден n-ге дейінгі мәндерді қабылдай алатын элементтердің k-кешектерінің жиыны - n элементтен таңдалған k элементтердің кез келген комбинациясы. Бұл жағдайда, егер олардың біреуінде n-ден кез келген элемент болса, бірақ екіншісіне жатпайтын болса, екі жиын әртүрлі болып саналады. Басқаша айтқанда, олар тек құрамы бойынша ғана ерекшеленеді. Комбинаторика элементтерінде комбинациялар кіріспе негіз болып табылады.
n-ден k-ге дейінгі комбинациялар саны C k арқылы белгіленеді, ағылшын тіліндегі Combination сөзінен. C 1=n және C =1 мәлімдемелері өте дұрыс. анық Яғни, бір уақытта n элементтен таңдау үшін тек n опция бар (элементтердің өздерімен бірдей сан) және сәйкесінше n дана көлемінде n элементтің жиынын жасауға болады, тек бір.
Сонымен, мысалы, үш элементтен тұратын {e, 2, a} жиынын қарастырайық. Ол үшін C31=3: {a}, {2}, {е}; C32=3: {e, 2}, {2, a}, {a, e}; және соңында C33=1: {e, 2, a}. Еске салайық, бұл жағдайда жиындардағы элементтердің реті маңызды емес.
С 0 не екенін анықтауға тырыссаңыз не болады?
Тапсырыс негізінде орналастыру немесе комбинация
Орналастыру комбинаторикасын түсіну оңай. Бұл бірдей комбинациялар, тек қазір композиция ғана емес, сонымен қатар әр комбинациядағы тәртіп ескеріледі. Сонымен, элементтердің n бөлігін k дана комбинацияларына (жиындарына) орналастыру арқылы, мұнда k 1-ден n-ге дейінгі мәндерді қабылдай алады,белгілі бір ретпен орналасқан n-ден бастап элементтердің k-кешектерінен тұратын кез келген комбинация деп аталады. Басқаша айтқанда, екі орналастыру комбинациясы үш жағдайда әр түрлі болады:
- олар құрамы бойынша ерекшеленеді;
- олар жиындардағы элементтер реті бойынша ерекшеленеді;
- олар құрамы да, реті де ерекшеленеді.
n-ден k-ге дейінгі орналастырулар саны A k арқылы белгіленеді. Үш элементтен тұратын {x, e, z} жиынының барлық орналастыру опцияларын қарастырыңыз:
- A31=3: (x), (e), (z);
- A32=6: (x, e), (e, x), (x, z), (z), x), (e, z), (z, e);
- A33=6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e, x).
Соңғы жол A33 ерекше назар аударуға лайық. Бұл ауыстырулардан басқа ештеңе емес.
Орналастырулар
Жоғарыда айтылғандай, ауыстырулар мағынасы жағынан өте қарапайым. Бұл әрқайсысы n элементтен тұратын n элементтің жай орналасуы. Яғни, бізді элементтердің реті бойынша ерекшеленетін барлық комбинациялар қызықтырады және тек оларда. Немесе, A . Орын ауыстырулар саны Permutation сөзінен алынған P әрпімен белгіленеді. Комбинаторика элементтерінде ауыстырулар тек бір индекспен қамтамасыз етіледі. Мысалы, P3=6, біз алдыңғы тарауда білдік.
Жиындар теориясы арқылы комбинациялар
Өздеріңіз білетіндей, математикада белгісіз тұлғалармен байланысу қиын: жиын, комбинация, т.б. Жақсы болар еді.немен айналысып жатқанымызды математикалық түрде дәл анықтаңыз. Бұл жерде жиындар теориясының тілі көмектеседі. Жиын теориясы тілінде комбинаторика элементтері қандай екенін анықтайық.
Кейбір n-жиын берілсін A={a1, a2, …, a }, ол элементтердің n бөлігін қамтиды. n-жиыннан оның k-ішкі жиынын анықтау оңай, мұндағы k n-ден кіші немесе оған тең. Сонда n-ден k-ге дейінгі комбинациялар n жиынының барлық k ішкі жиындары деп аталады. Осы анықтаманың арқасында C 0 жазбасы қандай болады деген сұраққа жауап беру оңай. Жиын теориясында бос жиын кез келген ішкі жиында болғандықтан, C 0=1. Басқаша айтқанда, ол біреуін қамтитын комбинация болады. элемент - бос жиын.
Осылайша, үш элементтен тұратын {c, b, a} жиынын зерттей отырып, біз мынаны аламыз: C 0 =1: { }; C31=3: {a}, {b}, {c}; C32=3: {a, b}, {b, c}, {c, a}; және соңында C33=1: {a, b, c}.
Сәйкесінше, олар орналастыру комбинаторикасында дәл осылай анықталады. Жалғыз айырмашылық - n-жиынынан реттелген k-ішкі жиындарды таңдау керек. Және барлық ішкі жиындарда бос жиын болады. Ол шартты түрде 0 данадан тұратын n элементтің реттелген комбинациясы болып саналады, яғни. A 0=1.
Түсіксіз конструкциялардан жиындар теориясында нақты анықталған объектілерге көшуіне байланысты сұрақтардың біріне жауап беру өте тривиальды болып шықты.туындаған сұрақтар. Мұның бәрі математика.
Қосу принципі
Бұл комбинаториканың екі негізгі ережесінің бірі. Мәскеуде А нүктесінен В нүктесіне дейін 5 автобус, 3 трамвай және 1 метро пойызы арқылы жетуге болады. Дұрыс жерге жетудің 5 + 3 + 1=9 жолы бар екен. Бұл қосудың комбинаторлық принципі.
Егер мәселені қарастырған кезде оны n тәсілмен шешуге болатын болса, бұл әдістердің біріншісін m1 рет қолдануға болады, екіншісі - m 2рет, т.б., содан кейін бұл мәселе шешіледі m1 + m2 + … + mжол.
Көбейту принципі
Енді Мәскеуден Қазанға Нижний Новгород арқылы жету керек деп елестетейік. Бұл ретте Мәскеу мен Нижний Новгородты 2 пойыз, 3 рейс және 10 жеңіл автокөлік, ал Нижний Новгород пен Қазанды 1 пойыз, 1 рейс және 2 автобус байланыстырады. Қосу принципі бойынша біз Мәскеуден Нижний Новгородқа, одан Қазанға жетудің 13 жолы бар деген қорытындыға келеміз - 4. Мәскеу мен Қазанды байланыстыратын жолдардың жалпы саны: 134=52 болады..
Осылайша, көбейтудің комбинаторлық принципі келесідей оқылады. Егер мәселе кезекті кезеңдердің n бөлігінде шешілсе, бірінші кезеңде m1 жолмен, m2 - екінші кезеңде, т.б., бұл жағдайда бұл кезекті кезеңдер тәуелсіз, яғни алдыңғы кезеңдерде шешімнің қалай қабылданғанына байланысты жолдар саны өзгермейді, содан кейін мәселе шешіледі m1 m2 …m жолдары. Қадамдарда кемінде бір айырмашылық болса, екі шешім әртүрлі болып саналады.
Негізгі формулалар
Формулаларды бірден көрсетейік, содан кейін олардың қайдан шыққанын қысқаша сипаттап, комбинаториканың осы элементтерін пайдаланып, бұрын сипатталған мысалдарды шешейік.
Тұрақ үйлер. Біз осы формуладан бастаймыз, өйткені басқалары осыдан алынған
| A k= | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1)= | n! |
| (n-k)! |
Орналастырулар
| P= | A = | n(n-1)(n-2)(n-3)(n-4)(n-5)…4321= | n! |
Комбинациялар
| C k= | A k | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1) | n! |
| k! | k! | k!(n-k)! |
Бұл формулалардың дәлелі комбинаторика элементтерінің принциптеріне - қосу және көбейту ережелеріне негізделген. Орналастыру санын табудың бірінші формуласын қарастырыңыз. Бірінші кезеңде біз элементтердің n бөлігінің біреуін аламыз және мұны істеудің n әдісі бар. Екінші кезеңде бізге n-1 элементтері және сәйкесінше n-1 таңдаулары қалады. Үшіншіден - n-3 жол. Жиынымызда k дана элементтер болғанша мұны істей береміз. Көбейту ережесі бойынша біз барлығында n (n-1) (n-2) (n-3) (n-4) (n-5) … (n-k + 1) болатынына келеміз.) k элементті таңдау тәсілдері. Орын ауыстыруларды табудың екінші формуласы біріншісінің қарапайым салдары болып табылады.ауыстыру саны m=k. Комбинациялар санын беретін соңғы формула n элементтің комбинацияларын іздеу кезінде k дана к қарауға келген сайын деген ойлардан алынады! n-ден k-ге дейінгі орналасулар (олар k элементтердің ауыстырылуы ретінде алынады). Сондықтан бізде A k=C kk!.
Енді біз бұрын жарияланған тапсырмаларға оралып, опциялар санын бағалай аламыз. Бірінші мәселе үшін біз ауыстыру формуласын пайдалануымыз керек, яғни P16=16!=20 922 789 888 000 ≈ 211012 16 команданы турнирлік кестеде қалай орналастыруға болатынының ықтимал нұсқалары. Екінші мәселе комбинацияларға қатысты, яғни C163=16! / [3!(16-3)!]=560 жеңімпаз. Соңында, соңғы мәселе орналастыруларға қатысты, яғни A163=16! / (16-3)!=16 команданың 3-і жүлделерді бөлісе алатын 3360 әдіс.
Жоғарыда айтылғандарды ескере отырып, үлкен сандар комбинаторикалары қалай жұмыс істейтіні туралы айту артық.
