Հնարավոր ընտրությունները 10-ից 4-ն են: Կոմբինատորիկայի բանաձևերը. Փոխադարձություններ. Փոխակերպումների քանակի հաշվում

Բոլոր N տարրերը, և ոչ մեկը չի կրկնվում, ապա սա փոխակերպումների քանակի խնդիրն է: Լուծումը կարելի է գտնել պարզ. N տարրից որևէ մեկը կարող է առաջին տեղը զբաղեցնել շարքում, հետևաբար ստացվում է N տարբերակ։ Երկրորդ տեղում՝ ցանկացած, բացառությամբ այն մեկի, որն արդեն օգտագործվել է առաջին տեղի համար։ Հետևաբար, արդեն հայտնաբերված N ընտրանքներից յուրաքանչյուրի համար կա (N - 1) երկրորդ տեղի ընտրություն և ընդհանուրհամակցությունները դառնում են N*(N - 1):
Նույնը կարելի է կրկնել շարքի մնացած տարրերի համար։ Հենց վերջին տեղի համար մնում է միայն մեկ տարբերակ՝ մնացած վերջին տարրը: Նախավերջինի համար՝ երկու տարբերակ և այլն։
Հետևաբար, մի շարք N չկրկնվող տարրերի համար հնարավոր փոխարկումները հավասար են 1-ից մինչև N բոլոր ամբողջ թվերի արտադրյալին: Այս արտադրյալը կոչվում է N-ի գործակից և նշվում է N-ով: (կարդացեք «en factorial»):

Նախորդ դեպքում շարքի հնարավոր տարրերի և տեղերի թիվը համընկնում էր, և դրանց թիվը հավասար էր N-ին: Բայց հնարավոր է մի իրավիճակ, երբ շարքում ավելի քիչ տեղեր կան, քան հնարավոր տարրերը: Այլ կերպ ասած, նմուշի տարրերի թիվը հավասար է որոշ M թվի, իսկ M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Նախ, կարող է անհրաժեշտ լինել հաշվել հնարավոր եղանակների ընդհանուր թիվը, որոնցով N-ից M տարրերը կարող են անընդմեջ դասավորվել: Նման ձևերը կոչվում են տեղաբաշխումներ:
Երկրորդ, հետազոտողին կարող է հետաքրքրել M տարրերը N-ից ընտրելու եղանակների քանակով: Այս դեպքում տարրերի հերթականությունը այլևս կարևոր չէ, բայց ցանկացած երկու տարբերակ պետք է տարբերվի միմյանցից առնվազն մեկ տարրով: . Նման մեթոդները կոչվում են համակցություններ:

N-ից M տարրերի տեղաբաշխումների թիվը գտնելու համար կարելի է դիմել նույն պատճառաբանության, ինչ փոխատեղումների դեպքում։ Առաջին տեղում դեռ կարող են լինել N տարրեր, երկրորդում (N - 1) և այլն։ Բայց վերջին տեղի համար՝ թիվը տարբերակները 1 չէ, այլ (N - M + 1), քանի որ երբ տեղաբաշխումն ավարտվի, դեռ կմնան (N - M) չօգտագործված տարրեր։
Այսպիսով, N-ից M տարրերի վրա տեղաբաշխումների թիվը հավասար է (N - M + 1)-ից N բոլոր ամբողջ թվերի արտադրյալին կամ, համարժեքորեն, N!/(N - M)! գործակցին:

Ակնհայտ է, որ N-ից M տարրերի համակցությունների թիվը պակաս կլինի տեղաբաշխումների քանակից։ Յուրաքանչյուր հնարավոր համակցության համար կա M! հնարավոր տեղաբաշխումներ՝ կախված այս համակցության տարրերի հերթականությունից։ Հետևաբար, այս թիվը գտնելու համար անհրաժեշտ է M տարրերի վրա տեղաբաշխումների քանակը N-ից բաժանել N!-ի: Այլ կերպ ասած, N-ից M տարրերի համակցությունների թիվը N!/(M!*(N - M)!):

Ընկերներ! Քանի որ ես արդեն ունեմ այս մեռած նոթատետրը, այն օգտագործում եմ ձեզ հարց տալու մի խնդիր, որի հետ երեկ պայքարում էին երեք ֆիզիկոս, երկու տնտեսագետ, մեկը Պոլիտեխնիկից և մեկը հումանիտար: Մենք կոտրել ենք մեր ամբողջ ուղեղը և անընդհատ տարբեր արդյունքներ ենք ստանում։ Միգուցե ձեր մեջ կան ծրագրավորողներ և մաթեմատիկական հանճարներ, բացի այդ, խնդիրն ընդհանրապես դպրոցական է և շատ հեշտ, պարզապես բանաձև չունենք։ Որովհետև մենք դուրս մնացինք ճշգրիտ գիտություններիսկ դրա փոխարեն, չգիտես ինչու, գրում ենք գրքեր և նկարում: Ներողություն.

Այսպիսով, նախապատմություն:

Ինձ տվեցին նոր բանկային քարտ և, ինչպես միշտ, ես առանց ջանքերի կռահեցի դրա փին կոդը: Բայց ոչ անընդմեջ: Այսինքն, ասենք, որ փին կոդը եղել է 8794, և ես զանգահարել եմ 9748։ Այսինքն՝ ես հաղթական եմ։ գուշակեց բոլոր թվերըտրված քառանիշ թվի մեջ պարունակվող. Դե, այո, ոչ միայն թիվ, բայց պարզապես դրա բաղադրիչները ժամըզարմացավ. Բայց բոլոր թվերը ճշմարիտ են: ԾԱՆՈԹԱԳՐՈՒԹՅՈՒՆ – Ես գործեցի պատահականորեն, այսինքն՝ ես ստիպված չէի ճիշտ հերթականությամբ դասավորել արդեն հայտնի թվերը, ես ուղղակի գործել եմ ոգով. այստեղ ինձ համար անհայտ չորս թվեր կան, և կարծում եմ, որ դրանց թվում կարող են լինել. 9, 7, 4 և 8, և դրանց հերթականությունը կարևոր չէ։Մենք անմիջապես հարցրինք ինքներս մեզ Քանի՞ տարբերակ ունեի(երևի հասկանալու համար, թե ինչ թույն է, որ վերցրեցի ու կռահեցի)։ Այսինքն՝ չորս թվերի քանի՞ համակցությունից պետք է ընտրեի։ Եվ հետո, իհարկե, սկսվեց դժոխքը: Ամբողջ երեկո մեր գլուխները պայթեցին, վերջում բոլորը բացարձակ դուրս եկան տարբեր տարբերակներպատասխան! Ես նույնիսկ սկսեցի անընդմեջ գրել այս բոլոր համակցությունները նոթատետրում, քանի որ դրանք ավելացան, բայց չորս հարյուրի ժամանակ հասկացա, որ դրանք չորս հարյուրից ավելի են (ամեն դեպքում, սա հերքեց ֆիզիկոս Թրեշի պատասխանը, որը վստահեցրեց. ինձ, որ եղել են չորս հարյուր համակցություններ, բայց դեռ այնքան էլ պարզ չէ) - և հրաժարվեց:

Իրականում, հարցի էությունը.Որքա՞ն է քառանիշ թվի մեջ պարունակվող չորս թվերը գուշակելու (ցանկացած հերթականությամբ) հավանականությունը։

Թե չէ, եկեք վերաձեւակերպենք (ես հումանիստ եմ, կներեք, թեեւ մաթեմատիկայի նկատմամբ միշտ ահռելի թուլություն եմ ունեցել) ավելի ու ավելի պարզ դարձնելու համար։ Ինչպես չկրկնվողթվերի համակցություններ, որոնք պարունակվում են 0-ից մինչև 9999 թվերի շարքում: ( խնդրում եմ սա մի շփոթեք «քանի համակցություններ» հարցի հետ չկրկնվողթվեր»!!! թվերը կարող են կրկնվել! Նկատի ունեմ՝ 2233 և 3322 համարներն են այս դեպքընույն համադրությունը):

Կամ ավելի կոնկրետ։ Ես պետք է չորս անգամ գուշակեմ տասը թվից մեկը: Բայց ոչ անընդմեջ:

Դե, կամ մեկ այլ բան: Ընդհանուր առմամբ, դուք պետք է պարզեք, թե քանի տարբերակ ունեի թվային համակցության համար, որոնք ձևավորեցին քարտի փին կոդը: Օգնե՛ք, բարի մարդիկ։ Ուղղակի խնդրում եմ, օգնեք, միանգամից մի սկսեք գրել, որ դրանց համար կա 9999 տարբերակ(երեկ սա սկզբում բոլորի մտքով անցավ) քանի որ սա անհեթեթություն է, ի վերջո, մեզ անհանգստացնող տեսանկյունից 1234 թիվը, 3421 թիվը, 4312 թիվը և այլն. մեկ ու նույնը! Դե, այո, թվերը կարելի է կրկնել, քանի որ կա 1111 փին կոդ կամ այնտեղ, օրինակ, 0007, դուք կարող եք պատկերացնել մեքենայի համարը փին կոդի փոխարեն։ Ենթադրենք, որքա՞ն է մեքենայի համարը կազմող բոլոր միանիշ թվերը գուշակելու հավանականությունը։ Կամ հավանականության տեսությունն ընդհանրապես վերացնելու համար՝ քանի՞ թվային համակցություններից պետք է ընտրեի մեկը։

Խնդրում եմ ձեր պատասխաններն ու հիմնավորումները մի քանի ստույգ բանաձևերով կրկնօրինակեք, քանի որ երեկ մենք քիչ էր մնում կորցնեինք մեր խելքը: Կանխավ շատ շնորհակալություն բոլորին:

P.S. Մեկը խելացի մարդծրագրավորող, նկարիչ և գյուտարար, պարզապես շատ ճիշտ առաջարկեց խնդրի ճիշտ լուծումը՝ ինձ տրամադրելով մի քանի րոպե հիանալի տրամադրություն. Խնդրի լուծումը սա է՝ նա օբսեսիվ-կոմպուլսիվ խանգարում ունի, բուժումը հետևյալն է՝ ամուսնանալ և լոլիկ փռել։ Եթե ես լինեի նրա փոխարեն, ինձ ավելի շատ կհուզեր ոչ թե «որն է հավանականությունը», այլ «այդ բոլոր թվերին ուշադրություն դարձնո՞ւմ եմ» հարցը։Ընդհանրապես ավելացնելու բան չկա :)

Ստորև բերված հաշվիչը նախատեսված է n-ով m տարրերի բոլոր համակցությունները ստեղծելու համար:
Նման համակցությունների թիվը կարելի է հաշվարկել «Elements of Combinatorics» հաշվիչի միջոցով: Փոխարկումներ, տեղաբաշխումներ, համակցություններ:

Հաշվիչի տակ առաջացման ալգորիթմի նկարագրությունը:

Ալգորիթմ

Համակցությունները ստեղծվում են բառարանագրական կարգով: Ալգորիթմն աշխատում է բազմության տարրերի հերթական ինդեքսներով։
Դիտարկենք ալգորիթմը օրինակով։
Ներկայացման հեշտության համար դիտարկեք հինգ տարրերից բաղկացած մի շարք, որոնց ինդեքսները սկսվում են 1-ով, այն է՝ 1 2 3 4 5:
Պահանջվում է ստեղծել m = 3 չափի բոլոր համակցությունները:
Նախ սկզբնավորվում է տրված m չափի առաջին համակցությունը՝ ինդեքսներն աճման կարգով
1 2 3
Այնուհետև ստուգվում է վերջին տարրը, այսինքն՝ i = 3: Եթե դրա արժեքը փոքր է n-m + i-ից, ապա այն ավելանում է 1-ով:
1 2 4
Վերջին տարրը կրկին ստուգվում է, և կրկին ավելացվում է:
1 2 5
Այժմ տարրի արժեքը հավասար է հնարավոր առավելագույնին՝ n - m + i = 5 - 3 + 3 = 5, ստուգվում է i = 2-ով նախորդ տարրը։
Եթե դրա արժեքը փոքր է n - m + i-ից, ապա այն ավելանում է 1-ով, իսկ դրան հաջորդող բոլոր տարրերի համար արժեքը հավասար է նախորդ տարրի արժեքին գումարած 1:
1 (2+1)3 (3+1)4 = 1 3 4
Այնուհետև մենք կրկին ստուգում ենք i = 3:
1 3 5
Այնուհետև - ստուգեք i = 2:
1 4 5
Այնուհետև գալիս է i = 1 հերթը:
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Եվ հետագայում,
2 3 5
2 4 5
3 4 5 - վերջին համակցությունը, քանի որ դրա բոլոր տարրերը հավասար են n - m + i:

Չնայած PIN-ների կարևոր դերին աշխարհի ենթակառուցվածքում, դեռևս ոչ մի ակադեմիական հետազոտություն չի իրականացվել այն մասին, թե իրականում ինչպես են մարդիկ ընտրում PIN-ները:

Քեմբրիջի համալսարանի հետազոտողներ Սորեն Պրայբուշը և Ռոս Անդերսոնը շտկել են իրավիճակը՝ հրապարակելով աշխարհում առաջին քանակական վերլուծությունը 4 նիշանոց բանկային PIN-ը գուշակելու դժվարության վերաբերյալ:

Օգտագործելով ոչ բանկային աղբյուրներից և առցանց հարցումներից գաղտնաբառերի արտահոսքի տվյալները՝ հետազոտողները պարզել են, որ օգտատերերը շատ ավելի լուրջ են վերաբերվում PIN կոդերի ընտրությանը, քան կայքերի գաղտնաբառերի ընտրությանը. կոդերի մեծ մասը պարունակում է թվերի գրեթե պատահական շարք: Այնուամենայնիվ, նախնական տվյալների մեջ կան և՛ պարզ համակցություններ, և՛ ծննդյան տարեդարձեր, այսինքն՝ որոշ բախտի դեպքում հարձակվողը կարող է պարզապես կռահել բաղձալի կոդը։

Հետազոտության մեկնարկային կետը RockYou տվյալների բազայից 4 նիշանոց գաղտնաբառերի հաջորդականությունն էր (1,7 մլն), և 200 հազար PIN կոդերի տվյալների բազա iPhone-ի էկրանի կողպման ծրագրից (շտեմարանը տրամադրել է հավելվածի մշակող Դանիել Ամիտայը): . Այս տվյալների վրա կառուցված գրաֆիկներում հետաքրքիր օրինաչափություններ են հայտնվում՝ ամսաթվերը, տարիները, կրկնվող թվերը և նույնիսկ 69-ով ավարտվող PIN կոդերը: Այս դիտարկումների հիման վրա գիտնականները գծային են կառուցել ռեգրեսիոն մոդել, որը գնահատում է յուրաքանչյուր PIN-ի ժողովրդականությունը՝ հիմնվելով 25 գործոնների վրա, օրինակ՝ արդյոք կոդը DDMM ամսաթիվ է, արդյոք այն աճող հաջորդականություն է և այլն։ Այս ընդհանուր պայմանները համապատասխանում են յուրաքանչյուր հավաքածուի PIN կոդերի 79%-ին և 93%-ին:

Այսպիսով, օգտատերերն ընտրում են 4 նիշանոց կոդեր՝ հիմնվելով ընդամենը մի քանի պարզ գործոնների վրա։ Եթե բանկային PIN կոդերը ընտրվեին այս կերպ, դրանց 8-9%-ը կարելի էր գուշակել ընդամենը երեք փորձով: Բայց, իհարկե, մարդիկ շատ ավելի ուշադիր են բանկային ծածկագրերի նկատմամբ։ Իրական բանկային տվյալների որևէ մեծ հավաքածուի բացակայության դեպքում հետազոտողները հարցազրույց են անցկացրել ավելի քան 1300 մարդու հետ՝ գնահատելու, թե իրական PIN կոդերը որքանով են տարբերվում արդեն իսկ դիտարկվածներից: Հաշվի առնելով հետազոտության առանձնահատկությունները՝ հարցվողներին հարցրել են ոչ թե իրենք՝ կոդերի, այլ միայն վերը նշված գործոններից որևէ մեկին դրանց համապատասխանության մասին (բարձրացում, DDMM ձևաչափ և այլն):

Պարզվեց, որ մարդիկ իսկապես շատ ավելի զգույշ են բանկի PIN կոդեր ընտրելիս։ Հարցվածների մոտ մեկ քառորդն օգտագործում է բանկի կողմից ստեղծված պատահական PIN: Մեկ երրորդից ավելին ընտրում է իր PIN կոդը՝ օգտագործելով իր հին հեռախոսահամարը, համարը ուսանողական քարտ, կամ թվերի այլ հավաքածու, որը պատահական է թվում: Արդյունքների համաձայն՝ քարտապանների 64%-ն օգտագործում է կեղծ պատահական PIN կոդ, ինչը շատ ավելին է, քան 23-27%-ը նախորդ ոչ բանկային կոդերի փորձարկումներում։ Եվս 5%-ը օգտագործում է թվային օրինաչափություն (օրինակ՝ 4545), իսկ 9%-ը նախընտրում է ստեղնաշարի օրինակ (օրինակ՝ 2684): Ընդհանուր առմամբ, վեց փորձ կատարած հարձակվողը (երեքը՝ բանկոմատով և երեքը՝ վճարային տերմինալով) ուրիշի քարտի PIN-ը գուշակելու 2%-ից քիչ հավանականություն ունի:

Գործոն	Օրինակ	ցնցել քեզ	iPhone	Հարցազրույց
*Ամսաթվեր*
DDMM	2311	5.26	1.38	3.07
DMYY	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
mmyy	0683	0.67	0.20	0.94
YYYY	1984	33.39	7.12	4.95
Ընդամենը		58.57	24.51	22.76
*Ստեղնաշարի նախշ*
կապված	6351	1.52	4.99	-
քառակուսի	1425	0.01	0.58	-
անկյունները	9713	0.19	1.06	-
Խաչ	8246	0.17	0.88	-
անկյունագծային գիծ	1590	0.10	1.36	-
հորիզոնական գիծ	5987	0.34	1.42	-
բառ	5683	0.70	8.39	-
ուղղահայաց գիծ	8520	0.06	4.28	-
Ընդամենը		3.09	22.97	8.96
*թվային օրինակ*
ավարտվում է 69-ով	6869	0.35	0.57	-
միայն 0-3 թվեր	2000	3.49	2.72	-
միայն 0-6 թվեր	5155	4.66	5.96	-
կրկնվող զույգեր	2525	2.31	4.11	-
նույն թվերը	6666	0.40	6.67	-
նվազող հաջորդականություն	3210	0.13	0.29	-
աճող հաջորդականություն	4567	3.83	4.52	-
Ընդամենը		15.16	24.85	4.60
*Պատահական թվերի հավաքածու*		23.17	27.67	63.68

Ամեն ինչ լավ կլիներ, բայց, ցավոք, հարցվածների մի զգալի մասը (23%) ընտրում է PIN կոդ՝ ամսաթվի տեսքով, և նրանց գրեթե մեկ երրորդն օգտագործում է իր ծննդյան ամսաթիվը։ Սա էական տարբերություն է տալիս, քանի որ հարցվածների գրեթե բոլորը (99%) պատասխանել են, որ իրենց դրամապանակում պահում են տարբեր նույնականացման քարտեր՝ բանկային քարտերով, որոնց վրա նշված է այս ամսաթիվը։ Եթե հարձակվողը գիտի քարտատիրոջ ծննդյան օրը, ապա գրագետ մոտեցման դեպքում PIN-կոդը գուշակելու հավանականությունը հասնում է 9%-ի:

Թոփ 100 ամենահայտնի PIN կոդերը

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S.Գործնականում, իհարկե, հարձակվողի համար շատ ավելի հեշտ է լրտեսել ձեր PIN-ը, քան կռահել այն: Բայց դուք կարող եք նաև պաշտպանվել ձեզ հայացքից, նույնիսկ, թվում է, անելանելի իրավիճակում.

Կոմբինատորիկան մաթեմատիկայի մի ճյուղ է, որն ուսումնասիրում է հարցեր այն մասին, թե տվյալ առարկաներից քանի տարբեր համակցություններ կարող են կատարվել որոշակի պայմաններից: Կոմբինատորիկայի հիմունքները շատ կարևոր են պատահական իրադարձությունների հավանականությունը գնահատելու համար, քանի որ. հենց նրանք են հնարավորություն տալիս հաշվարկել իրադարձությունների զարգացման տարբեր սցենարների սկզբունքորեն հնարավոր թիվը։

Հիմնական կոմբինատորիկայի բանաձև

Թող լինեն k տարրերի խմբեր և i-րդ խումբբաղկացած է n i տարրերից։ Յուրաքանչյուր խմբից ընտրենք մեկ տարր։ Հետո ընդհանուր թիվը N եղանակները, որոնցով կարելի է նման ընտրություն կատարել, որոշվում է N=n 1 *n 2 *n 3 *...*n k հարաբերությամբ:

Օրինակ 1Եկեք բացատրենք այս կանոնը պարզ օրինակով. Թող լինեն տարրերի երկու խումբ, առաջին խումբը բաղկացած է n 1 տարրից, իսկ երկրորդը՝ n 2 տարրից։ Քանի՞ տարբեր զույգ տարրեր կարելի է պատրաստել այս երկու խմբերից, որպեսզի զույգը պարունակի մեկ տարր յուրաքանչյուր խմբից: Ենթադրենք, մենք վերցրել ենք առաջին տարրը առաջին խմբից և, առանց այն փոխելու, անցել ենք բոլոր հնարավոր զույգերով՝ փոխելով միայն երկրորդ խմբի տարրերը։ Այս տարրի համար կա n 2 նման զույգ։ Այնուհետև առաջին խմբից վերցնում ենք երկրորդ տարրը և դրա համար կազմում ենք բոլոր հնարավոր զույգերը։ Կլինի նաև n 2 նման զույգ։ Քանի որ առաջին խմբում կա ընդամենը n 1 տարր, կլինեն n 1 *n 2 հնարավոր տարբերակներ:

Օրինակ 2Քանի՞ եռանիշ զույգ կարելի է կազմել 0, 1, 2, 3, 4, 5, 6 թվանշաններից, եթե թվանշանները կարելի է կրկնել:
Լուծում: n 1 \u003d 6 (քանի որ դուք կարող եք ցանկացած թվանշան վերցնել 1, 2, 3, 4, 5, 6-ից որպես առաջին նիշ), n 2 \u003d 7 (քանի որ կարող եք 0-ից ցանկացած թվանշան վերցնել որպես երկրորդ նիշ , 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (քանի որ դուք կարող եք ցանկացած թվանշան վերցնել 0, 2, 4, 6-ից որպես երրորդ թվանշան):
Այսպիսով, N=n 1 *n 2 *n 3 =6*7*4=168:

Այն դեպքում, երբ բոլոր խմբերը բաղկացած են նույն թվով տարրերից, այսինքն. n 1 =n 2 =...n k =n մենք կարող ենք ենթադրել, որ յուրաքանչյուր ընտրություն կատարվում է նույն խմբից, և ընտրությունից հետո տարրը վերադառնում է խումբ: Այնուհետև ընտրության բոլոր եղանակների թիվը հավասար է n k-ի: Ընտրության այս եղանակը կոմբինատորիկայի մեջ կոչվում է վերադարձի նմուշներ.

Օրինակ 3Քանի՞ քառանիշ թիվ կարելի է կազմել 1, 5, 6, 7, 8 թվերից:
Լուծում.Քառանիշ թվի յուրաքանչյուր թվի համար կա հինգ հնարավորություն, ուստի N=5*5*5*5=5 4 =625։

Դիտարկենք n տարրից բաղկացած բազմություն: Այս բազմությունը կոմբինատորիկայի մեջ կոչվում է ընդհանուր բնակչությունը.

n տարրերից տեղաբաշխումների քանակը m-ով

Սահմանում 1.Տեղավորում սկսած nտարրեր ըստ մկոմբինատորիկայի մեջ կոչվում է ցանկացած պատվիրված հավաքածու-ից մՏարբեր տարրեր, որոնք ընտրվել են ընդհանուր բնակչությունից nտարրեր.

Օրինակ 4Երեք տարրերի (1, 2, 3) տարբեր դասավորվածությունները երկու-երկու կկազմեն (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3): , 2). Տեղադրումները կարող են տարբերվել միմյանցից և՛ տարրերով, և՛ իրենց հերթականությամբ:

Կոմբինատորիկայի մեջ տեղաբաշխումների քանակը նշվում է A n m-ով և հաշվարկվում է բանաձևով.

Մեկնաբանություն: n՛=1*2*3*...*n (կարդացեք՝ «en factorial»), բացի այդ, ենթադրվում է, որ 0՛=1։

Օրինակ 5. Քանի՞ երկնիշ թիվ կա, որոնցում տասնյակների և միավորների թվանշանները տարբեր են և կենտ:
Լուծում:որովհետեւ կան հինգ կենտ թվանշաններ, մասնավորապես՝ 1, 3, 5, 7, 9, ապա այս խնդիրը կրճատվում է հինգ տարբեր թվանշաններից երկուսը երկու տարբեր դիրքերում ընտրելով և դնելով, այսինքն. տրված թվերը կլինեն.

Սահմանում 2. Համադրություն-ից nտարրեր ըստ մկոմբինատորիկայի մեջ կոչվում է ցանկացած չպատվիրված հավաքածու-ից մ տարբեր տարրերընտրված բնակչության ընդհանուր թվից nտարրեր.

Օրինակ 6. Կոմպլեկտի համար (1, 2, 3) համակցություններն են (1, 2), (1, 3), (2, 3):

m-ով n տարրերի համակցությունների թիվը

Համակցությունների թիվը նշվում է C n m-ով և հաշվարկվում է բանաձևով.

Օրինակ 7Քանի՞ ձևով կարող է ընթերցողը ընտրել վեց գրքերից երկուսը:

Լուծում:Ճանապարհների թիվը հավասար է վեց գրքերի երկուսի համակցությունների թվին, այսինքն. հավասար է.

n տարրերի փոխարկումներ

Սահմանում 3. Փոխադարձություն-ից nտարրերը կոչվում են ցանկացած պատվիրված հավաքածուայս տարրերը.

Օրինակ 7ա.Երեք տարրերից (1, 2, 3) բաղկացած բազմության բոլոր հնարավոր փոխարկումներն են՝ (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2)։

n տարրերի տարբեր փոխարկումների թիվը նշվում է P n-ով և հաշվարկվում է P n =n! բանաձևով:

Օրինակ 8Քանի՞ ձևով կարելի է դարակաշարում անընդմեջ դասավորել տարբեր հեղինակների յոթ գիրք:

Լուծում:այս խնդիրը յոթ տարբեր գրքերի փոխակերպումների քանակի մասին է: Գոյություն ունեն գրքերը դասավորելու P 7 =7!=1*2*3*4*5*6*7=5040 եղանակ:

Քննարկում.Մենք տեսնում ենք, որ հնարավոր համակցությունների թիվը կարելի է հաշվարկել տարբեր կանոններով (փոխադարձություններ, համակցություններ, տեղաբաշխումներ), և արդյունքը տարբեր կլինի, քանի որ. հաշվելու սկզբունքը և բանաձևերն իրենք տարբեր են։ Ուշադիր նայելով սահմանումներին՝ կարող եք տեսնել, որ արդյունքը կախված է մի քանի գործոններից միաժամանակ:

Նախ, քանի տարրից մենք կարող ենք միավորել դրանց հավաքածուները (որքան մեծ է տարրերի ընդհանուր պոպուլյացիան):

Երկրորդ, արդյունքը կախված է նրանից, թե ինչ չափի տարրեր են մեզ անհրաժեշտ:

Ի վերջո, կարևոր է իմանալ, թե արդյոք մեզ համար նշանակալի է հավաքածուի տարրերի հերթականությունը: Վերջին գործոնը բացատրենք հետևյալ օրինակով.

Օրինակ 9Ծնողական ժողովին 20 հոգի է։ Քանի՞ տարբեր տարբերակ կա ծնողական հանձնաժողովի կազմի համար, եթե այն պետք է ներառի 5 հոգի:
Լուծում:Այս օրինակում մեզ չի հետաքրքրում հանձնաժողովի ցուցակի անունների հերթականությունը։ Եթե դրա բաղադրության մեջ ի հայտ են գալիս նույն մարդիկ, ապա մեզ համար իմաստային առումով սա նույն տարբերակն է։ Հետևաբար, թիվը հաշվարկելու համար մենք կարող ենք օգտագործել բանաձևը համակցություններ 20 տարրից՝ 5.

Գործերը տարբեր կլինեն, եթե հանձնաժողովի յուրաքանչյուր անդամ ի սկզբանե պատասխանատու է աշխատանքի որոշակի ոլորտի համար: Հետո, հանձնաժողովի նույն աշխատավարձով, ներսում հնարավոր է 5-ը։ տարբերակները փոխակերպումներայդ հարցը. Տարբեր (ինչպես կազմի, այնպես էլ պատասխանատվության ոլորտի) տարբերակների քանակը այս դեպքում որոշվում է թվով. տեղաբաշխումներ 20 տարրից՝ 5.

Առաջադրանքներ ինքնաստուգման համար
1. Քանի՞ եռանիշ զույգ թվեր կարելի է կազմել 0, 1, 2, 3, 4, 5, 6 թվերից, եթե թվերը կարելի է կրկնել։
Որովհետեւ երրորդ տեղում զույգ թիվը կարող է լինել 0, 2, 4, 6, այսինքն. չորս նիշ. Երկրորդ տեղը կարող է լինել յոթ թվանշաններից որևէ մեկը: Առաջին տեղը կարող է լինել յոթ թվանշաններից որևէ մեկը, բացի զրոյից, այսինքն. 6 հնարավորություն. Արդյունք =4*7*6=168:
2. Քանի՞ հնգանիշ թիվ կա, որը նույն կերպ է կարդացվում ձախից աջ և աջից ձախ:
Առաջին տեղը կարող է լինել ցանկացած թիվ, բացի 0-ից, այսինքն. 9 հնարավորություն. Երկրորդ տեղը կարող է լինել ցանկացած թիվ, այսինքն. 10 հնարավորություն. Երրորդ տեղը կարող է լինել նաև ցանկացած թիվ, այսինքն. 10 հնարավորություն. Չորրորդ և հինգերորդ թվանշանները կանխորոշված են, դրանք համընկնում են առաջինի և երկրորդի հետ, հետևաբար, այդպիսի թվերի թիվը 9*10*10=900 է։
3. Դասարանում կա տասը առարկա և օրական հինգ դաս: Քանի՞ եղանակով կարող եք մեկ օրվա գրաֆիկ կազմել:

4. Քանի՞ եղանակով կարելի է ընտրել 4 պատվիրակ համաժողովի համար, եթե խմբում կա 20 հոգի:

n = C 20 4 = (20!)/(4!*(20-4)!)=(16*17*18*19*20)/((1*2*3*4)*(16! ))=(17*18*19*20)/(1*2*3*4)=4845։
5. Քանի՞ ձևով կարելի է ութ տարբեր տառեր դնել ութ տարբեր ծրարների մեջ, եթե յուրաքանչյուր ծրարի մեջ դրված է միայն մեկ տառ:
Առաջին ծրարի մեջ կարող եք տեղադրել ութ տառերից 1-ը, մնացած յոթ տառերից երկրորդում, վեցից երրորդում և այլն։ n = 8! = 1*2*3*4*5*6*7*8 = 40320։
6. Երեք մաթեմատիկոսից և տասը տնտեսագետից անհրաժեշտ է կազմել հանձնաժողով՝ բաղկացած երկու մաթեմատիկոսից և վեց տնտեսագետից։ Քանի՞ եղանակով կարելի է դա անել:

ԿՈՄԲԻՆԱՏՈՐԻԿԱ

Կոմբինատորիկան մաթեմատիկայի մի ճյուղ է, որն ուսումնասիրում է որոշ հիմնական բազմությունից տարրեր ընտրելու և դասավորելու խնդիրները՝ համաձայն տրված կանոնների։ Հավանականության տեսության մեջ օգտագործվում են կոմբինատորիկայի բանաձևեր և սկզբունքներ՝ հավանականությունը հաշվարկելու համար պատահական իրադարձություններև, համապատասխանաբար, բաշխման օրենքների ձեռքբերում պատահական փոփոխականներ. Սա, իր հերթին, հնարավորություն է տալիս ուսումնասիրել զանգվածային պատահական երևույթների օրենքները, ինչը շատ կարևոր է բնության և տեխնիկայի մեջ դրսևորվող վիճակագրական օրենքների ճիշտ ընկալման համար։

Գումարման և բազմապատկման կանոնները կոմբինատորիկայի մեջ

Գումարի կանոն. Եթե A և B գործողությունները միմյանց բացառող են, և A գործողությունը կարող է կատարվել m եղանակներով, իսկ B-ն՝ n եղանակներով, ապա այս գործողություններից որևէ մեկը (կամ A կամ B) կարող է իրականացվել n + m եղանակներով:

Օրինակ 1

Դասարանում սովորում է 16 տղա և 10 աղջիկ։ Քանի՞ եղանակով կարող է նշանակվել մեկ սպասավոր:

Լուծում

Դուք կարող եք նշանակել կամ տղա, կամ աղջիկ հերթապահ, այսինքն. 16 տղաներից կամ 10 աղջիկներից որևէ մեկը կարող է հերթապահել:

Ըստ գումարի կանոնի՝ ստանում ենք, որ մեկ հերթապահին կարելի է նշանակել 16+10=26 եղանակ։

Ապրանքի կանոն. Թող պահանջվի հաջորդաբար k գործողություններ կատարել: Եթե առաջին գործողությունը կարող է կատարվել n 1 եղանակով, երկրորդ գործողությունը՝ n 2 եղանակով, երրորդը՝ n 3 եղանակով, և այսպես շարունակ մինչև k-րդ գործողությունը, որը կարող է կատարվել n k եղանակով, ապա բոլոր k գործողությունները միասին կարող են լինել. կատարեց՝

ուղիները.

Օրինակ 2

Դասարանում սովորում է 16 տղա և 10 աղջիկ։ Քանի՞ եղանակով կարող են նշանակվել երկու սպասավորներ:

Լուծում

Առաջին հերթապահը կարող է լինել կամ տղա, կամ աղջիկ։ Որովհետեւ դասարանում կա 16 տղա և 10 աղջիկ, ապա առաջին հերթապահին կարող եք նշանակել 16 + 10 = 26 եղանակով։

Առաջին հերթապահին ընտրելուց հետո մնացած 25 հոգուց կարող ենք ընտրել երկրորդին, այսինքն. 25 եղանակ.

Բազմապատկման թեորեմով կարելի է ընտրել երկու ուղեկցող 26*25=650 եղանակով։

Համակցություններ առանց կրկնության. Համակցություններ կրկնություններով

Կոմբինատորիկայի դասական խնդիրը առանց կրկնությունների համակցությունների քանակի խնդիրն է, որի բովանդակությունը կարող է արտահայտվել հարցով. որքան ուղիները կարող է ընտրել մ–ից n տարբեր իրեր ?

Օրինակ 3

Դուք պետք է ընտրեք նվեր 10 տարբեր գրքերից 4-ը: Քանի՞ եղանակով կարելի է դա անել:

Լուծում

Մենք պետք է ընտրենք 10 գրքից 4-ը, իսկ ընտրության հերթականությունը նշանակություն չունի։ Այսպիսով, դուք պետք է գտնեք 10 տարրերի համակցությունների քանակը 4-ով:

Դիտարկենք կրկնություններով համակցությունների քանակի խնդիրը. n-ից յուրաքանչյուրում կան r նույնական օբյեկտներ: տարբեր տեսակներ; որքան ուղիները կարող է ընտրել m() of Սրանք (n*r) իրե՞ր:

Օրինակ 4

Հրուշակեղենի խանութում վաճառվում էր 4 տեսակի թխվածք՝ նապոլեոն, էկլեր, բլիթ և աղվափնջիկ։ Քանի՞ եղանակով կարելի է գնել 7 տորթ:

Լուծում

Որովհետեւ 7 տորթերի մեջ կարող են լինել նույն բազմազանության տորթեր, այնուհետև 7 տորթերի գնման եղանակների քանակը որոշվում է 7-ից 4-ը կրկնող համակցությունների քանակով:

Տեղադրումներ առանց կրկնության. Տեղադրումներ՝ կրկնություններով

Կոմբինատորիկայի դասական խնդիրը առանց կրկնությունների տեղաբաշխումների քանակի խնդիրն է, որի բովանդակությունը կարող է արտահայտվել հարցով. որքան ուղիները կարող է ընտրել և տեղ վրա մ տարբեր տեղերը մ–ից n տարբեր իրեր?

Օրինակ 5

Որոշ թերթ ունի 12 էջ։ Այս թերթի էջերին անհրաժեշտ է տեղադրել չորս լուսանկար։ Քանի՞ ձևով կարելի է դա անել, եթե թերթի ոչ մի էջ չպետք է պարունակի մեկից ավելի լուսանկար:

Լուծում.

Այս խնդրի դեպքում մենք ոչ թե պարզապես ընտրում ենք լուսանկարներ, այլ դրանք տեղադրում թերթի որոշակի էջերում, և թերթի յուրաքանչյուր էջ պետք է պարունակի ոչ ավելի, քան մեկ լուսանկար: Այսպիսով, խնդիրը վերածվում է դասական խնդրի՝ 12 տարրերից առանց կրկնությունների 4 տարրով որոշելու տեղաբաշխումների քանակը.

Այսպիսով, 12 էջի վրա 4 լուսանկար կարելի է դասավորել 11880 եղանակով։

Նաև դասական խնդիրկոմբինատորիկան կրկնություններով տեղաբաշխումների քանակի խնդիրն է, որի բովանդակությունը կարող է արտահայտվել հարցով. որքան ուղիները կարող է դուբբանակ և տեղ վրա մ տարբեր տեղերը մ–ից n իրերՀետռեդի որը կա նույնը?

Օրինակ 6

Տղան նկարահանման հրապարակից մեկնել էր սեղանի խաղՆամականիշեր 1, 3 և 7 թվերով։ Նա որոշեց օգտագործել այս նամականիշները բոլոր գրքերի վրա հնգանիշ թվեր դնելու համար՝ կատալոգ կազմելու համար։ Քանի՞ տարբեր հնգանիշ թիվ կարող է կազմել տղան:

Փոխակերպումներ առանց կրկնության. Փոխակերպումներ՝ կրկնություններով

Կոմբինատորիկայի դասական խնդիրը առանց կրկնության փոխատեղումների քանակի խնդիրն է, որի բովանդակությունը կարող է արտահայտվել հարցով. որքան ուղիները կարող է տեղ n բազմազան իրեր վրա n տարբեր տեղերը?

Օրինակ 7

Քանի՞ քառատառ «բառ» կարելի է կազմել «ամուսնություն» բառի տառերից:

Լուծում

Ընդհանուր հավաքածուն «ամուսնություն» բառի 4 տառ է (բ, փ, ա, կ): «Բառերի» թիվը որոշվում է այս 4 տառերի փոխարկումներով, այսինքն.

Այն դեպքում, երբ ընտրված n տարրերի մեջ կան նույնը (ընտրություն վերադարձով), կրկնություններով փոխատեղումների քանակի խնդիրը կարող է արտահայտվել հարցով. Քանի՞ ձևով կարող է n առարկա վերադասավորվել n տարբեր տեղերում, եթե n առարկաների մեջ կան k տարբեր տեսակներ (k< n), т. е. есть одинаковые предметы.