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