Skip to main content
LibreTexts - Ukrayinska

1.5: Зірки та бари

  1. Last updated
  2. Save as PDF
  • Page ID
    64448

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Template:MathJaxLevin

    Досліджуйте!

    Припустимо, у вас є деяка кількість однакових кубиків Рубіка, щоб роздати своїм друзям. Уявіть, що ви починаєте з одного ряду кубиків.

    1. Знайдіть кількість різних способів розподілу наданих кубиків:
      1. У вас є 3 кубика, щоб дати 2 людям.
      2. У вас є 4 кубика, щоб дати 2 людям.
      3. У вас є 5 кубиків, щоб дати 2 людям.
      4. У вас є 3 кубика, щоб дати 3 людям.
      5. У вас є 4 кубика, щоб дати 3 людям.
      6. У вас є 5 кубиків, щоб дати 3 людям.
    2. Зробіть здогадки про те, скільки різних способів ви могли б розподілити 7 кубиків 4 людям. Поясніть.
    3. Що робити, якщо від кожної людини потрібно було дістати хоча б один куб? Як змінилися б ваші відповіді?

    Розглянемо наступну проблему підрахунку:

    У вас є 7 печива, щоб дати 4 дітям. Скільки способів ви можете це зробити?

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

    Перш ніж вирішити проблему, ось неправильна відповідь: Ви можете здогадатися, що відповідь повинна бути\(4^7\) тому, що для кожного з 7 файлів cookie є 4 варіанти дітей, яким ви можете дати печиво. Це розумно, але неправильно. Щоб зрозуміти, чому, розглянемо кілька можливих результатів: ми могли б призначити перші шість файлів cookie дитині А, а сьоме печиво дитині Б. Інший результат призначить перший файл cookie малюкові B, а шість решти печива малюкові А. Обидва результати включені у\(4^7\) відповідь. Але для нашої проблеми підрахунку обидва результати дійсно однакові - дитина А отримує шість печива, а малюк Б отримує одне печиво.

    Як насправді виглядають результати? Як ми можемо їх представляти? Одним з підходів було б написати результат у вигляді рядка з чотирьох чисел, таких як це:

    \ begin {рівняння*} 3112,\ end {рівняння*}

    які представляють результат, в якому перший малюк отримує 3 печива, другий і третій малюк отримує по 1 печиво, а четвертий - 2 печива. Представлений таким чином, має значення порядок, в якому відбуваються числа. 1312 - це інший результат, тому що перший малюк отримує одне печиво замість 3. Кожне число в рядку може бути будь-яким цілим числом від 0 до 7. Але відповідь не\(7^4\text{.}\) Нам потрібна сума чисел, щоб бути 7.

    Інший спосіб, яким ми можемо представити результати, - це написати рядок із семи літер:

    \ begin {рівняння*}\ mbox {ABAADCD},\ кінець {рівняння*}

    що означає, що перше печиво йде малюкові А, друге печиво йде малюкові B, третє і четверте печиво - малюкові А, і так далі. Фактично, цей результат ідентичний попередньому - A отримує 3 печива, B і C отримують 1 кожен, а D отримує 2. Кожна з семи букв в рядку може бути будь-якою з 4 можливих букв (по одній на кожного малюка), але кількість таких рядків не\(4^7\text{,}\) тому, що тут порядок не має значення. Насправді ще один спосіб написати такий же результат -

    \ почати {рівняння*}\ mbox {AAABCDD}. \ end {рівняння*}

    Це буде кращим представленням результату. Оскільки ми можемо писати літери в будь-якому порядку, ми можемо також писати їх в алфавітному порядку для цілей підрахунку. Таким чином, ми напишемо всі A спочатку, потім всі B, і так далі.

    Тепер подумайте, як можна було б конкретизувати такий результат. Все, що нам дійсно потрібно зробити, це сказати, коли переходити з однієї літери на іншу. Що стосується файлів cookie, ми повинні сказати, через скільки файлів cookie ми перестаємо давати печиво першій дитині і починаємо давати печиво другій дитині. А потім через скільки ми переходимо на третього малюка? А через скільки ми переходимо на четверту? Отже, ще один спосіб представити результат виглядає так:

    \ begin {рівняння*} ***|*|*|**\ end {рівняння*}

    Три печива йдемо до першого малюка, потім перемикаємо і даємо одне печиво другому малюкові, потім перемикаємо, одне на третього малюка, перемикаємо, два на четвертого малюка. Зверніть увагу, що нам потрібні 7 зірок і 3 бари - одна зірка для кожного печива, і один бар для кожного перемикання між дітьми, тому на один менше барів, ніж є діти (нам не потрібно перемикатися після останнього малюка - ми закінчили).

    Чому ми все це зробили? Просто: щоб підрахувати кількість способів розповсюдження печива 7 для 4 дітей, все, що нам потрібно зробити, це порахувати, скільки зірок і барів діаграм є. Але діаграма зірок і барів - це просто рядок символів, деякі зірки і деякі бари. Якщо замість зірок і барів ми б використовувати 0 і 1, це буде просто трохи рядок. Ми знаємо, як їх рахувати.

    Перш ніж ми будемо занадто схвильовані, ми повинні переконатися, що дійсно будь-який рядок (у нашому випадку) 7 зірок і 3 барів відповідає іншому способу розповсюдження печива дітям. Зокрема, розглянемо рядок, подібний до цього:

    \ begin {рівняння*} |***||****\ end {рівняння*}

    Чи відповідає це розповсюдженню файлів cookie? Так. Він являє собою розподіл, в якому дитина А отримує 0 печива (тому що ми перемикаємося на малюка B перед будь-якими зірками), малюк B отримує три печива (три зірки перед наступним баром), дитина C отримує 0 печива (без зірок перед наступним баром), а дитина D отримує решту 4 печива. Незалежно від того, як розташовані зірки та бари, ми можемо розподіляти печиво таким чином. Крім того, враховуючи будь-який спосіб розповсюдження печива, ми можемо уявити це за допомогою діаграми зірок та барів. Наприклад, розподіл, в якому малюк А отримує 6 печива, а малюк Б отримує 1 печиво, має наступну діаграму:

    \ begin {рівняння*} ******|||\ кінець {рівняння*}

    Після всієї цієї роботи ми нарешті готові порахувати. Кожен спосіб розподілу печива відповідає діаграмі зірок і барів із 7 зірками та 3 барами. Таким чином, є 10 символів, і ми повинні вибрати 3 з них, щоб бути бари. Таким чином:

    \ begin {рівняння*}\ mbox {Є} {10\ choose 3}\ mbox {способи розповсюдження 7 файлів cookie для 4 дітей.} \ end {рівняння*}

    Поки ми займаємося цим, ми також можемо відповісти на відповідне запитання: скільки способів розповсюдити 7 печива 4 дітям, щоб кожна дитина отримала хоча б одне печиво? Що можна сказати про відповідні діаграмах зірок і барів? Графіки повинні починатися і закінчуватися хоча б однією зіркою (щоб діти A і D) отримували печиво, а також жодні два стовпчики не можуть бути сусідніми (щоб діти B і C не пропускали). Один із способів запевнити це - лише розміщувати смуги в проміжках між зірками. З 7 зірками між зірками є 6 плям, тому ми повинні вибрати 3 з цих 6 місць, щоб заповнити смугами. Таким чином, існують\({6 \choose 3}\) способи розповсюдження 7 печива 4 дітям, даючи принаймні одне печиво кожній дитині.

    Інший (і більш загальний) спосіб підійти до цієї модифікованої проблеми - спочатку дати кожному малюкові одне печиво. Тепер решта 3 печива можна роздати 4 малюкам без обмежень. Таким чином, у нас є 3 зірки і 3 бари в цілому 6 символів, 3 з яких повинні бути бари. Отже, знову ми бачимо, що існують\({6 \choose 3}\) способи розповсюдження файлів cookie.

    Зірки та бари можуть бути використані для підрахунку проблем, крім дітей та печива. Ось кілька прикладів:

    Приклад\(\PageIndex{1}\)

    Ваша улюблена математична мережа піци пропонує 10 начинок. Скільки піц ви можете зробити, якщо вам дозволено 6 начинок? Порядок начинки не має значення, але тепер вам дозволено повторення. Отже, одна можлива піца - потрійна ковбаса, подвійний ананас та цибуля.

    Рішення

    Отримуємо 6 начинки (підраховуючи можливі повтори). Представляємо кожну з цих начинок як зірку. Подумайте про те, щоб спуститися по меню по одній доливі за раз: спочатку ви бачите анчоуси і переходите до наступного, ковбасу. Ви говорите «так» ковбасі 3 рази (використовуйте 3 зірки), а потім перейдіть на наступний топінг у списку. Ви продовжуєте пропускати, поки не дійдете до ананаса, який ви говорите «так» двічі. Ще один перемикач і ви на цибулю. Ви скажете «так» один раз. Тоді ви продовжуєте перемикатися, поки не дійдете до останнього доповнення, ніколи більше не кажучи так (оскільки ви вже сказали так 6 разів. Є 10 начинок на вибір, тому ми повинні перейти від розгляду однієї начинки до наступних 9 разів. Це і є бруски.

    Тепер, коли ми впевнені, що маємо потрібну кількість зірок і барів, відповідаємо на питання просто: є 6 зірок і 9 смуг, тому 15 символів. Нам потрібно вибрати 9 з них, щоб бути бари, так що там кількість піци можливо є

    \ begin {рівняння*} {15\ вибрати 9}. \ end {рівняння*}

    Приклад\(\PageIndex{2}\)

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

    Рішення

    Нам потрібно визначитися з 7 цифрами, тому ми будемо використовувати 7 зірок. Смуги представлятимуть перемикання від кожного можливого однозначного числа вниз наступного меншого. Отже, номер телефону 866-5221 представлений діаграмою зірок і барів.

    \ begin {рівняння*} |*||**|||||**|*|\ end {рівняння*}
    Є 10 варіантів для кожної цифри (0-9), тому ми повинні перемикатися між варіантами 9 разів. У нас 7 зірок і 9 барів, тому загальна кількість телефонних номерів становить

    \ begin {рівняння*} {16\ вибрати 9}. \ end {рівняння*}

    Приклад\(\PageIndex{3}\)

    Скільки цілочисельних розв'язків рівняння

    \ begin {рівняння*} x_1 + x_2 + x_3 + x_4 + x_5 = 13. \ end {рівняння*}

    (Цілочисельне рішення рівняння - це рішення, в якому невідоме має мати ціле значення.)

    1. де\(x_i \ge 0\) для кожного\(x_i\text{?}\)
    2. де\(x_i > 0\) для кожного\(x_i\text{?}\)
    3. де\(x_i \ge 2\) для кожного\(x_i\text{?}\)
    Рішення

    Ця проблема так само, як дати 13 печива 5 дітям. Ми повинні сказати, скільки з 13 одиниць йдуть до кожної з 5 змінних. Іншими словами, у нас 13 зірок і 4 смуги (смуги схожі на знаки «+» в рівнянні).

    1. Якщо\(x_i\) може бути 0 або більше, ми знаходимося в стандартному випадку без обмежень. Так 13 зірок і 4 бари можна розташувати\({17 \choose 4}\) способами.
    2. Тепер кожна змінна повинна бути не менше 1. Так дати одну одиницю для кожної змінної, щоб задовольнити це обмеження. Тепер залишилося 8 зірок, а ще 4 смуги, тому кількість рішень\({12 \choose 4}\text{.}\)
    3. Тепер кожна змінна повинна бути 2 або більше. Тому перед будь-яким підрахунком дайте кожній змінній 2 одиниці. Тепер у нас є 3 залишилися зірки і 4 бари, тому є\({7 \choose 4}\) рішення.

    Counting with Functions

    Many of the counting problems in this section might at first appear to be examples of counting functions. After all, when we try to count the number of ways to distribute cookies to kids, we are assigning each cookie to a kid, just like you assign elements of the domain of a function to elements in the codomain. However, the number of ways to assign 7 cookies to 4 kids is \({10 \choose 7} = 120\text{,}\) while the number of functions \(f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}\) is \(4^7 = 16384\text{.}\) What is going on here?

    When we count functions, we consider the following two functions, for example, to be different:

    \[f = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{a \amp b \amp c \amp c \amp c \amp c \amp c} \qquad g = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{b \amp a \amp c \amp c \amp c \amp c \amp c}.\]

    But these two functions would correspond to the same cookie distribution: kids \(a\) and \(b\) each get one cookie, kid \(c\) gets the rest (and none for kid \(d\)).

    The point: elements of the domain are distinguished, cookies are indistinguishable. This is analogous to the distinction between permutations (like counting functions) and combinations (not).

    Contributors and Attributions