Комбинаторни количествени методи

ГЛАВА СЕДМА

КОМБИНАТОРНИ КОЛИЧЕСТВЕНИ МЕТОДИ

§1. ВЪВЕДЕНИЕ

С помощта на комбинаторни количествени методи могат да се моделират начините, способите, средствата и правилата за съставяне на групи, редици, съединения или класове от елементи, взети от едно ли повече крайни множества и подредени един до друг,
Комбинаторните задачи намират широко приложение във всички области на нашия обществено-икономически живот.Използват се много често и в образователната система, например:
Задача 1: Един студент има 5 ризи, 3 панталона и 4 чифта чорапи и 2 чифта обувки. Колко дни този студент може да се облича по различен начин с тези тоалети. Отг. 5.3.4.2 = 120 дни.
Задача 2: Колко различни трицифрени числа можем да образуваме с помощта на цифрите 1, 2 и 3 без да се повтаря нито една от тях?
123; 132; 213; 231; 312; 321 – шест
Задача 3: По колко различни начина могат да седнат трима ученика на една маса с три стола.
Отговор: Ако учениците са А, В и С, те могат да седнат по следните начини: АВС; АСВ; ВАС; ВСА; САВ и СВА
В последните два примера имаме да решим по една комбинаторна задача, в която участват всички дадени елементи, а групите от тях, които получаваме, се различават само по мястото на елементите в тях. Такива групи наричаме разместване или пермутации.

§2. ПЕРМУТАЦИИ
В двата примера, които разгледахме имаме по три дадени елемента, от които получихме по 6 различни наредби (подреждания, пермутации).
За да можем да разместваме произволен брой елементи и да намираме броя на всички възможни размествания (пермутации) ще се спрем последователно на случаите с 1, 2, 3, 4 и т.н. елементи:
когато имаме само едни елемент <Object: word/embeddings/oleObject1.bin>;
при два елемента <Object: word/embeddings/oleObject2.bin> имаме <Object: word/embeddings/oleObject3.bin> и <Object: word/embeddings/oleObject4.bin>, т.е. <Object: word/embeddings/oleObject5.bin>;
при три елемента <Object: word/embeddings/oleObject6.bin> и <Object: word/embeddings/oleObject7.bin> имаме:
<Object: word/embeddings/oleObject8.bin>
при <Object: word/embeddings/oleObject9.bin>елемента ще имаме:
<Object: word/embeddings/oleObject10.bin>
т.е. <Object: word/embeddings/oleObject11.bin>
при <Object: word/embeddings/oleObject12.bin> ще имаме <Object: word/embeddings/oleObject13.bin>
ако произведението <Object: word/embeddings/oleObject14.bin> означим с <Object: word/embeddings/oleObject15.bin>, получаваме:

<Object: word/embeddings/oleObject16.bin>
<Object: word/embeddings/oleObject17.bin>и т.н.
<Object: word/embeddings/oleObject18.bin>
<Object: word/embeddings/oleObject19.bin>чете се ен-факториел. С други
думи броят на пермутациите от <Object: word/embeddings/oleObject20.bin> елемента е равен на <Object: word/embeddings/oleObject21.bin> (ен-факториел).

§3. ВАРИАЦИИ

Ако от дадените числа образуваме групи от по-малко елемента, в които и разместваме елементите в групата, получаваме друг вид съединения, наречени вариации. Например:
Колко двуцифрени числа можем да образуваме с помощта на цифрите 1, 2 и 3, без да се повтаря нито една от тях?
<Object: word/embeddings/oleObject22.bin>
Тъй като са ни дадени 3 цифри, а образуваме двуцифрени числа, ще въведем означението <Object: word/embeddings/oleObject23.bin>(чете се вариация от три елемента, втори клас).
С помощта на 4 елемента можем да образуваме следните вариации:
<Object: word/embeddings/oleObject24.bin>

<Object: word/embeddings/oleObject25.bin>
<Object: word/embeddings/oleObject26.bin>
<Object: word/embeddings/oleObject27.bin>
<Object: word/embeddings/oleObject28.bin>

в общия случай <Object: word/embeddings/oleObject29.bin>

<Object: word/embeddings/oleObject30.bin>

или <Object: word/embeddings/oleObject31.bin> <Object: word/embeddings/oleObject32.bin> <Object: word/embeddings/oleObject33.bin>

<Object: word/embeddings/oleObject34.bin>

§4. КОМБИНАЦИИ

Ако от всичките вариации на <Object: word/embeddings/oleObject35.bin>елемента от <Object: word/embeddings/oleObject36.bin>-ти клас изберем тези, които се различават само по участващите в тях елементи (но не и по местата им) ще получим комбинации от <Object: word/embeddings/oleObject37.bin>елемента <Object: word/embeddings/oleObject38.bin>-ти клас, които ще означаваме с <Object: word/embeddings/oleObject39.bin>или <Object: word/embeddings/oleObject40.bin> чете се “<Object: word/embeddings/oleObject41.bin> над <Object: word/embeddings/oleObject42.bin>”, например <Object: word/embeddings/oleObject43.bin> и <Object: word/embeddings/oleObject44.bin>. Ако сравним тези комбинации с вариациите от 4 елемента, трети клас ще видим, че вариациите са получени от комбинациите чрез пермутиране на всеки от четирите комбинации. Следователно <Object: word/embeddings/oleObject45.bin>, откъдето <Object: word/embeddings/oleObject46.bin> или
<Object: word/embeddings/oleObject47.bin>
Пример1: Колко различни снимки могат да направят 7 ученика, ако се снимат по трима в един кадър?
<Object: word/embeddings/oleObject48.bin>снимки.

Пример 2: Колко различни фиша трябва да попълним за играта тото 2, 6 от 49, за да сме сигурни че ще улучим шестица?

<Object: word/embeddings/oleObject49.bin>

ОПРЕДЕЛЕНИЕ 1: Пермутации (разместване) наричаме групи съединения или класове от елементи, в които участвуват всички дадени елементи, а групите се различават помежду си само по мястото на елементите в групата (бележат се с <Object: word/embeddings/oleObject50.bin>)

ОПРЕДЕЛЕНИЕ 2: Вариации наричаме групи съединения или класове от елементи, в които участвуват част от дадените елементи и се различават помежду си както по елементите в тях, така и по мястото им в групата (бележат се с <Object: word/embeddings/oleObject51.bin>).

ОПРЕДЕЛЕНИЕ 3: Комбинациите са групи съединения или класове от елементи, в които участват част от дадените елементи, а групите се различават помежду си само по елементите, участващи в тях (бележат се с <Object: word/embeddings/oleObject52.bin>).

От формулата <Object: word/embeddings/oleObject53.bin>чрез непосредствена проверка могат да се докажат и следните свойства:

<Object: word/embeddings/oleObject54.bin>

Свойство 3 се доказва като извършим следните преобразувания:

<Object: word/embeddings/oleObject55.bin>

Свойство 4 може да се докаже така:

<Object: word/embeddings/oleObject56.bin>

§5. НЮТОНОВ БИНОМ
Като използуваме въведените означения за <Object: word/embeddings/oleObject57.bin> можем да получим една много важна формула за пресмятане на бинома <Object: word/embeddings/oleObject58.bin>по следния начин:
<Object: word/embeddings/oleObject59.bin> или в общия случай: <Object: word/embeddings/oleObject60.bin>
Едно практическо правило за намиране коефициентите <Object: word/embeddings/oleObject61.bin> ни дава така наречения триъгълник на Паскал:

<Object: word/embeddings/oleObject62.bin>
Числата в триъгълника се наричат биномни коефициенти и те участват като коефициенти в развитието на бинома <Object: word/embeddings/oleObject63.bin>.
Следствие: при <Object: word/embeddings/oleObject64.bin> ще получим :<Object: word/embeddings/oleObject65.bin>.

Задачи за упражнение

Задача 1: Колко различни трицифрени числа можем да запишем с помощта на цифрите: 0, 1, 2 без да се повтаря нито една от тях?
Задача 2: Колко различни четирицифрени числа, които се делят на 2, можем да запишем с помощта на цифрите: 1, 2, 3 и 4, без да се повтаря нито една от тях?
Задача 3: По колко различни начина може да се подредят 6 деца в една редица, като 3 от тях са едно до друго:
а) без да се разместват помежду си;
б) ако се разместват помежду си.
Отг: а) <Object: word/embeddings/oleObject66.bin> б) <Object: word/embeddings/oleObject67.bin>
Задача 4: Колко различни трицифрени числа, които се делят на 2 можем да запишем с помощта на цифрите: 1, 2, 3, 4 и 5, без да се повтаря нито една от тях?
Отг.: <Object: word/embeddings/oleObject68.bin>
Задача 5: Колко различни двуцифрени числа можем да запишем с помощта на цифрите: 1, 2, 3 и 4, ако цифрите могат да се повтарят?
Отг.: <Object: word/embeddings/oleObject69.bin>
Задача 6: Колко различни телефонни номера могат да се образуват при телефонен номер: а) с 5 цифри; б) с 6 цифри? Обяснете защо?
Отг.: а) 105
б) 106
Задача 7: Колко различни тричленки могат да се излъчат от една група от 10 студенти? Отг. <Object: word/embeddings/oleObject70.bin>
Задача 8: Колко фиша от тото 2, 5 от 35 трябва да попълним ако играем с 8 числа?
Отг.: <Object: word/embeddings/oleObject71.bin>
Задача 9: Запишете в разгънат вид биномите?
а) <Object: word/embeddings/oleObject72.bin> б) <Object: word/embeddings/oleObject73.bin> в) <Object: word/embeddings/oleObject74.bin>
г) <Object: word/embeddings/oleObject75.bin> д) <Object: word/embeddings/oleObject76.bin> е) <Object: word/embeddings/oleObject77.bin>

Задача 10: Колко различни триъгълника можем да построим през 7 точки, които са разположени така, че никои три от тях не лежат на една права?
Отг.: <Object: word/embeddings/oleObject78.bin>
Задача 11: Колко различни прави можем до построим през 7 различни точки, които са разположени така, че само три от тях лежат на една права.

Отг. <Object: word/embeddings/oleObject79.bin>
Задача 12: Да се определи броя на елементите, които удовлетворяват уравненията:

1. <Object: word/embeddings/oleObject80.bin> Отг. n = 5. 7. <Object: word/embeddings/oleObject81.bin> n = 5.
2. <Object: word/embeddings/oleObject82.bin> n = 4. 8. <Object: word/embeddings/oleObject83.bin> n = 5.
3. <Object: word/embeddings/oleObject84.bin> n = 2. 9. <Object: word/embeddings/oleObject85.bin> n = 13.
4. <Object: word/embeddings/oleObject86.bin> n = 4. 10. <Object: word/embeddings/oleObject87.bin> n = 7.
5. <Object: word/embeddings/oleObject88.bin> n = 3. 11. <Object: word/embeddings/oleObject89.bin> n = 8.

6. <Object: word/embeddings/oleObject90.bin> n = 8. 12. <Object: word/embeddings/oleObject91.bin> n = 2;5