Първото място в реда може да бъде всеки от N елемента, следователно има N опции. На второ място - всяко, с изключение на това, което вече е използвано за първо място. Следователно за всяка от вече намерените N опции има (N - 1) опции за второ място и общият брой комбинации става N*(N - 1).
Същото може да се повтори и за останалите елементи от серията. За последното място остава само една опция - последният останал елемент. За предпоследния има два варианта и т.н.
Следователно, за поредица от N неповтарящи се елемента, възможните пермутации са равни на произведението на всички цели числа от 1 до N. Това произведение се нарича N и N! (четете „en factorial“).

В предишния случай количеството възможни елементии броят на местата в реда съвпадаше и техният брой беше равен на N. Но е възможна ситуация, когато в реда по-малко местаотколкото има възможни елементи. С други думи, броят на елементите в извадката е равен на определено число M и M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
Първо може да се наложи да преброите общия брой възможни начини, който може да се използва за подреждане на M елемента от N в ред. Такива методи за поставяне.
Второ, изследователят може да се интересува от броя на начините, по които M елементи могат да бъдат избрани от N. В този случай редът на елементите вече не е важен, но всеки два варианта трябва да се различават един от друг с поне един елемент . Такива методи се наричат ​​комбинации.

За да намерите броя на разположенията на M елемента от N, можете да прибегнете до същия метод на разсъждение, както в случая с пермутациите. Все още може да има N елемента на първо място, N - 1 на второ място и т.н. Но за последното място количеството възможни вариантине е равно на единица, а на (N - M + 1), тъй като когато поставянето приключи, все още ще останат (N - M) неизползвани елементи.
Така броят на поставянията на M елемента от N е равен на произведението на всички цели числа от (N - M + 1) до N, или, което е същото, частното N!/(N - M)!.

Очевидно броят на комбинациите от M елемента от N ще бъде по-малък от броя на разположенията. За всяка възможна комбинация има М! възможните разположения в зависимост от реда на елементите на тази комбинация. Следователно, за да намерите това количество, трябва да разделите броя на разположенията на M елемента от N на N!. С други думи, броят на комбинациите от M елемента от N е равен на N!/(M!*(N - M)!).

източници:

• брой комбинации

Факториалестественото число е произведението на всички предишни естествени числа, включително самото число. Факториалнула равно на едно. Изглежда, че изчисляването на факториела на число е много просто - просто умножете всичко естествени числа, като не надвишава определения. Стойността на факториела обаче нараства толкова бързо, че някои калкулатори не могат да се справят с тази задача.

Ще ви трябва

• калкулатор, компютър

Инструкции

За да изчислите факториела на естествено число, умножете всички , които не надвишават даденото. Всяко число се брои само веднъж. Под формата на формула това може да се запише по следния начин: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, където n е естествено число, чийто факториел трябва да бъде изчислен.
0! приет равно на едно(0!=1). С нарастването на аргумента стойността на факториела се увеличава много бързо, така че обичайният (счетоводен) за факториел от 15 може да даде грешка вместо резултат.

За да изчислите факториела на голямо естествено число, вземете инженерен калкулатор. Тоест, такъв калкулатор на клавиатурата има символи математически функции(cos, sin, √). Въведете оригиналното число в калкулатора и след това щракнете върху бутона за факториел. Обикновено бутон като "n!" или подобно (вместо „n“ може да има „N“ или „x“, но удивителен знак"!" факторното обозначение трябва да присъства във всеки случай).
При големи стойностиаргумент, резултатите от изчислението започват да се показват в „експоненциална“ (експоненциална) форма. Така, например, факториел от 50 ще бъде представен във формата: 3,0414093201713378043612608166065e+64 (или подобен). За да получите резултата от изчисленията в обичайната форма, добавете толкова нули към числото, показано преди символа „e“, колкото са посочени след „e+“ (ако, разбира се, има достатъчно място).

В комбинаториката те изучават въпроси за това колко комбинации от определен тип могат да бъдат направени от дадени обекти (елементи).

Раждането на комбинаториката като клон се свързва с трудовете на Б. Паскал и П. Ферма върху теорията хазарт. Голям принос за развитието на комбинаторните методи направи G.V. Лайбниц, Й. Бернули и Л. Ойлер.

Френският философ, писател, математик и физик Блез Паскал (1623–1662) проявява рано своите изключителни математически способности. Обхватът на математическите интереси на Паскал беше много разнообразен. Паскал доказа едно нещо
от основните теореми на проективната геометрия (теорема на Паскал), проектира сумираща машина (добавяща машина на Паскал), даде метод за изчисляване на биномни коефициенти (триъгълник на Паскал), беше първият, който точно дефинира и приложи метода на математическата индукция за доказателство, направи значителна стъпка в развитието на безкрайно малкия анализ, изигра важна роля в появата на теорията на вероятностите. В хидростатиката Паскал установи нейния основен закон (закон на Паскал). „Писма до един провинциалец“ на Паскал е шедьовър на френската класическа проза.

Готфрид Вилхелм Лайбниц (1646–1716) е немски философ, математик, физик и изобретател, юрист, историк и лингвист. В математиката, заедно с И. Нютон, той развива диференциалното и интегралното смятане. Той направи важен принос в комбинаториката. Името му се свързва по-специално с проблемите на теорията на числата.

Готфрид Вилхелм Лайбниц нямаше особено впечатляваща външност и затова създаваше впечатлението за доста обикновен човек. Един ден в Париж той влиза в книжарница с надеждата да си купи книга от философ, когото познава. Когато посетител попита за тази книга, продавачът на книги, след като го прегледа от главата до петите, подигравателно каза: „Защо ви е нужна? Наистина ли сте в състояние да четете такива книги? Преди ученият да успее да отговори, самият автор на книгата влезе в магазина с думите: „Поздрави и уважение към Великия Лайбниц!“ Продавачът не можа да разбере, че това наистина е известният Лайбниц, чиито книги бяха в голямо търсене сред учените.

В бъдеще важна роля ще играе следното

Лема.Пуснете в набор от елементи, а в набор - елементи. Тогава броят на всички отделни двойки където ще бъде равен на .

Доказателство.Наистина с един елемент от множество можем да направим толкова различни двойки, а общо в множество от елементи.

Разположения, пермутации, комбинации

Нека имаме набор от три елемента. По какви начини можем да изберем два от тези елементи? .

Определение.Подредбите на набор от различни елементи по елементи са комбинации, които са съставени от дадени елементи по > елементи и се различават или по самите елементи, или по реда на елементите.

Броят на всички подреждания на набор от елементи по елементи се обозначава с (от началната буква на френската дума “arrangement”, което означава подреждане), където и .

Теорема.Броят на разположенията на набор от елементи по елементи е равен на

Доказателство.Да кажем, че имаме елементи. Нека са възможни разположения. Ние ще изградим тези разположения последователно. Първо, нека дефинираме първия елемент за разположение. От даден набор от елементи може да се избере по различни начини. След като изберете първия елемент, все още има начини да изберете втория елемент и т.н. Тъй като всеки такъв избор дава ново разположение, всички тези избори могат свободно да се комбинират един с друг. Следователно имаме:

Пример.По колко начина едно знаме може да бъде съставено от три хоризонтални ивици? различни цветове, ако има материал от пет цвята?

Решение.Необходимият брой трилентови флагове:

Определение.Пермутацията на набор от елементи е подреждането на елементите в определен ред.

По този начин всички различни пермутации на набор от три елемента са

Посочен е броят на всички пермутации на елементи (от началната буква на френската дума "permutation", което означава "пермутация", "движение"). Следователно броят на всички различни пермутации се изчислява по формулата

Пример.По колко начина могат да се поставят топовете на шахматната дъска, така че да не се нападат един друг?

Решение.Необходимият брой топове

По дефиниция!

Определение.Комбинации от различни елементи по елементи са комбинации, които са съставени от дадени елементи по елементи и се различават поне по един елемент (с други думи, -елементни подмножества на даден набор от елементи).

Както можете да видите, при комбинации, за разлика от разположенията, редът на елементите не се взема предвид. Броят на всички комбинации от елементи, елементи във всяка, е посочен (от началната буква на френската дума „combinasion“, което означава „комбинация“).

Числа

Всички комбинации от комплект от две са .

Свойства на числата (\sf C)_n^k

Наистина, всяко подмножество от -елементи на дадено множество от -елементи съответства на едно и само едно подмножество от -елементи на същото множество.

Наистина можем да изберем подмножества от елементи по следния начин: фиксираме един елемент; броят на -елементните подмножества, съдържащи този елемент, е равен на ; броят на -елементните подмножества, които не съдържат този елемент, е равен на .

Триъгълник на Паскал

В този триъгълник крайните числа във всеки ред са равни на 1, а всяко неекстремно число е равно на сумата от двете числа над него от предходния ред. По този начин този триъгълник ви позволява да изчислявате числа.

Теорема.

Доказателство.Нека разгледаме набор от елементи и решим следната задача по два начина: колко последователности могат да бъдат направени от елементите на даден
множества, във всяко от които никой елемент не се среща два пъти?

1 начин. Избираме първия член на редицата, след това втория, третия и т.н. член

Метод 2. Нека първо изберем елементи от дадено множество и след това да ги подредим в някакъв ред

Умножете числителя и знаменателя на тази дроб по:

Пример.По колко начина можете да изберете 5 числа от 36 в играта „Спортлото”?

Необходим брой начини

Задачи.

1. Регистрационните номера на автомобила се състоят от 3 букви от руската азбука (33 букви) и 4 цифри. Колко различни регистрационни номера има?
2. На пианото има 88 клавиша. По колко начина можете да произведете последователно 6 звука?
3. Колко шестцифрени числа има, които се делят на 5?
4. По колко начина могат да се поставят 7 различни монети в три джоба?
5. Колко петцифрени числа можете да направите, които имат цифрата 5 в десетичния си запис поне веднъж?
6. По колко начина могат да седнат 20 души? кръгла маса, считайки методите за еднакви, ако могат да се получат един от друг чрез движение в кръг?
7. Колко петцифрени числа има, които се делят на 5 и не съдържат еднакви цифри?
8. Върху карирана хартия със страна на клетката 1 cm е начертана окръжност с радиус 100 cm, която не минава през върховете на клетките и не докосва страните на клетките. Колко клетки може да пресече тази окръжност?
9. По колко начина могат да се подредят числата в редица, така че числата да са съседни и във възходящ ред?
10. Колко петцифрени числа могат да бъдат направени от цифри, ако всяка цифра може да се използва само веднъж?
11. От думата ROT, чрез пренареждане на буквите, можете да получите следните думи: TOP, ORT, OTR, TRO, RTO. Те се наричат ​​анаграми. Колко анаграми можете да съставите от думата ЛОГАРИТЪМ?
12. Да се ​​обадим разделянеестествено число, представянето му като сбор от естествени числа. Ето, например, всички дялове на едно число:

Разделите се считат за различни, ако се различават или по номера, или по реда на техните условия.

Колко различни разделяния на число на членове има?
13. Колко са трицифрените числа с ненарастващ ред на цифрите?
14. Колко са четирицифрените числа с ненарастващ ред на цифрите?
15. По колко начина могат да се настанят 17 души в редица, така че да застанат един до друг?
16. момичетата и момчетата се настаняват произволно в ред седалки. По колко начина могат да бъдат настанени така, че две момичета да не седят едно до друго?
17. момичетата и момчетата се настаняват произволно в ред седалки. По колко начина могат да се настанят така, че всички момичета да седнат едно до друго?

Нека преброим в MS EXCEL броя на комбинациите от n елемента по k. Използвайки формули, показваме всички опции за комбинация на листа ( английски преводтермин: Комбинации без повторение).

Комбинации от n различни елемента от k елемента са комбинации, които се различават в поне един елемент. Например, по-долу са ВСИЧКИ комбинации от 3 елемента, взети от набор, състоящ се от 5 елемента (1; 2; 3; 4; 5):

(1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5)

Забележка: Това е статия за преброяване на броя на комбинациите с помощта на MS EXCEL. Теоретични основиПрепоръчваме да го прочетете в специализиран учебник. Научаването на комбинации от тази статия е лоша идея.

Разлика между комбинации и разположения

Показване на всички комбинации от комбинации

В примерния файл се създават формули за показване на всички комбинации за дадени n и k.

Като посочим броя на елементите на множеството (n) и броя на елементите, които избираме от него (k), с помощта на формули можем да изведем всички комбинации.

Задача

Един автовоз може да транспортира 4 коли. Необходимо е да транспортирате 7 различни автомобила (LADA Granta, Hyundai Solaris, KIA Rio, Рено Дъстър, Лада Калина, Фолксваген Поло, Лада Ларгус). По колко различни начина може да се напълни първият автовоз? Конкретното място на автомобила в автовоза не е важно.

Трябва да определим броя Комбинации 7 коли на 4 места на автовоз. Тези. n=7 и k=4. Оказва се, че има 35 такива опции =NUMCOMB(7,4).

За да улесня навигацията в материала, ще добавя съдържанието на тази тема:

Въведение. Комплекти и селекции.

В тази тема ще разгледаме основните понятия на комбинаториката: пермутации, комбинации и поставяния. Нека да разберем тяхната същност и формули, по които можете да намерите тяхното количество.

За да работим, се нуждаем от допълнителна информация. Нека започнем с такава фундаментална математическа концепция като набор. Понятието множество беше разгледано подробно в темата "Понятието множество. Методи за дефиниране на множества".

Много разказотносно комплектите: показване\скриване

Накратко: наборът е колекция от обекти. Запишете множествата във фигурни скоби. Редът, в който са записани елементите, няма значение; не се допускат повторения на елементи. Например наборът от цифри на числото 11115555999 ще бъде: $\(1,5,9\)$. Наборът от съгласни в думата "тигърче" е: $\(t, g, r, n, k\)$. Нотацията $5\in A$ означава, че елемент 5 принадлежи на множеството $A=\(1,5,9 \)$. Броят на елементите в едно крайно множество се нарича мощностот това множество и означете $|A|$. Например, за набор $A=\(1,5,9 \)$, съдържащ 3 елемента, имаме: $|A|=3$.

Да разгледаме определено непразно крайно множество $U$, чиято мощност е $n$, $|U|=n$ (т.е. множеството $U$ има $n$ елемента). Нека въведем понятие като проба(някои автори го наричат ​​кортеж). Под извадка от обем $k$ от $n$ елемента (съкратено като $(n,k)$-извадка) имаме предвид набор от елементи $(a_1, a_2,\ldots, a_k)$, където $a_i\in U$. Селекцията се нарича подредена, ако редът на нейните елементи е определен. Две подредени проби, които се различават само по реда на елементите, са различни. Ако редът на елементите на извадката не е значим, тогава извадката се нарича неподредена.

Имайте предвид, че дефиницията на селекция не казва нищо за повторенията на елементите. За разлика от елементите на комплекта, елементите за избор могат да се повтарят.

Например, разгледайте набора $U=\(a,b,c,d,e\)$. Множеството $U$ съдържа 5 елемента, т.е. $|U|=5$. Пример без повторения може да бъде: $(a,b,c)$. Тази селекция съдържа 3 елемента, т.е. размерът на тази извадка е 3. С други думи, това е $(5,3)$-извадка.

Проба с повторения може да бъде следната: $(a,a,a,a,a,c,c,d)$. Съдържа 8 елемента, т.е. неговият обем е 8. С други думи, това е $(5,8)$-извадка.

Нека разгледаме още две $(5,3)$-проби: $(a,b,b)$ и $(b,a,b)$. Ако приемем, че нашите извадки са неподредени, тогава извадката $(a,b,b)$ е равна на извадката $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Ако приемем, че нашите проби са подредени, тогава $(a,b,b)\neq(b,a,b)$.

Нека да разгледаме друг пример, малко по-малко абстрактен:) Да предположим, че има шест бонбона в една кошница и всички те са различни. Ако свържем първия бонбон с числото 1, втория бонбон с числото 2 и т.н., тогава следният набор може да бъде свързан с бонбоните в кошницата: $U=\(1,2,3,4, 5,6\)$. Представете си, че произволно пъхаме ръката си в кошница, за да извадим три бонбона. Извадените бонбони са селекцията. Тъй като вземаме 3 бонбона от 6, получаваме (6,3)-проба. Редът, в който бонбоните са поставени в дланта, е напълно без значение, така че тази проба не е подредена. Е, и тъй като всички бонбони са различни, селекцията е без повторение. И така, в тази ситуация говорим за неподредена (6,3)-извадка без повторения.

Сега да се приближим от другата страна. Нека си представим, че сме във фабрика за производство на бонбони и в тази фабрика се произвеждат четири вида бонбони. Множеството $U$ в тази ситуация е както следва: $U=\(1,2,3,4 \)$ (всяко число е отговорно за свой вид бонбони). Сега нека си представим, че всички бонбони се изсипват в един улей, близо до който стоим. И като поставим дланите си, избираме 20 бонбона от този поток. Една шепа сладки е за проба. Има ли значение редът, в който се поставят бонбоните в шепа? Естествено, не, така че извадката не е подредена. Има само 4 вида бонбони и ние избираме двадесет броя от общия поток - повторението на сортовете е неизбежно. В същото време пробите могат да бъдат много различни: дори може да имаме всички бонбони от един и същи вид. Следователно в тази ситуация имаме работа с неподредена (4,20)-извадка с повторения.

Нека да разгледаме още няколко примера. Нека върху кубчетата са изписани различни 7 букви: к, о, н, е, д, т, а. Тези букви образуват множеството $U=\(k,o,n,f,e,t,a\)$. Да кажем, че от тези кубчета искаме да направим „думи” от 5 букви. Буквите на тези думи (например "konfe", "tenko" и т.н.) образуват (7,5)-селекции: $(k,o,n,f,e)$, $(t,e,n ,k ,o)$ и т.н. Очевидно редът на буквите в такава извадка е важен. Например думите „nokft“ и „kfton“ са различни (въпреки че се състоят от едни и същи букви), тъй като редът на буквите в тях не съвпада. В такива „думи“ няма повторения на букви, защото има само седем кубчета. И така, наборът от букви на всяка дума е подредена (7,5)-извадка без повторения.

Друг пример: правим всякакви осемцифрени числа от четири цифри 1, 5, 7, 8. Например 11111111, 15518877, 88881111 и т.н. Наборът $U$ е: $U=\(1,5,7,8\)$. Цифрите на всяко съставено число образуват (4,8)-извадка. Редът на цифрите в едно число е важен, т.е. пробата е поръчана. Повторенията са разрешени, така че тук имаме работа с подредена (4,8)-извадка с повторения.

Разположения без повторения на $n$ елемента по $k$

Поставяне без повторения на $n$ елемента по $k$ - подредена $(n,k)$-селекция без повторения.

Тъй като елементите в разглежданата извадка не могат да бъдат повторени, не можем да изберем повече елементи в извадката, отколкото са в оригиналния набор. Следователно за такива проби е вярно следното неравенство: $n≥ k$. Броят на поставянията без повторения на $n$ елемента по $k$ се определя по следната формула:

\begin(equation)A_(n)^(k)=\frac(n{(n-k)!} \end{equation} !}

Какво означава знакът "!": показване\скриване

Запис "n!" (чете се "en factorial") обозначава произведението на всички числа от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По дефиниция се приема, че $0!=1!=1$. Например, нека намерим 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Пример №1

Азбуката се състои от набор от символи $E=\(+,*,0,1,f\)$. Нека определим броя на тези думи от три знака в тази азбука, които не съдържат повтарящи се букви.

Под думи от три знака имаме предвид изрази като „+*0“ или „0f1“. Множеството $E$ има пет елемента, така че буквите на думите от три знака образуват (5,3)-селекции. Първият въпрос е: поръчани ли са тези проби или не? Думите, които се различават само по реда на буквите си, се считат за различни, така че редът на елементите в извадката е важен. Това означава, че пробата е поръчана. Втори въпрос: разрешени ли са повторения или не? Отговорът на този въпрос се дава от условието: думите не трябва да съдържат повтарящи се букви. За да обобщим: буквите на всяка дума, която отговаря на условията на проблема, образуват подредена (5,3)-извадка без повторения. С други думи, буквите на всяка дума образуват разположение без повторение на 5 елемента от 3. Ето примери за такива разположения:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Интересуваме се от общия брой на тези разположения. Съгласно формула (1) броят на поставянията без повторения на 5 елемента от 3 ще бъде както следва:

$$ A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

Тези. можете да направите 60 думи от три знака, чиито букви няма да се повтарят.

отговор: 60.

Разположения с повторения на $n$ елемента от $k$

Разпределение с повторения на $n$ елемента по $k$ - подредена $(n,k)$-селекция с повторения.

Броят на поставянията с повторения на $n$ елемента от $k$ се определя по следната формула:

\begin(equation)\bar(A)_(n)^(k)=n^k \end(equation)

Пример №2

Колко петцифрени числа могат да бъдат съставени от набора от цифри $\(5,7,2\)$?

от този комплектчисла можете да направите петцифрени числа 55555, 75222 и така нататък. Цифрите на всяко такова число образуват (3,5)-извадка: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Нека се запитаме какви са тези мостри? Първо, цифрите в числата могат да се повтарят, така че имаме работа с проби с повторения. Второ, редът на цифрите в числото е важен. Например 27755 и 77255 - различни числа. Следователно имаме работа с подредени (3,5)-проби с повторения. Намираме общия брой на тези проби (т.е. общия брой необходими петцифрени числа), използвайки формула (2):

$$ \bar(A)_(3)^(5)=3^5=243. $$

Следователно от дадените цифри могат да се съставят 243 петцифрени числа.

отговор: 243.

Пермутации без повторения на $n$ елемента

Пермутация без повторения на $n$ елемента е подредена $(n,n)$-селекция без повторения.

По същество пермутацията без повторение е специален случайпоставяне без повторения, когато размерът на извадката е равен на мощността на оригиналния набор. Броят на пермутациите без повторение на $n$ елемента се определя по следната формула:

\begin(equation)P_(n)=n! \край (уравнение)

Между другото, тази формула е лесна за получаване, ако вземете предвид, че $P_n=A_(n)^(n)$. Тогава получаваме:

$$ P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Пример №3

Във фризера има пет порции сладолед от различни компании. По колко начина можете да изберете реда, в който да се ядат?

Нека числото 1 съответства на първия сладолед, числото 2 - на втория и т.н. Ще получим набора $U=\(1,2,3,4,5\)$, който ще представлява съдържанието на фризера. Редът на хранене може да бъде както следва: $(2,1,3,5,4)$ или както следва: $(5,4,3,1,2)$. Всеки такъв набор е (5,5)-извадка. Ще бъде подредено и без повторения. С други думи, всяка такава извадка е пермутация на 5 елемента от оригиналния набор. Съгласно формула (3), общият брой на тези пермутации е както следва:

$$ P_5=5!=120. $$

Следователно има 120 поръчки за избор на ред на хранене.

отговор: 120.

Пермутации с повторения

Пермутацията с повторения е подредена $(n,k)$-извадка с повторения, в която елемент $a_1$ се повтаря $k_1$ пъти, $a_2$ се повтаря $k_2$ пъти и т.н., до последния елемент $ a_r$, което се повтаря $ k_r$ пъти. В този случай $k_1+k_2+\ldots+k_r=k$.

Общият брой на пермутациите с повторения се определя по формулата:

\begin(equation)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Пример №4

Думите са съставени въз основа на азбуката $U=\(a,b,d\)$. Колко различни думи могат да бъдат съставени от седем знака, ако в тези думи буквата „а“ трябва да се повтори 2 пъти; буквата "б" - 1 път, а буквата "г" - 4 пъти?

Ето примери за думи за търсене: "aabdddd", "daddabd" и т.н. Буквите на всяка дума образуват (3,7)-образец с повторения: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ и др. Всяка такава проба се състои от два елемента "a", един елемент "b" и четири елемента"г". С други думи, $k_1=2$, $k_2=1$, $k_3=4$. Общият брой повторения на всички символи, естествено, е равен на размера на извадката, т.е. $k=k_1+k_2+k_3=7$. Замествайки тези данни във формула (4), ще имаме:

$$ P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105. $$ !}

Следователно общият брой думи за търсене е 105.

отговор: 105.

Комбинации без повторения на $n$ елемента по $k$ всеки

Комбинация без повторения на $n$ елемента от $k$ е неподредена $(n,k)$-извадка без повторения.

Общият брой комбинации без повторения на $n$ елемента от $k$ се определя по формулата:

\begin(equation)C_(n)^(k)=\frac(n{(n-k)!\cdot k!} \end{equation} !}

Пример №5

Кошницата съдържа карти с изписани цели числа от 1 до 10. От кошницата се изваждат 4 карти и записаните на тях числа се събират. Колко различни комплекта карти могат да бъдат изтеглени от кошницата?

И така, в този проблем първоначалният набор е: $U=\(1,2,3,4,5,6,7,8,9,10\)$. От този набор избираме четири елемента (т.е. четири карти от кошницата). Номерата на изтеглените елементи образуват (10,4)-селекция. Повторенията в тази селекция не са разрешени, тъй като номерата на всички карти са различни. Въпросът е: редът, в който се избират картите, има ли значение или не? Тоест, например, извадките $(1,2,7,10)$ и $(10,2,1,7)$ равни ли са или не са равни? Тук трябва да се обърнете към условията на проблема. Картите се изваждат, за да се намери по-късно сумата на елементите. Това означава, че редът на картите не е важен, тъй като промяната на местата на термините няма да промени сумата. Например извадката $(1,2,7,10)$ и извадката $(10,2,1,7)$ ще съответстват на едно и също число $1+2+7+10=10+2+1+ 7 = $20. Извод: от условията на задачата следва, че имаме работа с неподредени проби. Тези. трябва да намерим общия брой неподредени (10,4)-проби без повторения. С други думи, трябва да намерим броя на комбинациите от 10 елемента от 4. Използваме формула (5) за това:

$$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Следователно общият брой на търсените набори е 210.

отговор: 210.

Комбинации с повторения на $n$ елемента по $k$ всеки

Комбинация с повторения на $n$ елемента от $k$ е неподредена $(n,k)$-извадка с повторения.

Общият брой комбинации с повторения на $n$ елемента от $k$ се определя по формулата:

\begin(equation)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!} \end{equation} !}

Пример №6

Представете си, че сме във фабрика за бонбони, точно до конвейер, по който се движат четири вида бонбони. Пъхаме ръцете си в този поток и изваждаме двадесет парчета. Колко различни "бонбонени комбинации" може да има в шепа?

Ако приемем, че първият тип съответства на числото 1, вторият тип - на числото 2 и т.н., тогава първоначалният набор в нашата задача е както следва: $U=\(1,2,3,4\) $. От този комплект избираме 20 елемента (т.е. същите тези 20 бонбона от поточната линия). Шепа сладкиши образуват (4,20)-проба. Естествено, ще има повторения на разновидностите. Въпросът е редът на елементите в извадката има ли значение или не? От условията на задачата следва, че редът, в който са подредени елементите, няма значение. За нас няма значение дали шепата съдържа първо 15 бонбона, а след това 4 шоколадови бонбони, или първо 4 шоколада, а след това 15 близалки. И така, имаме работа с неподредена (4,20) извадка с повторения. За да намерим общия брой на тези проби, използваме формула (6):

$$ \bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Следователно общият брой на търсените комбинации е 1771.

Комбинацията е неподреден избор на елементи от краен набор с фиксиран брой и без повторения на елементи. Различните комбинации трябва да се различават поне в един елемент, като редът на елементите няма значение. Например от набора от всички гласни латински букви(AEIOU) можете да направите 10 различни комбинации от 3 букви, образувайки следните неподредени тройки:

AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.

Интересно е да се отбележи, че от едни и същи пет букви можете да получите и 10 различни комбинации, ако ги комбинирате по 2 букви наведнъж, което прави следните неподредени двойки:

AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.

Въпреки това, ако комбинирате едни и същи гласни латински букви с 4, ще получите само следните 5 различни комбинации:

AEIO, AEIU, AIOU, EIOU, AEOU.

Като цяло, за да се обозначи броя на комбинациите от n различни елемента от m елемента, се използва следната функционална, индексна или векторна (Appel) символика:

Независимо от формата на запис, броят на комбинациите от n елемента по m елемента може да се определи с помощта на следните мултипликативни и факторни формули:

Лесно е да се провери дали резултатът от изчисленията с помощта на тези формули съвпада с резултатите от примера, обсъден по-горе с комбинации от гласни в латински букви. По-специално, при n=5 и m=3, изчисленията с помощта на тези формули ще дадат следния резултат:

В общия случай формулите за броя на комбинациите имат комбинаторно значение и са валидни за всякакви цели числа на n и m, така че n > m > 0. Ако m > n и m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Освен това е полезно да запомните следните ограничаващи брой комбинации, които могат лесно да бъдат проверени чрез директно заместване в мултипликативните и факториалните формули:

Трябва също да се отбележи, че мултипликативната формула остава валидна дори когато n е реално число, докато m все още е цяло число. Тогава обаче резултатът от изчислението с него, запазвайки формалната валидност, губи своя комбинаторен смисъл.

ИДЕНТИЧНОСТИ НА КОМБИНАЦИИ

Практическото използване на мултипликативни и факторни формули за определяне на броя на комбинациите за произволни стойности на n и m се оказва с малка производителност поради експоненциалното нарастване на факториалните продукти на техния числител и знаменател. Дори за относително малки стойности на n и m, тези продукти често надхвърлят възможностите за представяне на цели числа в съвременните изчисления и софтуерни системи. Освен това техните стойности се оказват значително по-големи от получената стойност на броя на комбинациите, която може да бъде относително малка. Например, броят на комбинациите от n=10 по m=8 елемента е само 45. Въпреки това, за да намерите тази стойност с помощта на факторната формула, първо трябва да изчислите много по-големи стойности от 10! в числителя и 8! в знаменателя:

За да премахнете отнемащите време операции за обработка на големи количества, за да определите броя на комбинациите, можете да използвате различни рекурентни отношения, които пряко следват от мултипликативните и факториалните формули. По-специално, следната рекурентна връзка следва от мултипликативната формула, която ни позволява да вземем съотношението на нейните индекси отвъд знака на броя на комбинациите:

И накрая, поддържането на индекса постоянен осигурява следната рекурентна връзка, която лесно се получава от факторната формула за броя на комбинациите:

След елементарни трансформации трите получени рекурентни отношения могат да бъдат представени в следните форми:

Ако сега съберем лявата и дясната страна на първите 2 формули и намалим резултата с n, получаваме важна рекурентна връзка, която се нарича идентичност на добавяне на комбинационни числа:

Идентичността на добавяне осигурява основно правило за повторение за ефективно определяне на броя на комбинациите за големи стойности на n и m, тъй като позволява операциите на умножение във факториалните продукти да бъдат заменени от по-простите операции на събиране и за по-малък брой комбинации. По-специално, използвайки идентичността на добавяне, вече е лесно да се определи броят на комбинациите от n=10 с m=8 елемента, което беше обсъдено по-горе, чрез извършване на следната последователност от повтарящи се трансформации:

В допълнение, няколко полезни съотношения за изчисляване на крайни суми могат да бъдат извлечени от идентичността на добавянето, по-специално формулата за сумиране чрез долен индекс, която има следната форма:

Тази връзка се получава, ако в идентичността на добавянето разширим повторението по термина с най-големия горен индекс, докато неговият долен индекс е по-голям от 0. Следният числен пример илюстрира този процес на повтарящи се трансформации:

Формулата за сумиране на долен индекс често се използва за изчисляване на сумата от степени на естествени числа. По-специално, ако приемем m=1, използвайки тази формула е лесно да се намери сумата от първите n числа от естествената серия:

друг полезна опцияформулите за сумиране могат да бъдат получени чрез разширяване на повторението на идентичността на добавяне по термина с най-малкия горен индекс. Следният числен пример илюстрира тази версия на повтарящи се трансформации:

В общия случай в резултат на такива трансформации се получава сумата от числата на комбинациите, чиито два индекса се различават с единица от съседните членове, а разликата в индексите остава постоянна (в разглеждания пример е също равно на едно). Така получаваме следната формула за сумиране и за двата индекса на комбинационните числа:

В допълнение към рекурентните отношения и формулите за сумиране, обсъдени по-горе, много други полезни идентичности за комбинационни числа са получени при комбинаторния анализ. Най-важното сред тях е идентичност на симетрията, което изглежда така:

Валидността на идентичността на симетрията може да се провери в следния пример чрез сравняване на броя на комбинациите от 5 елемента по 2 и по (5 2) = 3:

Идентичността на симетрията има очевидно комбинаторно значение, тъй като чрез определяне на броя на опциите за избор на m елемента от n елемента, тя едновременно установява броя на комбинациите от останалите (nm) неизбрани елементи. Посочената симетрия се получава незабавно чрез замяна на m с (nm) във факториалната формула за броя на комбинациите:

Числата и комбинираните идентичности се използват широко в различни области на съвременната изчислителна математика. Най-популярните им приложения обаче са свързани с бинома на Нютон и триъгълника на Паскал.

БИНОМНА ТЕОРЕМА

За извършване на различни математически трансформации и изчисления е важно да можете да представите всяка естествена степен на алгебричен бином (бином) под формата на полином. За малки степени желаният полином може лесно да се получи чрез директно умножение на биноми. По-специално, следните формули за квадрат и куб на сумата от два члена са добре известни от курса на елементарната математика:

В общия случай, за произволна степен n на бином, необходимото представяне под формата на полином се осигурява от биномната теорема на Нютон, която обявява следното равенство за вярно:

Това равенство обикновено се нарича бином на Нютон. Полиномът от дясната му страна се образува от сумата на произведенията на n члена X и Y от бинома от лявата страна, а коефициентите пред тях се наричат ​​биномни и са равни на броя на комбинациите с индекси, които се получават от техните правомощия. Като се има предвид особената популярност на биномната формула на Нютон в комбинаторния анализ, термините биномен коефициент и брой комбинации обикновено се считат за синоними.

Очевидно формулите за сумата на квадрат и куб са специални случаи на биномната теорема за n=2 и n=3, съответно. За обработка на по-високи степени (n>3) трябва да се използва биномна формула на Нютон. Приложението му за бином от четвърта степен (n=4) се демонстрира със следния пример:

Трябва да се отбележи, че биномната формула е била известна още преди Нютон на средновековните математици от арабския изток и Западна Европа. Следователно общоприетото му име не е исторически справедливо. Заслугата на Нютон е, че той обобщи тази формула за случая на произволен реален показател r, който може да приема всякакви положителни или отрицателни рационални и ирационални стойности. В общия случай такава биномна формула на Нютон има безкрайна сума от дясната страна и обикновено се записва, както следва:

Например, при положителна дробна стойност на показателя r=1/2, като се вземат предвид стойностите на биномните коефициенти, се получава следното разширение:

В общия случай биномиалната формула на Нютон за всяка експонента е специална версия на формулата на Маклорен, която дава разлагането на произволна функция в степенен ред. Нютон показа, че за |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой естествена степен r = n от дясната страна също води до крайна сума от (n+1) първи членове, тъй като всички C(n, k>n) = 0 . Ако сега зададем Z=X/Y и умножим лявата и дясната страна по Yn, получаваме версия на биномната формула на Нютон, обсъдена по-горе.

Въпреки своята универсалност, биномната теорема запазва своето комбинаторно значение само за неотрицателни цели числа на бинома. В този случай може да се използва за доказване на няколко полезни идентичности за биномни коефициенти. По-специално, по-горе бяха обсъдени формули за сумиране на числата на комбинациите по долен индекс и по двата индекса. Липсващата сумирана идентичност на горния индекс може лесно да се получи от биномната формула на Нютон, като се постави X = Y = 1 или Z = 1 в нея:

Друга полезна идентичност установява равенството на сумите от биномни коефициенти с четни и нечетни числа. Получава се веднага от биномната формула на Нютон, ако X = 1 и Y = 1 или Z = 1:

И накрая, от двете разгледани идентичности получаваме идентичността на сумата от биномни коефициенти само с четни или само с нечетни числа:

Въз основа на разгледаните тъждества и повтарящото се правило за премахване на индексите под знака на броя на комбинациите могат да се получат редица интересни зависимости. Например, ако във формулата за сумиране на горния индекс заменим n навсякъде с (n1) и премахнем индексите във всеки член, получаваме следната връзка:

Използвайки подобна техника във формулата за сумата от биномни коефициенти с четни и нечетни числа, е възможно да се докаже валидността например на следната връзка:

Друга полезна идентичност ви позволява лесно да изчислите сумата от продуктите на симетрично разположени биномни коефициенти на два бинома с произволни степени n и k, като използвате следната формула на Коши:

Валидността на тази формула следва от необходимото равенство на коефициентите за всяка степен m на променливата Z от лявата и дясната страна на следната идентична връзка:

В специалния случай, когато n=k=m, като се вземе предвид тъждеството на симетрията, се получава по-популярната формула за сумата от квадратите на биномните коефициенти:

Много други полезни идентичности за биномни коефициенти могат да бъдат намерени в обширната литература за комбинаторен анализ. Най-известното им практическо приложение обаче е свързано с триъгълника на Паскал.

ТРИЪГЪЛНИК НА ПАСКАЛ

Аритметичният триъгълник на Паскал е образуван от безкраен таблица с числа, съставен от биномни коефициенти. Редовете му са подредени по степени на биноми отгоре надолу. Във всеки ред биномните коефициенти са подредени във възходящ ред на горните индекси на съответните комбинационни числа отляво надясно. Триъгълникът на Паскал обикновено се записва или в равнобедрен, или в правоъгълен вид.

По-визуален и често срещан е равнобедреният формат, където биномните коефициенти, разположени в шахматен вид, образуват безкраен равнобедрен триъгълник. Неговият начален фрагмент за биноми до 4-та степен (n=4) има следния вид:

Като цяло, равнобедреният триъгълник на Паскал осигурява удобно геометрично правило за определяне на биномни коефициенти, което се основава на идентичността на събирането и симетрията на числовите комбинации. По-специално, според идентичността на добавяне, всеки биномен коефициент е сумата от двата коефициента на предходния ред, който е най-близо до него. Според идентичността на симетрията, равнобедреният триъгълник на Паскал е симетричен по отношение на ъглополовящата си. По този начин всяка от неговите линии е числен палиндром от биномни коефициенти. Посочените алгебрични и геометрични характеристики позволяват лесно разширяване на равнобедрения триъгълник на Паскал и последователно намиране на стойностите на биномните коефициенти на произволни степени.

Въпреки това, да учи различни свойстваТриъгълникът на Паскал е по-удобен за използване на формално по-строгия правоъгълен формат. В този формат тя се определя от долна триъгълна матрица от биномни коефициенти, където те образуват безкраен правоъгълен триъгълник. Първоначален фрагмент правоъгълен триъгълникПаскал за биноми до 9-та степен (n=9) има следната форма:

Геометрично такава правоъгълна маса се получава чрез хоризонтална деформация равнобедрен триъгълникПаскал. В резултат на това числовите серии, успоредни на страничните страни на равнобедрения триъгълник на Паскал, се превръщат във вертикали и диагонали на правоъгълния триъгълник на Паскал, а хоризонталите на двата триъгълника съвпадат. В същото време правилата за добавяне и симетрия на биномните коефициенти остават валидни, въпреки че правоъгълният триъгълник на Паскал губи визуалната симетрия, характерна за своя равнобедрен аналог. За да се компенсира това, става по-удобно формален анализразлични числени свойства на биномни коефициенти за хоризонтали, вертикали и диагонали на правоъгълния триъгълник на Паскал.

Започвайки анализа на хоризонталите на правоъгълния триъгълник на Паскал, лесно се забелязва, че сумата от елементите на всеки ред с номер n е равна на 2n в съответствие с формулата за сумиране на биноми с горен индекс. От това следва, че сумата от елементите над всяка от хоризонталните линии с номер n е равна на (2 n 1). Този резултат става съвсем очевиден, ако стойността на сумата от елементите на всеки хоризонтал се запише в двоичната бройна система. Например, за n=4 това събиране може да се запише по следния начин:

Ето още няколко интересни свойства на хоризонталите, които също са свързани със степени на две. Оказва се, че ако хоризонталното число е степен на две (n=2 k), то всички негови вътрешни елементи (с изключение на външните) са четни числа. Напротив, всички числа на хоризонтална линия ще бъдат нечетни, ако номерът й е с единица по-малко степендвойки (n=2 k 1). Валидността на тези свойства може да се провери чрез проверка на четността на вътрешните биномни коефициенти, например в хоризонталите n=4 и n=3 или n=8 и n=7.

Сега нека номерът на реда на правоъгълния триъгълник на Паскал е просто число p. Тогава всички негови вътрешни биномни коефициенти се делят на p. Това свойство е лесно да се провери за малки стойности на прости контурни числа. Например, всички вътрешни биномни коефициенти на петия хоризонтал (5, 10 и 5) очевидно се делят на 5. За да докажем, този резултат е валиден за всеки просто числохоризонтално p, трябва да напишете мултипликативната формула за неговите биномни коефициенти, както следва:

Тъй като p е просто число и следователно не се дели на m!, произведението на останалите множители на числителя на тази формула трябва да се дели на m!, за да се гарантира цяло число на биномния коефициент. От това следва, че отношението в квадратни скоби е естествено число N и желаният резултат става очевиден:

Използвайки този резултат, можем да установим, че числата на всички хоризонтали на триъгълника на Паскал, чиито вътрешни елементи се делят на дадено просто число p, са степени на p, тоест имат формата n=p k. По-специално, ако p=3, тогава простото число p разделя не само всички вътрешни елементи на ред 3, както е установено по-горе, но, например, 9-ия хоризонтал (9, 36, 84 и 126). От друга страна, в триъгълника на Паскал е невъзможно да се намери хоризонтална линия, чиито вътрешни елементи да се делят на съставно число. В противен случай числото на такава хоризонтална линия трябва да бъде същевременно степен на прости делители съставно число, на които са разделени всичките му вътрешни елементи, но по обясними причини това е невъзможно.

Разгледаните съображения ни позволяват да формулираме следния общ критерий за делимост на хоризонталните елементи на триъгълника на Паскал. Най-големият общ делител(КИМАНЕ) на всички вътрешни елементивсяка хоризонтална линия на триъгълника на Паскал с номер n е равна на простото число p, ако n=pk или 1 във всички останали случаи:

НОД(Cmn) = ( ) за всяка 0< m < n .

За да завършим анализа на хоризонталите, струва си да разгледаме още едно интересно свойство, което притежават сериите от биномни коефициенти, които ги образуват. Ако биномните коефициенти на която и да е хоризонтална линия с номер n се умножат по последователни степени на числото 10 и след това се добавят всички тези продукти, резултатът е 11 n. Официалното оправдание за този резултат е заместването на стойностите X=10 и Y=1 (или Z=1) в биномната формула на Нютон. Следният числен пример илюстрира изпълнението на това свойство за n=5:

Анализът на свойствата на вертикалите на правоъгълния триъгълник на Паскал може да започне с изучаване на индивидуалните характеристики на съставните им елементи. Формално всеки вертикал m се формира от следната безкрайна последователност от биномни коефициенти с постоянен горен индекс (m) и нарастване на долния индекс:

Очевидно при m=0 се получава редица от единици, а при m=1 се образува редица от естествени числа. При m=2 вертикалата се състои от триъгълни числа. Всяко триъгълно число може да бъде изобразено на равнина под формата на равностранен триъгълник, който е изпълнен с произволни обекти (ядра), подредени в шахматен ред. В този случай стойността на всяко триъгълно число T k определя броя на представящите ядра, а индексът показва колко реда ядра са необходими за представянето му. Например 4 начални триъгълни числа представляват следните конфигурации на съответния брой ядрени символи "@":

Трябва да се отбележи, че по подобен начин могат да се въведат в разглеждане квадратни числа S k , които се получават чрез повдигане на квадрат на естествени числа и като цяло многоъгълни фигурни числа, образувани чрез редовно запълване на правилни многоъгълници. По-специално, 4-те начални квадратни числа могат да бъдат представени по следния начин:

Връщайки се към анализа на вертикалите на триъгълника на Паскал, можем да отбележим, че следващият вертикал при m=3 е запълнен с тетраедрични (пирамидални) числа. Всяко такова число P k определя броя на ядрата, които могат да бъдат подредени във формата на тетраедър, а индексът определя колко хоризонтални триъгълни слоя от редици ядра са необходими, за да го изобразите в триизмерно пространство. В този случай всички хоризонтални слоеве трябва да бъдат представени като последователни триъгълни числа. Елементите на следните вертикали на триъгълника на Паскал за m>3 образуват серии от хипертетраедни числа, които нямат визуална геометрична интерпретация в равнината или в триизмерното пространство, но формално съответстват на многомерни аналози на триъгълни и тетраедални числа.

Въпреки че вертикалните числови редове на триъгълника на Паскал имат разглежданите индивидуални оформени характеристики, за тях е възможно да се изчислят частичните суми на стойностите на началните елементи по същия начин, като се използва формулата за сумиране на числата на комбинациите по долен индекс . В триъгълника на Паскал тази формула има следната геометрична интерпретация. Сумата от стойностите на n горните биномни коефициенти на всеки вертикал е равна на стойността на елемента на следващия вертикал, който се намира един ред по-долу. Този резултат също е в съответствие с геометричната структура на триъгълни, тетраедрични и хипертетраедрични числа, тъй като представянето на всяко такова число се състои от основни слоеве, които представляват числа от по-нисък ред. по-специално, n-ти триъгълникчислото T n може да се получи чрез сумиране на всички естествени числа, представляващи неговите линейни слоеве:

По същия начин не е трудно да се намери тетраедричното число Pn чрез изчисляване на следната сума от първите n триъгълни числа, които съставляват неговите хоризонтални основни слоеве:

В допълнение към хоризонталите и вертикалите в правоъгълния триъгълник на Паскал могат да се проследят диагонални редове от елементи, изучаването на свойствата на които също представлява известен интерес. В този случай обикновено се прави разлика между низходящи и възходящи диагонали. Диагоналите надолу са успоредни на хипотенузата на правоъгълния триъгълник на Паскал. Те се формират от серии от биномни коефициенти с нарастване на двата индекса. Поради идентичността на симетрията, низходящите диагонали съвпадат в стойностите на техните елементи със съответните вертикални редове на триъгълника на Паскал и следователно повтарят всички техни свойства, обсъдени по-горе. Посоченото съответствие може да бъде проследено чрез съвпадението на стойностите на елементите на низходящия диагонал и вертикалата с всяко число n, ако не се вземат предвид вертикалните нули:

Възходящите диагонали образуват числови серии, геометрично перпендикулярни на хипотенузата на правоъгълния триъгълник на Паскал. Те се попълват с биномни коефициенти с декремент на долния и инкремент на горния индекс. По-специално, 7-те горни възходящи диагонала образуват следното числова последователностбез нули в края:

Като цяло, възходящото диагонално число n съдържа следните биномни коефициенти, сумата от индексите на всеки от които е равна на (n1):

По силата на идентичността на добавяне за комбинационни числа, всеки диагонален елемент равно на суматадва елемента, съответстващи по индекси от двата предишни възходящи диагонала. Това позволява всеки следващ възходящ диагонал да бъде конструиран чрез сумиране по двойки на съседни хоризонтални елементи от двата предишни диагонала, безкрайно разширявайки триъгълника на Паскал по диагонала. Следният фрагмент от триъгълника на Паскал илюстрира конструкцията на възходящ диагонал номер 8 по диагонали с номера 6 и 7:

С този метод на конструиране сумата от елементите на всеки възходящ диагонал, започвайки от 3-ти, ще бъде равна на сумата от елементите на двата предишни възходящи диагонала, а първите 2 диагонала се състоят само от един елемент, стойността от които е 1. Резултатите от съответните изчисления образуват следната числова серия, според която можете да проверите валидността на разглежданото свойство на възходящите диагонали на правоъгълния триъгълник на Паскал:

Анализирайки тези числа, можете да видите, че според подобен закон се формира добре известната последователност от числа на Фибоначи, където всяко следващо число е равно на сумата от двете предходни, а първите две числа са равни на 1:

Така можем да направим следното важно заключение: диагоналните суми на елементите на триъгълника на Паскал съставляват редицата на Фибоначи. Това свойство ви позволява да зададете друго интересна функцияТриъгълник на Паскал. Разширявайки формулата на Фибоначи рекурсивно, е лесно да се докаже, че сумата от първите n числа на Фибоначи е равна на (F n+2 1).

Следователно сумата от биномните коефициенти, които запълват горните n диагонали, също е равна на (F n+2 1). От това следва, че сборът от първите n диагонала на триъгълника на Паскал е с 1 по-малък от сбора на биномните коефициенти, които стоят на неговия диагонал с число (n+2).

В заключение трябва да се отбележи, че разгледаните свойства на хоризонталите, вертикалите и диагоналите на триъгълника на Паскал не изчерпват огромното разнообразие от възможности, които свързват различни математически аспекти, които на пръв поглед нямат нищо общо. Такива необичайни свойства ни позволяват да считаме триъгълника на Паскал за една от най-съвършените числени системи, чиито възможности не могат да бъдат изброени и е трудно да се надценят.

Алгоритъмът за изчисляване на броя на комбинациите с помощта на триъгълника на Паскал е представен по-долу:

Частна функция SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Next For i = 2 To n For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Следващ Следващ SochTT = TT (n, k) Крайна функция

Ако трябва да изчислите броя на комбинациите много пъти, тогава може да е по-удобно да конструирате триъгълника на Паскал веднъж и след това да получите данни от масива.

Dim TT () Като Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) Като Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub

Първо трябва да извикате процедурата CreateTT. След това можете да получите броя на комбинациите с помощта на функцията SochTT. Когато вече не се нуждаете от триъгълника, извикайте процедурата TerminateTT. В горния код, когато извиквате функцията SochTT, ако триъгълникът все още не е завършен до необходимото ниво, тогава той се завършва с помощта на процедурата BuildTT. След това функцията получава задължителен елемент TT масив и го връща.

Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 За j = 1 До N Ако X1(j)<>0 Тогава n1 = n1 + 1 Ако n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 Изход за край Ако следващ txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub

ИЗБЕРЯВАНЕ НА КОМБИНАЦИИ ОТ ЕСТЕСТВЕНИ ЧИСЛА

За решаването на много практически проблеми е необходимо да се изброят всички комбинации с фиксирана мощност, които могат да бъдат получени от елементите на дадено крайно множество, а не просто да се определи техният брой. Като се има предвид винаги съществуващата възможност за целочислено номериране на елементите на всяко крайно множество, в повечето случаи е допустимо да се ограничим до използването на алгоритми за изброяване на комбинации от естествени числа. Най-естественият и прост от тях е алгоритъмът за изброяване на комбинации от естествени числа в лексикографски ред.

За да се опише формално този алгоритъм, е удобно да се приеме, че основното множество, всички комбинации от m елемента, от които трябва да бъдат изброени, образуват последователни естествени числа от 1 до n. Тогава всяка комбинация от m

В резултат на подреждането стойността във всяка позиция на такъв вектор от комбинации естествено се оказва ограничена по стойност отгоре и отдолу, както следва:

Лексиграфският алгоритъм последователно генерира такива комбинирани вектори, започвайки с лексиграфски най-малкия вектор, където всички позиции съдържат следните минимални възможни стойности на елементи, равни на техните индекси:

Всеки следващ комбиниран вектор се формира от текущия след сканиране на елементите му отляво надясно, за да се намери най-десният елемент, който все още не е достигнал граничната си стойност:

Стойността на такъв елемент трябва да се увеличи с 1. На всеки елемент вдясно от него трябва да се присвои възможно най-малката стойност, която е с 1 повече от съседния му отляво. След тези промени следващият вектор от комбинации ще има следния елементен състав:

По този начин следващият комбиниран вектор ще бъде лексикографски по-голям от предишния, тъй като стойностите на техните начални (j1) елементи са еднакви по стойност, а стойността на елемента на позиция j е с 1 по-голяма от тази на предишния . Посочената връзка на нарастващ лексикографски ред гарантирано ще бъде изпълнена при всички итерации на алгоритъма. Резултатът е нарастваща лексикографска последователност, която се допълва от лексикографски най-големия комбиниран вектор, където елементите във всички позиции имат следните максимални стойности:

Разглежданият лексикографски алгоритъм се илюстрира със следния пример, където е необходимо да се изброят във възходящ лексикографски ред всичките 15 комбинации от n=6 първи естествени числа по m=4 числа, т.е. всички възможни 4-елементни подмножества на главните генериращи комплект (1, 2, 3, 4 , 5, 6) от 6 елемента. Резултатите от изчислението са представени в следната таблица:

В този пример най-големите допустими стойности на числата в позициите на комбинираните вектори са съответно 3, 4, 5 и 6. За по-лесно тълкуване на резултатите, във всеки комбиниран вектор, най-десният елемент, който има все още не е достигнал максималната си стойност, е подчертано. Числовите индекси на комбинираните вектори определят номерата им в лексикографски ред. В общия случай лексиграфският номер N на всяка комбинация от n елемента по m може да се изчисли с помощта на следната формула, където по козметични причини се използва символиката на Appel за обозначаване на броя на комбинациите:

По-специално, следните изчисления, използващи тази формула за числото на комбинацията (1, 3, 4, 6) от n=6 елемента от m=4 в лексикографски ред, ще дадат резултата N=8, който съответства на примера, обсъден по-горе:

В общия случай, използвайки идентичността за сумата от числата на комбинациите за двата индекса, е възможно да се покаже, че номерът на лексикографски най-малката комбинация (1, ... i, ... m), когато се изчислява с помощта на това формулата винаги ще бъде равна на 1:

Очевидно е също, че броят на най-голямата лексикографски комбинация (m, … nm+i, … n), когато се изчисли с помощта на тази формула, ще бъде равен на броя комбинации от n елемента по m:

Формулата за изчисляване на числата на лексикографската комбинация може да се използва за решаване на обратната задача, където трябва да определите вектора на комбинацията по неговия номер в лексикографски ред. За да се реши такъв обратен проблем, той трябва да бъде написан под формата на уравнение, където всички неизвестни стойности на елементите на вектора на желаната комбинация (C 1, ... C i, ... C m ) са съсредоточени в числата на комбинациите от дясната му страна, а известната разлика L на броя на комбинациите е записана от лявата страна на n елемента всеки m и номерът на търсената комбинация N:

Решението на това уравнение се осигурява от следния „алчен“ алгоритъм, по време на чиито итерации се избират последователно стойностите на елементите на вектора на желаната комбинация. При първоначалната итерация се избира минималната възможна (в рамките на ограниченията) стойност на C 1, при която първият член от дясната страна ще има максимална стойност, която не надвишава L:

Сега лявата страна на L трябва да се намали с първия брой комбинации от дясната страна с избраната стойност на C 1 и по подобен начин да се определи стойността на C 2 при втората итерация:

По същия начин трябва да се извършат всички следващи итерации, за да се изберат стойностите на всички други елементи C i от желаната комбинация, до последния елемент C m:

По очевидни причини стойността на последния елемент C m може да се определи въз основа на равенството на броя на неговите комбинации на остатъчната стойност на лявата страна на L:

Трябва да се отбележи, че стойността на последния елемент от комбинацията C m може да се намери още по-просто, без да се изброяват възможните му стойности:

Изпълнението на итерациите на разглеждания алгоритъм е илюстрирано със следния пример, където е необходимо да се определят комбинации с числото N=8 в лексикографски ред, ако n=6 и m=4:

Алгоритмичната способност за определяне на комбинация от дадено число в лексикографски ред може да се използва в различни посоки. По-специално, когато изброявате комбинации в лексикографски ред, е необходимо да се осигури връщане към всяка комбинация, която е получена по-рано, достатъчно е да знаете само нейния номер. Освен това става възможно генерирането на комбинации в произволен ред, който се регулира от произволно зададена последователност от техните лексикографски номера.

Сега представяме алгоритъм за генериране на комбинации в лексикографски ред:

2 за i:= 1 до k направи A[i] := i;

5 начало на запис(A, …, A[k]);

6 if A[k] = n then p:= p 1 else p:= k;

8 за i:= k downto p направи A[i] := A[p] + i p + 1

КОМБИНАЦИИ С ПОВТОРЕНИЯ НА ЕЛЕМЕНТИ

За разлика от класическата комбинация, където всички елементи са различни, комбинацията с повторения образува неподредена селекция от елементи на краен набор, където всеки елемент може да се появява неограничено често и не е задължително да присъства в едно копие. В този случай броят на повторенията на елементите обикновено е ограничен само от дължината на комбинацията, а комбинации, които се различават в поне един елемент, се считат за различни. Например, като изберете 4 по избор различни числа от набора 1, 2 и 3, можете да създадете следните 15 комбинации с повторения:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

Като цяло, комбинации с повторения могат да се образуват чрез избиране на n елемента от произволен тип. Те обаче винаги могат да бъдат свързани с последователни естествени числа от 1 до n. Тогава всяка комбинация от m незадължително различни числа в този диапазон може да бъде записана във векторна форма, подреждайки ги в ненамаляващ ред отляво надясно:

Естествено, при тази форма на нотиране всички съседни елементи могат да бъдат равни поради възможността за неограничени повторения. Въпреки това, всеки комбиниран вектор с повторения на n елемента по m може да бъде свързан с комбиниран вектор от (n+m−1) елемента по m, който е конструиран както следва:

Ясно е, че за всякакви стойности на елементите на вектора f, елементите на вектора C са гарантирано различни и строго подредени в нарастващ ред на техните стойности от диапазона от 1 до (n+m1) :

Наличието на едно към едно съответствие между елементите на комбинираните вектори f и C ни позволява да предложим следния прост метод за систематично изброяване на комбинации с повторения на n елемента по m. Необходимо е само да се изброят, например, в лексикографски ред, всички C комбинации от (n+m1) елементи от m, като последователно се трансформират елементите на всяка от тях в съответните елементи от комбинации с повторения f, като се използва следната формула:

В резултат на това се формира последователност от вектори от комбинации с повторения на елементи, които са подредени в реда, генериран чрез изброяване на съответните комбинации без повторения на елементи. По-специално, за да се получи горната последователност от комбинации от 3 цифри 1, 2 и 3 с повторения от 4 цифри, е необходимо да се изброят в лексикографски ред всички комбинации без повторения от 6 цифри 1,2,3,4, 5 и 6 са по 4 цифри всяка, като ги конвертирате, както е посочено. Следващият пример показва такова преобразуване на комбинацията (1,3,4,6) с лексикографското число 8:

Разгледаното едно към едно съответствие между комбинации със и без повторения на елементи означава, че техните комплекти са еднакво мощни. Следователно в общия случай броят на комбинациите с повторения на n елемента по m е равен на броя на комбинациите без повторения на (n+m1) елемента по m. Използвайки една и съща символика за обозначаване на броя на комбинациите с повторения f и без повторения C, това равенство може да се запише по следния начин:

Лесно е да се провери, че за разгледания по-горе пример, където n=3 и m=4, броят на комбинациите от повторения ще бъде равен на 15, което съвпада с резултата от директното им изброяване:

Трябва да се отбележи, че за разлика от класическата версия, стойностите на параметрите на комбинацията с повторения n и m не са пряко свързани една с друга, следователно f(n,m)>0 за всяка комбинация от техните положителни стойности. Съответните гранични условия се определят от равенството между стойностите на (n+m1) и (n1) или (n+m1) и m:

Също така трябва да е съвсем очевидно, че ако m е равно на 1, тогава не са възможни повторения на елементи и следователно за всяка положителна стойност на n>0 ще бъде вярно следното равенство:

В допълнение, за брой комбинации с повторения за всякакви положителни стойности n и m се прилага следната рекурентна връзка, която е подобна на идентичността на добавяне за комбинационни числа без повторение на елементи:

Всъщност той се превръща в посочената добавъчна идентичност при формално заместване на съответните числа от комбинации без повторения в лявата и дясната му страна:

Разгледаната рекурентна връзка може да се използва за ефективно определяне на броя на комбинациите с повторения, когато е важно да се елиминират трудоемките операции за изчисляване на факторни продукти и да се заменят с по-прости операции на добавяне. В този случай, за да изчислите стойността на f(n,m), трябва само да приложите тази рекурентна връзка, докато получите сумата от членове във формата f(1,m) и f(i,1), където i приема стойности в диапазона от n до 1. По дефиниция на количеството такива членове са равни съответно на 1 и i. Следният пример илюстрира използването на тази техника на трансформация за случая на n=3 и m=4:

ИЗБЕРЯВАНЕ НА ДВОИЧНИ КОМБИНАЦИИ

Когато внедрявате комбинации в хардуера или програмирате на асемблер, е важно да можете да обработвате записи на комбинации в двоичен формат. В този случай всяка комбинация от n елемента от m трябва да бъде специфицирана под формата на n-битово двоично число (B n,...B j,...B 1), където m единични цифри показват елементите на комбинация, а останалите (nm) цифри имат нулеви стойности. Очевидно при тази форма на запис различните комбинации трябва да се различават в подреждането на цифрите на единиците и има само C(n,m) начина за подреждане на m единици или (nm) нули в n-битов двоичен набор. Например следната таблица изброява всичките 6 такива двоични комбинации, които предоставят 4-битови двоични числа за всички комбинации от 4 елемента на произволен набор (E 1 , E 2 , E 3 , E 4 ) по 2:

В общия случай задачата за изброяване на такива двоични комбинации се свежда до систематично търсене на всички n-битови двоични набори с различни подредби на m един и (nm) нула бита. В най-простата форма се осъществява такова търсене различни методитранспозиции на съседни битове с отместване (алгоритми за транспозитивно изместване). Това са итеративни алгоритми и имената им отразяват естеството на операциите, извършвани на всяка стъпка. Итеративните процедури на алгоритмите за транспозитивно изместване образуват последователности от двоични комбинации, които започват с двоичен набор, където всички единици са концентрирани в цифрите от нисък порядък (вдясно) и завършват, когато всички 1 са в цифрите от висок порядък ( отляво):

Докато съвпадат в началната и крайната комбинация, тези последователности се различават по реда, в който са изброени междинните двоични комплекти. Във всички случаи обаче всяка следваща двоична комбинация се образува от предходната в резултат на извършване на съответните операции за транспониране и смяна. В същото време различните алгоритми за транспозитивно изместване се различават по начина, по който избират двойка битове за транспониране и група битове за изместване. Тази специфика е обсъдена по-долу за алгоритми за транспониране с ляво и дясно изместване.

В алгоритъма за транспониране с ляво изместване, на всяка стъпка, следващата двоична комбинация се получава от текущата чрез замяна на най-лявата двойка цифри 01 с 10 (транспониране) и изместване на групата от водещи единични цифри, ако има такива, близо до двойката 10, получена след транспонирането (отместването). Ако в този случай няма единици в най-високите цифри в текущата двоична комбинация, тогава преместването не се извършва, дори когато водещата единица е получена след транспониране на тази стъпка. Преместването също не се извършва, когато няма нули в най-значимите битове преди двойката 10, получена след транспонирането. Разглежданите действия са илюстрирани със следния пример за изпълнение на две последователни итерации на този алгоритъм, където при една итерация (15) се извършва само транспониране (T"), а при друга итерация (16) транспонирането се допълва от отместване ( T"+S"):

В алгоритъма за транспониране с дясно изместване концептуално подобни стъпки се изпълняват на всяка стъпка. Само транспонирането гарантира, че най-десните битове на 01 се заменят с 10 (вместо с най-левите), а след това всички вдясно от него се изместват към най-младите битове. Както и преди, смяната се извършва само ако има единици, които могат да бъдат изместени надясно. Разглежданите действия са илюстрирани със следния пример за извършване на две последователни итерации на този алгоритъм, където при една итерация (3) се извършва само транспониране (T"), а при друга итерация (4) транспонирането се допълва от отместване ( T"+S"):

Трябва да се отбележи, че итерациите на двата алгоритъма могат да бъдат записани в адитивна форма, ако двоичните комбинации се интерпретират като цели числа в числовата система с основа 2. По-специално, за алгоритъма за транспониране с изместване надясно, всяка следваща двоична комбинация (B" n ,…B" j , …B" 1), винаги може да се получи от текущата комбинация (B n,…B j,…B 1) чрез извършване на операциите за добавяне на цели числа, като се използва следната адитивна формула:

В тази адитивна формула показателите на степени на двойки f и t означават съответно броя на нулевите цифри от нисък порядък на текущата двоична комбинация и броя на единиците в ред вляво от тях. Например за 4-тата двоична комбинация (001110) от n=6 цифри f =1 и t =3. Следователно, изчисляването на следващата двоична комбинация с помощта на адитивната формула при итерация 5 ще даде следния резултат, еквивалентен на извършване на операциите за транспониране и преместване:

За сравнителен анализна разглежданите алгоритми за транспониране с ляво и дясно изместване е препоръчително да се сравнят последователностите от двоични комбинации, които те генерират в своите итерации. Следващата таблица показва две такива поредици от двоични комбинации от 4 елемента от 2, които са получени съответно от алгоритми за ляво (TSL) и дясно (TSR) преместване:

Сравнявайки тези 2 последователности, можете да видите, че те са обратно огледало. Това означава, че всеки две двоични комбинации, които се намират в тях на еднакво разстояние от взаимно противоположните краища на техните последователности, са огледален образ една на друга, тоест те съвпадат, когато индексирането на битовете в която и да е от тях е обърнато. Например, вторият двоичен модел от началото на TSL последователността (0101) е огледален образ на двоичния модел (1010), който е втори от края на TSR последователността. Като цяло, всяка двоична комбинация с номер i от една последователност е огледален образ на двоична комбинация с номер (ni+1) от друга последователност. Тази връзка между тези последователности е следствие от симетричния характер на операциите за транспониране и отместване в двата разглеждани алгоритъма за изброяване на двоични комбинации.

Трябва да се отбележи, че двоичният формат може да се използва и за запис на комбинации с повторения на елементи. За да направите това, е необходимо да се установи едно-към-едно съответствие между комбинации с повторения и двоични комбинации, които са конструирани по следния начин. Нека има произволна комбинация с повторения, която се получава чрез избор на m по избор различни елемента от n елемента на генериращото множество. За да установите желаното съвпадение, първо трябва да добавите всички елементи на формиращия набор (cat) към комбинацията и след това да сортирате получената конкатенация (сортиране), така че всички идентични елементи да са един до друг. Резултатът е поредица от (n+m) елемента, където има n групи от идентични елементи. Ще има общо (n+m1) празнини между елементите, сред които ще има (n1) празнини между групи от идентични елементи и m празнини между елементи в групи. За по-голяма яснота можете да поставите символите „|“ на посочените места. и "", съответно. Ако сега съпоставим 1 с интервалите между групите (|) и 0 с всички останали интервали (), получаваме двоична комбинация. Той се формира от двоичен набор от (n+m1) бита, където (n1) са единици и m нула бита, чието местоположение уникално съответства на оригиналната комбинация с повторения на елементи от n до m. Разглежданата техника на трансформация е илюстрирана със следния пример за конструиране на двоична комбинация (1001101) с помощта на комбинация с повторения (BBD), чиито елементи са избрани от генериращия набор от първите пет латински букви:

Като цяло, броят на такива двоични комплекти определя броя на начините за подреждане на (n1) единици (или m нули) в (n+m1) двоични цифри. Тази стойност очевидно е равна на броя комбинации от (n+m1) по (n1) или по m, т.е. C(n+m1,n1) или C(n+m1,m), което е равно на брой комбинации с повторения f( n,m) от n елемента, по m всеки. По този начин, имайки съответствие едно към едно между комбинации с повторения и двоични комбинации, е законно да се намали изброяването на комбинации с повторения до изброяване на двоични комбинации, например, като се използват алгоритми за транспониране с ляво или дясно изместване. След това трябва само да възстановите необходимите комбинации с повторения, като използвате получените двоични комбинации. Това винаги може да се направи с помощта на следната техника за възстановяване.

Нека основното множество, от чиито елементи се образуват комбинации с повторения на m не непременно различни елементи, е подредено по произволен начин, така че всеки от неговите елементи да има определена сериен номерот 1 до n. Нека също приложим изброяването на двоични комбинации от (n+m1) двоични цифри, където (n1) единици и m нула цифри. Всяка получена двоична комбинация може да бъде допълнена отляво с фиктивна единица цифра, а всички единици цифри могат да бъдат номерирани отляво надясно с цели числа от 1 до n. Тогава броят на нулите в ред след всяка i-та единица от двоичната комбинация ще бъде равен на броя на екземплярите на i-тия елемент от основния набор в съответната комбинация с повторения. Разгледаната техника е илюстрирана със следния пример, където с помощта на двоична комбинация (1001101) се възстановява комбинация с повторения на BBD, чиито елементи са избрани от генериращия набор от първите пет латински букви, написани по азбучен ред , а горната линия показва елементи, които липсват в тази комбинация:

Извършване на подобни действия при условия този пример, можете да изброите всичките 35 двоични комбинации, които образуват 7-битови двоични набори, където има 4 единици и 3 нули, и да възстановите съответните комбинации с повторения на 5 елемента от 3.