23.3: Додатки

Last updated
Save as PDF

Page ID: 65280

\( \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}\): Counting partitions of a finite set.

Якщо\(vert A \vert = n\text{,}\) тоді кількість способів\(A\)\(m\) розділення на нез'єднані підмножини\(A_1, A_2, \ldots, A_m\text{,}\) з кожною підмножиною заданого розміру\(\vert A_j \vert = i_j\text{,}\) дорівнює

\ begin {рівняння*}\ binom {n} {i_1, i_2,\ ldots, i_m}\ текст {.} \ end {рівняння*}

Доказ ідеї.: Є\(C^n_{i_1}\) можливості для\(A_1\text{.}\) Після вибору\(A_1\text{,}\) є\(C^{n - i_1}_{i_2}\) можливості для\(A_2\text{.}\) Після вибору\(A_2\text{,}\) є\(C^{n - i_1 - i_2}_{i_3}\) можливості для\(A_2\text{.}\) Продовжити таким чином, щоб\(A_m\text{,}\) потім помножити всю формулу комбінації вирази разом.

Альтернативна ідея доказу.: Повертаючись до основних принципів підрахунку, ми можемо підійти до цього так само, як ми придумали факторіальну формулу для функції вибору. Вибір перестановки\(A\) (\(n!\)способів) дає нам екземпляр бажаного розділу\(A\) шляхом встановлення бути\(A_1\) підмножиною, що складається з перших\(i_1\) об'єктів у перестановці, а потім встановлюючи\(A_2\) підмножину, що складається з наступних\(i_2\) об'єктів у перестановки і так далі. Однак упорядкування елементів всередині будь-якого такого підмножини\(A_j\) не має значення, і ми б отримали той самий розділ, якби ми взяли нашу перестановку\(A\) і знову перестановлені «кластери», що відповідають кожній підмножині\(A_j\text{.}\) Оскільки існують\(i_j!\) способи перемикання підмножини\(A_j\text{,}\) ми слід розділити\(n!\) на кожен з факторіалів\(i_j!\text{.}\)

Попередження\(\PageIndex{1}\)

У вищезгаданій теоремі порядок\(A_1, A_2, \ldots, A_m\) має значення!

Пропозиція\(\PageIndex{2}\): Counting words with a fixed composition of letters.

Припустимо\(x_1, x_2, \ldots, x_m\), що різні літери в алфавіті\(\Sigma\text{.}\) Для\(i_1 + i_2 + \cdots + i_m = n\text{,}\) кількості слів довжиною,\(n\) які складаються саме з\(i_1\)\(x_1\) 's,\(i_2\)\(x_2\)' s\(\ldots\text{,}\) і\(i_m\)\(x_m\) 's є багатономіальним коефіцієнтом\(\Sigma ^{\ast}\)

\ begin {рівняння*}\ binom {n} {i_1, i_2,\ ldots, i_m}\ текст {.} \ end {рівняння*}

Доказ ідеї.: Якщо ми розглядаємо кожну букву\(x_i\) як змінну, а кожне слово, що складається з букв,\(x_1,\ldots,x_m\) як добуток цих змінних, то кожне із слів, яке ми хочемо порахувати, дає нам один спосіб досягти терміну розширення Кількість\((x_1 + \cdots + x_m)^n\text{.}\) таких способів - багатономіальний коефіцієнт.\(x_1^{i_1} \cdots x_m^{i_m}\)

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

Скільки різних\(9\) -digit цілих чисел ми можемо сформувати з трьох\(3\) s, чотирьох\(6\) s і двох\(9\) s?

Рішення

Число цілих чисел потрібного розрядного складу - багатономіальний коефіцієнт

\ begin {рівняння*}\ binom {9} {3,4,2} =\ dfrac {9!} {3! 4! 2!} =\ drac {9\ точка 8\ точка 7\ точка 6\ точка 5} {3\ точка 2\ точка 2} = 9\ точка 4\ точка 7\ точка 5 = 1,260\ текст {.} \ end {рівняння*}