$\newcommand{\block}[2]{\begin{#1} #2 \end{#1}}$ $\newcommand{\cases}[1]{\block{cases}{#1}}$ $\newcommand{\up}[2]{\stackrel{#1}{#2}}$ $\def\dn#1#2{\mathrel{\mathop{#2}\limits_{#1}}}$ $\def\ident{\Longleftrightarrow}$ $\def\thus{\Rightarrow}$ $\newcommand{\set}[1]{ \{ #1 \} }$ $\newcommand{\bigset}[1]{ \left \{ #1 \right \} }$ $\newcommand{\bracs}[1]{ ( #1 ) }$ $\newcommand{\bigbracs}[1]{ \left ( #1 \right ) }$ $\newcommand{\bkets}[1]{\langle #1 \rangle}$ $\newcommand{\bigbkets}[1]{\left \langle #1 \right \rangle}$ $\newcommand{\mat}[1]{\block{Vmatrix}{#1}}$ $\newcommand{\det}[1]{\block{vmatrix}{#1}}$ $\newcommand{\pmat}[1]{\block{pmatrix}{#1}}$ $\newcommand{\emat}[1]{\block{matrix}{#1}}$ $\renewcommand{\geq}{\geqslant}$ $\renewcommand{\leq}{\leqslant}$ $\newcommand{\upline}[1]{\overline{#1}}$ $\newcommand{\dnline}[1]{\underline{#1}}$ $\def\ex{\exists}$ $\def\exo{\ex!}$ $\renewcommand{\fal}{\forall}$ $\renewcommand{\int}{\intop}$ $\def\inf{\infty}$ $\renewcommand{\tg}{\tan}$ $\renewcommand{\phi}{\varphi}$ $\renewcommand{\epsilon}{\varepsilon}$ $\def\alp{\alpha}$ $\def\lam{\lambda}$ $\def\gam{\gamma}$ $\def\eps{\epsilon}$ $\def\sig{\sigma}$ $\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\FF}{\mathbb{F}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\EE}{\mathbb{E}}$ $\newcommand{\UU}{\mathcal{U}}$ $\newcommand\E{\mathbbold{e}}$ $\newcommand\F{\mathbbold{f}}$ $\newcommand\G{\mathbbold{g}}$ $\newcommand{\rawOlim}[3]{\dn{{#1}\rightarrow{#2}}{#3}}$ $\newcommand{\lim}[2]{\rawOlim{#1}{#2}{lim}}$ $\newcommand{\uplim}[2]{\rawOlim{#1}{#2}{\upline{lim}}}$ $\newcommand{\dnlim}[2]{\rawOlim{#1}{#2}{\dnline{lim}}}$ $\newcommand{\norm}[1]{\left \lVert #1 \right \rVert}$ $\newcommand{\ord}[1]{\operatorname{ord}(#1)}$ $\newcommand{\ans}[1]{\textbf{Ответ}: #1.}$ $\renewcommand{\gcd}{\text{НОД}}$ $\newcommand{\lcm}{\text{НОК}}$ $\newcommand{\proj}[2]{\text{пр.}_{#1}{#2}}$ $\newcommand{\U}[2]{U_{#1}(#2)}$ # Комбинаторика Учебник, задачник - Виленкин комбинаторика Задачник - Короткова комбинаторика ## ЛЕК 10.02.23 Комбинации - сочетание определения в определённом порядке Задачи и классы проблем: - существования - вычислительная - выборная лучшего Задача укладки - уложить в замкнутое пространство объектов (объединение принадлежит) Задача покрытия - покрыть так, чтобы пустых мест не было (пересечение не равно нулю) Задача разбиения Проблема комбинаторики - задача выбора Выборка бывает: - упорядоченная (перестановки) - без повторений - с повторениями - неупорядоченная (сочетания) - без повторений - с повторениями $$ N, K - множество, f - функция выбора f - отображения N на K может быть, что только часть элементов N переносятся на K а может быть, что все - сюрьекция также существует также обратная функция для неё отображение инективное для взаимно-однозначном отображении - в дву стороны - называем биективным 4 класса задач исходит из того, что множества N, K могут быть различимы и неразличимы Пример фигрура 1) цифра 2) буква из англ 3) кружочек, трегольничек, квадратик, ромбик сколько всего фигур $10 \cdot 26 \cdot 4$ А значит независимые вещи влияют на результат отдельно **СЕМ 18.02** Обобщённое правило суммы: Дано r множеств $T_i (i=1,\dots, r )$ Каждое из которые содержит $n_i$ элементов $T_i \cap T_j \neq \emptyset$ при $i \neq j$ $|S| = \sum_{i=1}^r n_i$ Правило произведения: Пусть $T_i$ - суть $S_i$-того подмножества, при чём необязательно, чтобы они не пересекались Осуществляется выбор в определённом порядке, $n_2 = T_1$ $M_2 = T_1 \times T_2$ множество $(n_1 \cdot n_2)$ $M_3 = M_2 \times T_3$ $M_k = M_{k-1}\times T_{k}$ $(n_1\cdot n_2\dots n_k)$ - множество $\prod^k n_i$ Комбинаторные числа: $\upline{P_n^r} = n^r$ - число сочетаний с повторениями $C^r_n = \frac{n(n-1)\dots(n-r+1)}{r!} = \frac{\upline{P_n^r}}{r!}$ Следствия: $C_n^r=\frac{n!}{r!(n-r)!}$ $C^r_n=C^{n-r}_n$ $C^0_n=1$ $C^r_0=0$ $C^0_0=1$ Задачи: Задача: В почтовом отделении продаются открытки 10 видов, сколькими способами можно купить 12 открыток для поздравления $\upline{C^n_n}=C^r_{n+r-1} = \frac{(n+r-1)!}{n!(r-1)!}$ $C^{12}_{10} = C^12_21=\frac {21!}{12!9!}=293930$ Расписание одного дня состояит из 5 уроков, определить число вариантов расписания, при выборе для 11 студентов $n=11, r=5$ $A^r_n=\frac{n!}{(n-r)!}$ $A^5_11=\frac{11!}{(11-5)!}=frac{11!}{6!} = 55440$ Сколькими способами можно расставить первые фигуры (король, ферзь, две ладьи, два слона, два ..) $n = 8, r= 1+1+2+2+2=8$ $\upline{P_n}(r_1,\dots,r_k) = \frac{n!}{r_1!,\dots,r_k!} = \frac{8!}{2!^3}$ 5 девушек и 3 юношей играют в коротки, сколькими способами они могут разбиться на команды по 4 челвека, если в каджой команде должно быть по одному юноше 1 парень 2 парня $(C_5^3 3 + C^2_5 C^2_3) / 2$ Из колоды, содержащей 52 карты, выдали 10 карт, сколько случаев, когда хотя бы 1 туз, ровно 1 туз, больше 1, не менее 2-х 1 Т: $C^9_{48} C^1_4 = \frac{48!}{9!39!} \frac{4!}{3!}$ 2 T: $C^8_{48} C^2_4 = \frac{48!}{8!40!}3!$ не менее 1: $C^{10}_{52} - C^{10}_{48}$ не менее 2: $C^{10}_{52} - C^{10}_{48} - C^9_{48}C^1_4$ Сколько можно сделать перестановок их n элементов в которых каждые два элемента не стоят рядом Данные три элемента a,b,c не стоят рядом $n! - 2(n-1)!$ $n! - 3!(n-2)!$ Компания из 7 юношей и 10 девушек танцуют, если в танце учавствуют все юношы, то сколько вариантов участия девушек в танце Сколько имеются вариантов, если учитывать лишь то, какие девушки неприглашённые две девушки точно приглашены $A_{10}^7$ $C_{10}^3$ $A_7^2 A_{8}^5$ **СЕМ 25.02** Лифт отправляется с 7 пассажирами и останавливается на 10 этажах, вероятность , что никакие два пассажира не выйдут на одном и том же этаже $10^7$ - общее колво вариантов $10 * 9*8*7*6*5*4$ 100 50 X 2/50 В урне A белых и Б черных шаров, A \geq 2 из урны вынимают две шара, вероятность, что два шара белых A / (A + B) * (A - 1)/(A + B - 1) в партии, состоящих их l из ### 04 принцип включения и исключения Теорема Путь E(n) обозначает сумму весов Элементы множество Х, которые удволетвояют в точности М свойства из P1 P2 Pn Тогда E(m) = W(m) - $\pmat{m+1\\m} W(m+1) + $\pmat{m+2\\m} w(m+2) - \dots + (-1)^{N-m} \pmat{N\\m}W(N)$ Теорема: Пусть E(o) обозначает сумму весов элементы множества Х не удволетворяют ни одному из свойств P1 P2 Pn Тогда E(o) = W(0) - W(1) + W(2) - ... + (-1)^N (W(N)) задача U(100) = 100(1-1/2)(1-1/5) = 100 1/2 4/5 = 40 $U(n) = n \prod(1-1/p)$ U(n) - функция эйлера p - простые делители цисла 3 задачи с семинаров + по ейлеру 92 к - 47 с - 38 в - 4 ск - 28 кв - 31 св - 26 скв - 25 тиктак одинаковые буквы не шли друг за другом т(иа)(тиак)() т(к)(тиа)() тиак 4! 2 С_2^1 6! - 4! 2 С_2^1 1234 1_000_000 1234 C_10^4 v + 10 b + 100 000 111 1 + C_10^3 1234000 1000000