Пояснення методики обчислення на іншому прикладі.

4 ящики - 6 елементів. 3-й ящик порожній

0 0 0

Дане, конкретне, розміщення описується кодом-вибіркою 111011001. Тоді, обчислюючи кількість перестановок елементів у вибірці з повторами визначаємо число можливих розміщень n елементів по m ящиках.

За допомогою даного методу визначається кількість можливих розміщень.

Якщо ж необхідно визначити кількість різних варіантів, за умовою, щоб в кожному було обов’язково по одному предмету, то спочатку розкладемо по одному предмету в кожний ящик. Залишиться n –m об’єктів, які необхідно додатково розмістити по ящиках. Загальна кількість варіантів буде . Прикладом такого методу розміщення може служити телевізійний сигнал. І біт визначає початок нового кадру. Або ж, при зв’язку через послідовний порт, існують при кожній посилці стартові та стопові біти.

Сполуки (комбінації) з повторенням. Сполукою із n по к з повторенням називається невпорядкована к -вибірка з повторенням із множини А для якої . Кількість сполук позначається .

Приклади сполук з повторами.

Для множини можна створити сполуки і т.д. Для отримання формули, яка визначає кількість різних сполук скористаємось кодуванням, яке було розглянуто раніше.

Якщо сполуки були отримані з множини , то маємо елементи “n” типів. Кожній сполуці із n по к відповідає її код-перестановка з повторами яка містить k -одиницьта n-1 – нулів (дійсно нулі розміщаються лише між елементами , тому їх буде на 1 менше ніж груп). Один із прикладів розміщення

….

1 0 0 1 …01

одиничок “к”, нулів n-1. Тоді, обчисливши вираз

отримаємо загальну кількість відповідних сполук. Зауважимо, що способи розподілу “n” однакових елементів по m різних комірках – це задача на сполуки з повтореннями.

Якщо в сполуки з повтореннями обов‘язково повинні входити “r” фіксованих типів елементів, то спочатку їх заповнимо. Залишається n – r елементів, які необхідно розподілити по k коробках. Маємо сполук.

Біном Ньютона. Властивості біноміальних коефіцієнтів.

Розглянемо степені двохчлена де

Числа Фібоначі, ряд Фібоначі, трикутник Паскаля.

к =0,1

121 к =0,1,2

1331 к =0,1,2,3

14641 к=0,1,2,3,4

15101051 к = 0,1,2,3,4,5

і т. д.

Тоді формула біному Ньютона.

Властивості розкладу бінома Ньютона та біноміальних коефіцієнтів.

1. Кількість доданків у розкладі

2. У кожному доданку сума показників рівна “n”, що - відповідає загальній розмірності елементів лівої частини.

3. Загальний член розкладу .

4. Коефіцієнти розкладу, рівновіддалені від його кінців, рівні між собою бо

5. Середній член розкладу при n=2р (парному) найбільший якщо ж

n=2р-1 (відсутній один, середній член) то найбільших доданків два однакових.

6. Сума усіх біноміальних коефіцієнтів

Доведемо. При

7. Сума біноміальних коефіцієнтів з парними k рівна сумі значень з непарними k. Тобто де - ціла частина х.

Дійсно, якщо взяти та

Тоді . Якщо перенести від‘ємні коефіцієнти направо то отримаємо необхідне співвідношення.

Ряд Ньютона!

Повернемось до бінома Ньютона, який дає можливість записати вираз у вигляді розкладу по степеням а та х. Відмітимо, що дану формулу знали і до Ньютона (середньоазіатські вчені Омар Хайям, Гияседін та інші). В західній Європі до Ньютона її знав Паскаль. В чому ж заслуга Ньютона? В тому, що він розширив дану формулу на не цілі показники.

Саме він показав, що, якщо “а” додатне число і , то, для довільного дійсного значення , має місце рівність

Тобто, в цьому випадку ряд буде безмежним. Тільки при цілих в чисельнику буде момент, що появиться дужка =0: всі подальші члени розкладу пропадуть!

Розглянемо два практичних випадки реалізації.

1.

По іншому дану формулу можна переписати у виді

причому , адже

Це співвідношення можна довести методом індукції (самостійно Комбінаторика Н.Я. Виленкин ст..200.)

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

Цей вираз можна використати при обчисленнях кореня квадратного з раціональних чисел з любою точністю. Для цього досить винести з під кореня найбільше число, корінь якого відомий.

 

Наприклад.

а дальше ряд Ньютона

дозволить обчислити значення з довільною, бажаною степеню точності.

Перетворивши останній вираз, отримаємо

.

Це можна здійснити також і наступним способом

104 500

4 416

1087 8400

7 7609

79100 і т.д.

 

От чому розклад в ряд по степенях b став називатись біномом Ньютона.