Skip to main content
LibreTexts - Ukrayinska

2.E: Включення виключення (вправи)

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

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

    2.1: Формула включення-виключення

    Вправа\(\PageIndex{1.1}\)

    Перерахуйте всі 6 розв'язків обмеженого рівняння у прикладі 2.1.1 та перерахуйте відповідні 6 підмножин.

    Вправа\(\PageIndex{1.2}\)

    Знайти кількість цілочисельних розв'язків до\(x_1+x_2+x_3+x_4=25\)\(1\le x_1\le6\),\(2\le x_2\le 8\),,\(0\le x_3\le8\),\(5\le x_4\le9\).

    Вправа\(\PageIndex{1.3}\)

    Знайти кількість підмножин\(\{25\cdot a,25\cdot b,25\cdot c,25\cdot d\}\) розміром 80.

    Вправа\(\PageIndex{1.4}\)

    Нагадаємо, що\(\left\{\begin{array}{c}n\\k\end{array}\right\}\) це число Стірлінга другого роду (визначення 1.9.1). Доведіть\(n\ge k\ge 0\), що для,\[ \left\{\begin{array}{c}n\\k\end{array}\right\}={1\over k!}\sum_{i=0}^k (-1)^{k-i}i^n{k\choose i}. \nonumber\] зробити\(n=0\) як особливий випадок, потім використовувати включення-виключення для інших. Ви можете припустити, за умовністю, що\(0^0=1\).

    2.2: Перестановки заборонених позицій

    Вправа\(\PageIndex{2.1}\)

    Доведіть, що\( D_n=nD_{n-1}+(-1)^n\) коли\(n\ge2\).

    Вправа\(\PageIndex{2.2}\)

    Доведіть,\(D_n\) що навіть якщо і тільки якщо\(n\) непарно.

    Вправа\(\PageIndex{2.3}\)

    Надайте відсутні деталі, наприклад 2.2.1. Що таке\(\lim_{n\to\infty} {Q_n\over n!}\)?

    Вправа\(\PageIndex{2.4}\)

    Знайдіть кількість перестановок\(1,2,\ldots,8\), які не мають непарного числа у правильному положенні.

    Вправа\(\PageIndex{2.5}\)

    Знайдіть кількість перестановок\(1,2,\ldots,8\), які мають принаймні одне непарне число у правильному положенні.

    Вправа\(\PageIndex{2.6}\)

    Скільки перестановок\([n]\) мають саме\(k\) числа у своїх правильних позиціях?

    Вправа\(\PageIndex{2.7}\)

    Дайте комбінаторний доказ того, що\[n!=\sum_{k=0}^n {n\choose k}D_{n-k}.\nonumber\]

    Вправа\(\PageIndex{2.8}\)

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

    Вправа\(\PageIndex{2.9}\)

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

    1. Ніхто не отримує ні власне пальто, ні власну сумку?
    2. Можна отримати власне пальто або сумку, але не обидва.

    Вправа\(\PageIndex{2.10}\)

    Припустимо,\(n\) люди сидять в\(m\ge n\) кріслах в кімнаті. У якийсь момент відбувається перерва, і всі виходять з кімнати. Коли вони повертаються, скільки способів їх можна сидіти, щоб жодна людина не займала такого ж стільця, як до перерви?