Այս հոդվածը կկենտրոնանա մաթեմատիկայի հատուկ բաժնի վրա, որը կոչվում է կոմբինատորիկա: Բանաձևեր, կանոններ, խնդիրների լուծման օրինակներ. այս ամենը կարող եք գտնել այստեղ՝ կարդալով հոդվածը մինչև վերջ։
Այսպիսով, ո՞րն է այս բաժինը: Կոմբինատորիկան զբաղվում է ցանկացած առարկա հաշվելու հարցով։ Բայց այս դեպքում առարկաները սալոր, տանձ կամ խնձոր չեն, այլ այլ բան։ Կոմբինատորիկան օգնում է մեզ գտնել իրադարձության հավանականությունը: Օրինակ՝ թղթախաղի ժամանակ ինչքա՞ն է հավանականությունը, որ հակառակորդը հաղթաթուղթ ունենա։ Կամ նման օրինակ՝ որքա՞ն է հավանականությունը, որ քսան գնդակից բաղկացած տոպրակից հենց սպիտակ կստանաս։ Հենց նման առաջադրանքների համար մենք պետք է իմանանք մաթեմատիկայի այս բաժնի առնվազն հիմունքները:
Կոմբինատոր կոնֆիգուրացիաներ
Հաշվի առնելով կոմբինատորիկայի հիմնական հասկացությունների և բանաձևերի հարցը՝ մենք չենք կարող ուշադրություն չդարձնել կոմբինատորային կոնֆիգուրացիաներին։ Դրանք օգտագործվում են ոչ միայն ձևակերպման, այլև կոմբինատոր տարբեր խնդիրների լուծման համար։ Նման մոդելների օրինակներն են՝
- տեղաբաշխում;
- փոխակերպում;
- համադրություն;
- համարի կազմը;
- բաժանված թիվ.
Առաջին երեքի մասին ավելի մանրամասն կխոսենք ավելի ուշ, բայց այս բաժնում ուշադրություն կդարձնենք կազմությանը և բաժանմանը։ Երբ խոսում են որոշակի թվի (ասենք՝ ա) կազմության մասին, նկատի ունեն ա թվի ներկայացումը որպես որոշ դրական թվերի կարգավորված գումար։ Իսկ բաժանումը չպատվիրված գումար է։
Բաժիններ
Նախքան ուղղակիորեն անցնելը կոմբինատորիկայի բանաձևերին և խնդիրների քննարկմանը, արժե ուշադրություն դարձնել այն փաստին, որ կոմբինատորիկան, ինչպես և մաթեմատիկայի մյուս բաժինները, ունի իր ենթաբաժինները։ Դրանք ներառում են՝
- թվական;
- կառուցվածքային;
- ծայրահեղ;
- Ռեմսիի տեսություն;
- հավանական;
- տոպոլոգիական;
- անսահման.
Առաջին դեպքում խոսքը թվային կոմբինատորիկայի մասին է, խնդիրները համարում են բազմությունների տարրերով կազմված տարբեր կոնֆիգուրացիաների թվարկումը կամ հաշվումը: Որպես կանոն, այս հավաքածուների վրա դրվում են որոշ սահմանափակումներ (տարբերելիություն, անտարբերություն, կրկնվելու հնարավորություն և այլն)։ Եվ այս կոնֆիգուրացիաների թիվը հաշվարկվում է գումարման կամ բազմապատկման կանոնով, որի մասին կխոսենք մի փոքր ուշ։ Կառուցվածքային կոմբինատորիկան ներառում է գրաֆիկների և մատրոիդների տեսությունները: Էքստրեմալ կոմբինատորիկայի խնդրի օրինակն այն է, թե որն է գրաֆիկի ամենամեծ չափը, որը բավարարում է հետևյալ հատկությունները… Չորրորդ պարբերությունում մենք նշեցինք Ռեմսիի տեսությունը, որն ուսումնասիրում է կանոնավոր կառուցվածքների առկայությունը պատահական կոնֆիգուրացիաներում։ Հավանականկոմբինատորիկան կարողանում է պատասխանել հարցին, թե որքան է հավանականությունը, որ տվյալ բազմությունն ունի որոշակի հատկություն: Ինչպես կարող եք կռահել, տոպոլոգիական կոմբինատորիկան կիրառում է մեթոդներ տոպոլոգիայում: Եվ վերջապես, յոթերորդ կետը՝ անսահման կոմբինատորիկան ուսումնասիրում է կոմբինատորիկայի մեթոդների կիրառումը անվերջ բազմությունների վրա։
Ավելացման կանոն
Կոմբինատորիկայի բանաձևերի մեջ կարելի է գտնել բավականին պարզեր, որոնց ծանոթ ենք վաղուց։ Օրինակ՝ գումարի կանոնը։ Ենթադրենք, մեզ տրված է երկու գործողություն (C և E), եթե դրանք միմյանց բացառող են, ապա C գործողությունը կարող է կատարվել մի քանի ձևով (օրինակ՝ a), իսկ գործողությունը E-ն կարող է կատարվել b- եղանակներով, ապա դրանցից որևէ մեկը (C) կամ E) կարելի է անել a + b եղանակներով:
Տեսականորեն սա բավականին դժվար է հասկանալ, կփորձենք ամբողջ միտքը փոխանցել պարզ օրինակով։ Վերցնենք մեկ դասարանում սովորողների միջին թիվը – ասենք քսանհինգ է: Նրանց թվում կան տասնհինգ աղջիկ և տասը տղա։ Ամեն օր դասին նշանակվում է մեկ ուղեկցորդ: Այսօր դասարանի սպասավոր նշանակելու քանի՞ եղանակ կա: Խնդրի լուծումը բավականին պարզ է, մենք կդիմենք ավելացման կանոնին. Առաջադրանքի տեքստում նշված չէ, որ հերթապահ կարող են լինել միայն տղաները կամ միայն աղջիկները։ Հետևաբար, դա կարող է լինել տասնհինգ աղջիկներից կամ տասը տղաներից որևէ մեկը: Կիրառելով գումարի կանոնը, մենք ստանում ենք բավականին պարզ օրինակ, որի հետ կրտսեր դպրոցի աշակերտը հեշտությամբ կարող է հաղթահարել՝ 15 + 10: Հաշվարկելով՝ ստանում ենք պատասխանը՝ քսանհինգ: Այսինքն՝ ընդամենը քսանհինգ ճանապարհ կաՀերթապահ դաս նշանակեք այսօրվա համար։
Բազմապատկման կանոն
Բազմապատկման կանոնը նույնպես պատկանում է կոմբինատորիկայի հիմնական բանաձևերին։ Սկսենք տեսությունից։ Ենթադրենք, պետք է կատարենք մի քանի գործողություններ (ա). առաջին գործողությունը կատարվում է 1 եղանակով, երկրորդը՝ 2 եղանակով, երրորդը՝ 3 եղանակով, և այսպես շարունակ, մինչև վերջին a-գործողությունը կատարվի sa եղանակով։ Այնուհետև այս բոլոր գործողությունները (որոնցից ընդհանուրն ունենք) կարելի է կատարել N եղանակներով։ Ինչպե՞ս հաշվարկել անհայտ N-ը: Բանաձևը կօգնի մեզ դրանում. N \u003d c1c2c3…ca.
Կրկին տեսականորեն ոչինչ պարզ չէ, անցնենք բազմապատկման կանոնի կիրառման պարզ օրինակին։ Վերցնենք քսանհինգ հոգանոց նույն դասարանը, որտեղ սովորում են տասնհինգ աղջիկ և տասը տղա։ Միայն այս անգամ պետք է երկու սպասավոր ընտրել։ Նրանք կարող են լինել կամ միայն տղաներ կամ աղջիկներ, կամ տղա աղջկա հետ: Մենք դիմում ենք խնդրի տարրական լուծմանը. Մենք ընտրում ենք առաջին սպասավորին, ինչպես որոշեցինք վերջին պարբերությունում, ստանում ենք քսանհինգ հնարավոր տարբերակ։ Երկրորդ հերթապահը կարող է լինել մնացած մարդկանցից ցանկացածը։ Մենք ունեինք քսանհինգ աշակերտ, ընտրեցինք մեկը, ինչը նշանակում է, որ մնացած քսանչորս հոգուց ցանկացածը կարող է երկրորդ հերթապահ լինել։ Ի վերջո, մենք կիրառում ենք բազմապատկման կանոնը և գտնում ենք, որ երկու ուղեկցորդները կարող են ընտրվել վեց հարյուր ձևով: Մենք ստացանք այս թիվը՝ բազմապատկելով քսանհինգը և քսանչորսը:
Փոխանակում
Այժմ մենք կքննարկենք ևս մեկ կոմբինատորիկայի բանաձև: Հոդվածի այս բաժնում մենքԵկեք խոսենք փոխակերպումների մասին: Անմիջապես հաշվի առեք խնդիրը օրինակով: Վերցնենք բիլիարդի գնդակներ, մենք ունենք դրանց n-րդ թիվը: Պետք է հաշվենք՝ քանի տարբերակ կա դրանք անընդմեջ դասավորելու, այսինքն՝ պատվիրված հավաքածու կազմելու համար։
Սկսենք, եթե գնդակներ չունենք, ուրեմն ունենք նաև զրո տեղաբաշխման տարբերակներ։ Իսկ եթե ունենք մեկ գնդակ, ապա դասավորությունը նույնպես նույնն է (մաթեմատիկորեն սա կարելի է գրել հետևյալ կերպ. Р1=1): Երկու գնդակ կարելի է դասավորել երկու տարբեր ձևով՝ 1, 2 և 2, 1։ Հետևաբար, Р2=2։ Երեք գնդակ կարելի է դասավորել վեց ձևով (Р3=6)՝ 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Իսկ եթե այդպիսի գնդակներ չկան երեք, այլ տաս կամ տասնհինգ։ Բոլոր հնարավոր տարբերակները թվարկելը շատ երկար է, ապա մեզ օգնության է գալիս կոմբինատորիկան։ Փոխակերպման բանաձևը կօգնի մեզ գտնել մեր հարցի պատասխանը: Pn=nP (n-1): Եթե փորձենք պարզեցնել բանաձևը, ապա կստանանք՝ Pn=n (n - 1) … 21: Եվ սա առաջին բնական թվերի արտադրյալն է: Նման թիվը կոչվում է գործոն և նշվում է որպես n!
Եկեք դիտարկենք խնդիրը. Առաջնորդն ամեն առավոտ շարում է իր ջոկատը (քսան հոգի)։ Ջոկատում կան երեք լավագույն ընկերներ՝ Կոստյան, Սաշան և Լեշան։ Որքա՞ն է հավանականությունը, որ նրանք կլինեն միմյանց կողքին։ Հարցի պատասխանը գտնելու համար անհրաժեշտ է «լավ» արդյունքի հավանականությունը բաժանել արդյունքների ընդհանուր թվի վրա: Փոխակերպումների ընդհանուր թիվը 20 է:=2,5 կվինտիլիոն: Ինչպե՞ս հաշվել «լավ» արդյունքների քանակը: Ենթադրենք, որ Կոստյան, Սաշան և Լեշան մեկ գերմարդ են։ Հետո մենքՄենք ընդամենը տասնութ առարկա ունենք։ Փոխակերպումների թիվը այս դեպքում 18=6,5 կվադրիլիոն է։ Այս ամենի հետ մեկտեղ Կոստյան, Սաշան և Լեշան կարող են կամայականորեն շարժվել միմյանց մեջ իրենց անբաժանելի եռյակով, և սա ևս 3-ն է:=6 տարբերակ: Այսպիսով, մենք ընդհանուր առմամբ ունենք 18 «լավ» համաստեղություններ:3! Պարզապես պետք է գտնենք ցանկալի հավանականությունը՝ (18!3!) / 20! Ինչը մոտավորապես 0,016 է։ Եթե փոխարկվի տոկոսի, ապա ստացվում է ընդամենը 1,6%։
Կացություն
Այժմ կքննարկենք կոմբինատորիկայի ևս մեկ շատ կարևոր և անհրաժեշտ բանաձև։ Տեղավորումը մեր հաջորդ խնդիրն է, որն առաջարկում ենք ձեզ դիտարկել հոդվածի այս բաժնում: Մենք գնալու ենք ավելի բարդանալու: Ենթադրենք, որ մենք ցանկանում ենք դիտարկել հնարավոր փոխարկումները ոչ թե ամբողջ բազմությունից (n), այլ ավելի փոքրից (m): Այսինքն՝ մենք դիտարկում ենք n տարրի փոխարկումները m-ով։
Կոմբինատորիկայի հիմնական բանաձևերը պետք է ոչ միայն անգիր անել, այլ հասկանալ: Նույնիսկ չնայած այն հանգամանքին, որ դրանք ավելի են բարդանում, քանի որ մենք ունենք ոչ թե մեկ պարամետր, այլ երկու։ Ենթադրենք, որ m \u003d 1, ապա A \u003d 1, m \u003d 2, ապա A \u003d n(n - 1): Եթե մենք էլ ավելի պարզեցնենք բանաձևը և անցնենք նշագրման՝ օգտագործելով գործակիցները, ապա կստանանք բավականին հակիրճ բանաձև՝ A \u003d n! / (n - m)!
Կոմբինացիա
Մենք դիտարկել ենք կոմբինատորիկայի գրեթե բոլոր հիմնական բանաձևերը օրինակներով: Այժմ եկեք անցնենք կոմբինատորիկայի հիմնական դասընթացի քննարկման վերջին փուլին՝ ծանոթանալ համադրությանը: Այժմ մենք կընտրենք m տարրեր մեր ունեցած n-ից, մինչդեռ բոլորը կընտրենք բոլոր հնարավոր ձևերով։ Այդ դեպքում ինչո՞վ է սա տարբերվում կացարանից: Մենք չենք անիհաշվի առեք կարգը. Այս չպատվիրված հավաքածուն կլինի համակցություն:
Անմիջապես ներկայացրեք նշումը. C. Մենք n-ից վերցնում ենք m գնդակների տեղադրում: Մենք դադարում ենք ուշադրություն դարձնել պատվերին և ստանում ենք կրկնվող համակցություններ։ Համակցությունների թիվը ստանալու համար պետք է տեղաբաշխումների քանակը բաժանել m-ի: (մ ֆակտորային): Այսինքն, C \u003d A / m! Այսպիսով, n գնդակից ընտրելու մի քանի եղանակ կա, մոտավորապես հավասար է այն քանակին, թե որքան ընտրենք գրեթե ամեն ինչ: Սրա տրամաբանական արտահայտությունը կա՝ քիչ ընտրելը նույնն է, ինչ գրեթե ամեն ինչ դեն նետել։ Կարևոր է նաև այս պահին նշել, որ կոմբինացիաների առավելագույն քանակին կարելի է հասնել, երբ փորձում եք ընտրել կետերի կեսը:
Ինչպե՞ս ընտրել խնդիր լուծելու բանաձև:
Մենք մանրամասնորեն ուսումնասիրել ենք կոմբինատորիկայի հիմնական բանաձևերը՝ տեղաբաշխում, փոխարկում և համակցություն: Այժմ մեր խնդիրն է հեշտացնել կոմբինատորիկայի խնդրի լուծման համար անհրաժեշտ բանաձեւի ընտրությունը։ Դուք կարող եք օգտագործել հետևյալ բավականին պարզ սխեման՝
- Հարցրու ինքդ քեզ՝ արդյո՞ք հաշվի է առնվում տարրերի հերթականությունը խնդրի տեքստում։
- Եթե պատասխանը ոչ է, ապա օգտագործեք համակցման բանաձևը (C=n! / (m!(n - m)!)).
- Եթե պատասխանը ոչ է, ապա դուք պետք է պատասխանեք ևս մեկ հարցի. արդյո՞ք բոլոր տարրերը ներառված են համակցության մեջ:
- Եթե պատասխանը այո է, ապա օգտագործեք փոխակերպման բանաձևը (P=n!):
- Եթե պատասխանը ոչ է, ապա օգտագործեք բաշխման բանաձևը (A=n! / (n - m)!).
Օրինակ
Մենք դիտարկել ենք կոմբինատորիկայի տարրերը, բանաձևերը և մի քանի այլ հարցեր: Հիմա անցնենքհաշվի առնելով իրական խնդիր. Պատկերացրեք, որ ձեր առջև ունի կիվի, նարինջ և բանան։
Հարց առաջին. քանի՞ եղանակով կարող են դրանք վերադասավորվել: Դա անելու համար մենք օգտագործում ենք փոխակերպման բանաձևը. P=3!=6 եղանակ։
Հարց երկրորդ. քանի՞ եղանակով կարելի է ընտրել մեկ միրգ: Սա ակնհայտ է, մենք ունենք ընդամենը երեք տարբերակ՝ ընտրել կիվի, նարինջ կամ բանան, բայց մենք կիրառում ենք համակցման բանաձևը՝ C \u003d 3! / (2!1!)=3.
Հարց երրորդ. քանի՞ եղանակով կարելի է ընտրել երկու պտուղ: Ի՞նչ տարբերակներ ունենք։ Կիվի և նարինջ; կիվի և բանան; նարինջ և բանան. Այսինքն՝ երեք տարբերակ, բայց դա հեշտ է ստուգել՝ օգտագործելով համակցման բանաձևը՝ C \u003d 3! / (1!2!)=3
Հարց չորրորդ. քանի՞ եղանակով կարելի է ընտրել երեք պտուղ: Ինչպես տեսնում եք, երեք միրգ ընտրելու միայն մեկ տարբերակ կա՝ վերցնել կիվի, նարինջ և բանան։ C=3! / (0!3!)=1.
Հարց հինգերորդ. քանի՞ եղանակով կարող եք ընտրել առնվազն մեկ միրգ: Այս պայմանը ենթադրում է, որ մենք կարող ենք վերցնել մեկ, երկու կամ բոլոր երեք պտուղները։ Հետևաբար, մենք ավելացնում ենք C1 + C2 + C3=3 + 3 + 1=7: Այսինքն, մենք ունենք յոթ տարբերակ սեղանից առնվազն մեկ կտոր միրգ վերցնելու համար:
