Композиція з повторенням: що це, формула, приклади

Ми знаємо як повторне розташування або повне розташування, усі впорядковані перегрупування, з якими ми можемо сформувати k елементи набору з немає елементи, з елементом немає може з’являтися більше одного разу. THE комбінаторний аналіз саме область математики розробляє методи підрахунку, щоб знайти кількість можливих скупчень у певних ситуаціях.

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

Читайте також: Фундаментальний принцип підрахунку - основна концепція комбінаторного аналізу

Що таке домовленість з повторенням?

Існує домовленість з повторенням у виробництві транспортних знаків. [1]

У нашому повсякденному житті ми стикаємось із ситуаціями, які включають послідовності та групування, які з’являються в вибирайте паролі в соціальних мережах або банку, а також у номерах телефонів або ситуаціях, які пов'язані з цим черги. У будь-якому випадку, нас оточують ситуації, що стосуються цих угруповань.

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

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

Для розрахунку кількості можливих повторюваних домовленостей ми використовуємо дуже просту формулу.

Не зупиняйтесь зараз... Після реклами є ще щось;)

Формулювання композиції з повторенням

Щоб знайти повну суму домовленості немає окремі елементи взяті з k в

о, у даній ситуації, яка дозволяє повторити елемент, ми використовуємо таку формулу:

ПОВІТРЯ_немає,_k = немає^k

AR → домовленість з повторенням
немає → кількість елементів у наборі
k → кількість елементів, які будуть обрані

Дивіться також: Проста комбінація - підрахувати всі підмножини даного набору

Як розрахувати номер повторюваної домовленості

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

Приклад 1:

Банківський пароль має п’ять цифр, що складаються виключно з цифр, яка кількість можливих паролів?

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

ПОВІТРЯ_10,5 = 10⁵ = 10.000

Отже, існує 10000 можливостей пароля.

Приклад 2:

Знаючи, що номерні знаки транспортних засобів складаються з трьох літер та чотирьох цифр, скільки номерних знаків ви можете сформувати?

Наш алфавіт складається з 26 букв, і існує 10 можливих цифр, тому давайте розділимося на два повних масиви та знайдемо кількість можливих масивів для букв і цифр.

ПОВІТРЯ_26,3 = 26³ = 17.576
ПОВІТРЯ₁₀,₄ = 10⁴ = 10.000

Таким чином, загальна кількість можливих домовленостей становить:

17.576 · 10.000 = 1.757.600.000

Різниця між простим розташуванням та повторним розташуванням

Відрізнити просту домовленість від домовленості повторенням є важливим для вирішення проблем за темою. Важливим для диференціації є усвідомлення того, що коли ми маємо справу з ситуацією, коли відбуваються перегрупування, порядок яких важливий, мова йде про домовленості, і якщо ці перегрупування дозволяють повторення між термінами, це домовленість з повторенням, також відома як домовленість повна. Коли перегрупування не дозволяє повторення, йдеться про просте розташування.

Проста формула розташування відрізняється від тієї, яку ми використовуємо для повторного розташування.

Ми бачили приклади повторення розташування раніше, тепер побачимо приклад простого розташування

Приклад:

Пауло хоче покласти на свою полицю три зі своїх 10 шкільних книжок, всі різні між собою, скільки способів він може організувати ці книги?

Зверніть увагу, що в цьому випадку порядок важливий, але немає повторень, оскільки це просте розташування. Щоб знайти кількість можливих групувань, ми повинні:

Щоб дізнатись більше про цю іншу форму групування, що використовується в комбінаторному аналізі, прочитайте текст: THEпросте розташування.

Вирішені вправи:

Питання 1 - (Енем) Банк попросив своїх клієнтів створити особистий шестизначний пароль, що складається лише з цифр від 0 до 9, для доступу до чекового рахунку через Інтернет. Однак фахівець з електронних систем безпеки рекомендував керівництву банку перереєструвати своїх користувачів, вимагаючи кожен з них, створення нового пароля з шести цифр, що тепер дозволяє використовувати 26 букв алфавіту, на додаток до цифр від 0 до 9. У цій новій системі кожна велика літера вважалася відмінною від малої версії. Крім того, використання інших типів символів було заборонено.

Одним із способів оцінити зміну системи паролів є перевірка коефіцієнта поліпшення, що є причиною нової кількості можливостей пароля щодо старої. Коефіцієнт поліпшення рекомендованої зміни становить:

Дозвіл

Альтернатива A

Старий пароль - це масив з повторенням, оскільки він може складатися з усіх чисел, тож це масив із 10 елементів, взятих кожні шість.

ПОВІТРЯ_10,6 = 10⁶

Новий пароль може складатися з 10 цифр, а також великих літер (26 букв) та малими літерами (26 букв), тож для кожної цифри пароль має 10 + 26 + 26 = 62 можливості. Оскільки є шість цифр, ми будемо обчислювати розташування з повторенням 62 елементів, взятих кожні шість.

ПОВІТРЯ_62,6 = 62⁶

THE причина нової кількості можливостей пароля порівняно зі старою дорівнює 62⁶/10⁶.

Питання 2 - (Enem 2017) Компанія створить свій веб-сайт і сподівається залучити аудиторію приблизно в один мільйон клієнтів. Щоб отримати доступ до цієї сторінки, вам знадобиться пароль із форматом, визначеним компанією. Існує п’ять варіантів формату, запропонованих програмістом, описаних у таблиці, де “L” та “D” представляють відповідно велику літеру та цифру.

Букви алфавіту серед 26 можливих, а також цифри, серед 10 можливих, можна повторити в будь-якому з варіантів.

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

Дозвіл

Альтернатива Е

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

I → LDDDDD

26 ·10⁵ перевищує два мільйони, тому не задовольняє запит компанії.

II → DDDDDD

10⁶ дорівнює одному мільйону, тому не задовольняє запит компанії.

III → LLDDDD

26² · 10⁴ перевищує два мільйони, тому не задовольняє запит компанії.

IV → DDDDD

10⁵ менше мільйона, тож це не задовольняє запит компанії.

V → LLLDD

26³ · 10² становить від одного до двох мільйонів, тому цей шаблон пароля є ідеальним.

Кредит зображення

[1] Рафаель Берланді / Shutterstock

Рауль Родрігес де Олівейра
Вчитель математики