Skip to main content
LibreTexts - Ukrayinska

8.1: Що таке комбінаторика?

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

    • \( \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}}\)

    Комбінаторика вивчає розташування об'єктів за деякими правилами. Питання, які можна задати, включають:

    • Існування. Чи існують домовленості?
    • Класифікація. Якщо домовленості існують, як їх охарактеризувати та класифікувати?
    • Перерахування. Скільки там домовленостей?
    • Будівництво. Чи існує алгоритм побудови всіх домовленостей?

    Приклад\(\PageIndex{1}\label{eg:whatiscombo-01}\)

    Скільки способів п'ять чоловік можуть сидіти за круглим столом? Що робити, якщо певна пара з них відмовляється сидіти поруч один з одним? Що робити, якщо є\(n\) люди?

    Приклад\(\PageIndex{1}\label{eg:whatiscombo-02}\)

    За даними цілих чисел\(n_1 \geq n_2 \geq \cdots \geq n_t \geq 1\), таблиця Янга форми\((n_1,n_2,\dots,n_t)\) складається з\(t\) рядків клітинок, що вирівнюються по лівому краю, з\(n_i\) осередками у другому рядку (відлік від верхнього ряду).\(i\) Ці клітинки зайняті цілими числами від 1 до\(n\)\(n=n_1+n_2+\cdots+n_t\), де, таким чином, що записи знаходяться в порядку спадання по кожному рядку зліва направо, і вниз по кожному стовпчику зверху вниз. Наприклад, три таблиці Янга фігури\((3,1)\) зображені на малюнку\(\PageIndex{1}\).

    Знімок екрана 2020-01-15 о 12.53.20 PM.png
    Малюнок\(\PageIndex{1}\): Три Молоді таблиці форми (3, 1).

    Відомо, що існує 35 молодих таблиць форми\((4,2,1)\). Чи можете ви перерахувати їх усі? Загалом, можна запитати, скільки Young tableaux є форми\((n_1,n_2,\ldots,n_t)\), і як ми можемо їх усіх генерувати?

    Приклад\(\PageIndex{3}\label{eg:whatiscombo-03}\)

    Двійковий рядок - це послідовність цифр, кожна з яких дорівнює 0 або 1. \(a_n\)Дозволяти кількість двійкових рядків довжини\(n\), які не містять послідовних 1s. Це легко перевірити\(a_1=2\)\(a_2=3\), і\(a_3=5\). Для чого потрібна загальна формула\(a_n\)?

    Приклад\(\PageIndex{4}\label{eg:whatiscombo-04}\)

    Складність алгоритму говорить нам, скільки операцій він вимагає. Порівнюючи складність декількох алгоритмів вирішення однієї і тієї ж задачі, можна визначити, який з них найбільш ефективний. \(b_n\)Дозволяти кількість операцій, необхідних для вирішення проблеми розміру\(n\). Якщо відомо, що\[b_n = 2b_{n-1}+3b_{n-2}, \qquad n\geq3, \nonumber\] де\(b_1=1\) і\(b_2=3\), для чого загальна формула\(b_n\)?