Дискретная математика

RawonaM · июня 25, 2011, 20:00

Задача: сколько есть вариантов выбросить сумму 25 с помощью 10 кубиков?

Я решил таки способом:
Сколько натуральных решений у уравнения $[tex]\inline x_1+x_2+...+x_{10}=25[/tex]$ если $[tex]\inline 1\le x_i\le 6[/tex]$ ? Дальше обычная комбинаторика.

В книге решение с помощью производящих функций, чего я до сих пор не пойму.

$[tex]f(x)=(x+x^2+x^3+x^4+x^5+x^6)^{10}=x^{10}(1-x^6)^{10}(1+x+x^2+...)^{10}[/tex]$

Отсюда они как-то прямиком выводят ответ. Я понимаю, что нужно найти коэффициент х¹⁵ в $[tex]\inline (1-x^6)^{10}(1+x+x^2+...)^{10}[/tex]$ . Также понятно, что коэффициент х¹⁵ в $[tex]\inline (1+x+x^2+...)^{10}[/tex]$ является D(10,15) (первое слагаемое в ответе). А как дальше дойти до конечного ответа, не понимаю.

RawonaM · июня 25, 2011, 20:35

Кажется до меня дошло. Нужно разложить по биному Ньютона. Все-таки имхо включением-исключением интуитивно проще решается.

Вот из этой же серии:
Есть четыре вида шариков, каждого вида по 10 штук, сколько вариантов выбрать из всех 25 шариков?

У меня вышло D(4,25)-4D(4,14)+6D(4,3). Верно?

На всяк случай:
$[tex]D(n, k)=\binom{n+k-1}{k}[/tex]$

RawonaM · июня 25, 2011, 22:09

Классная задачка, делюсь:

В группе есть 50 человек. Для первого задания нужно создать не более 6 подгрупп, ограничений нет. Для второго задания нужно создать не более 8 подгрупп, но так, чтобы никакие два человека, бывшие в одной группе в первом задании, не были в одной группе во втором задании. Возможно ли?

Квас · июня 26, 2011, 00:36

Ой, это уже на завтра всё. А то будут кошмары сниться о производящих функциях.

RawonaM · июня 26, 2011, 09:32

А мне снились, тока сейчас уже не помню что точно.

Помню, что за ночь понял какую-то сложную вещь, которую никак не мог понять. Надеюсь когда с ней встречусь, вспомню.

RawonaM · июня 29, 2011, 21:02

Вот задача, которая понизила мою уверенность на порядок:

Есть следующие предметы:
четыре кубика — синий, красный, белый, зеленый
четыре шарика — так же
четыре цилиндра — так же

1) Сколько вариантов есть поделить эти 12 предметов на 4 группы, если в каждой группе ровно один кубик, ровно один шарик и ровно один цилиндр? Группы не упорядочены.
2) В скольких из этих вариантов ни в одной группе нет 3 предметов одного цвета.

Пока думайте, я наберу свои ответы...

RawonaM · июня 29, 2011, 21:35

Ответы:

1) Начнет выбирать предметы в первую группу: 4 варианта кубиков, 4 — цилиндров, 4 — шариков, итого 4³. Во вторую группу уже 3³, в третью 2³, а в четвертую что осталось. В сумме 24³. Т.к. группы не упорядоченные, делим на 4!, итого ответ 24³/4!.
упд: более короткий путь: просто делим каждый тип предмета по отдельности между группами: 4!³/4!=24³/4!.

2) Будем считать группы упорядоченными, потом поделим на 4!. Определим множество вариантов А_i, что в группе i все предметы одного цвета.

По принципу включения-исключения конечный ответ будет таким: |U|-4|A₁|+6|A₁⋂A₂|-4!.

|U|=24³.

Посчитаем элементы в множестве А_i. 4 варианта выбрать цвет для группы i. Остальные три считаем как делали в пункт 1, получается 4*3³2³=4*6³.

|A₁⋂A₂|=6*2³

|U|-4|A₁|+6|A₁⋂A₂|-4!=24³-4*4*6³+6*6*2³-4!=10632

10632/4!=443

У меня навязчивое ощущение, что где-то я запутался...

Квас · июля 1, 2011, 11:04

Цитата: RawonaM от июня 29, 2011, 21:35
4!³/4!=24³/4!.

Я рекуррентно получил тот же результат (4!)².

RawonaM · июля 1, 2011, 11:09

Цитата: Квас от июля 1, 2011, 11:04
Цитата: RawonaM от июня 29, 2011, 21:354!³/4!=24³/4!.
Я рекуррентно получил тот же результат (4!)².

Как это рекуреннто?

Во-второй части по-моему я уже вижу ошибку.

А экзамен был вчера, кстати.

Квас · июля 1, 2011, 11:21

Цитата: RawonaM от июля 1, 2011, 11:09
А экзамен был вчера, кстати.

Эх. Хороша ложка к обеду.

Цитата: RawonaM от июля 1, 2011, 11:09
Цитата: Квас от июля 1, 2011, 11:04
Цитата: RawonaM от июня 29, 2011, 21:354!³/4!=24³/4!.
Я рекуррентно получил тот же результат (4!)².
Как это рекуреннто?

Пусть A_n — множество разбиений нужного вида, B_n — множество допустимых троек. Выбираем по одному предмету каждого вида, после чего надо раскидать оставшиеся, и получим отображение
$[tex]B_n \times A_{n-1} \to A_n. [/tex]$
Ясно, что оно сюръективное, и прообраз каждого элемента из A_n состоит из n элементов. Поэтому
$[tex]|A_n| = \frac{|B_n||A_{n-1}|}{n}[/tex]$
Очевидно, что |B_n| = n³, поэтому
$[tex]|A_n| = n^2 |A_{n-1}| = n^2(n-1)^2|A_{n-2}| = \ldots = (n!)^2[/tex]$

RawonaM · июля 1, 2011, 11:24

Да, интересный путь.

Что-то меня от дискретки подташнивает.

Я уже весь в логике, еще неделя.

RawonaM · октября 4, 2011, 10:37

Даны множества:
$[tex]A=\{(x,y)|x,y \in R\,, x-y=\sqrt2\,,x+y\in N\}[/tex]$
$[tex]B=\{(x,y)|x,y \in R\,, x-y=k\sqrt2 \,(k \in N)\,,x+y\in N\}[/tex]$

Нужно определить мощности A и B. Первая вроде алеф0, вторая вроде тоже, но вот заструдняюсь доказать.

Квас · октября 4, 2011, 11:48

B: при фиксированном k будет счётное множество, а B равно (счётному) объединению этих множеств по всем k, то есть тоже счётно.

RawonaM · октября 4, 2011, 12:57

А как определить биективную функцию из чего-нибудь счетного в B? Ну или можно инъективную из В во что-нибудь счетное.

Вот так прокатит:
f:NxN→B
$[tex]f(n,k)=(\frac{n+k\sqrt2}2,\frac{n-k\sqrt2}2)[/tex]$
?

Квас · октября 4, 2011, 19:32

Цитата: RawonaM от октября 4, 2011, 12:57
Вот так прокатит:

Ага.

Условия-то по смыслу одинаковые:
$[tex] x-y=k\sqrt2, \ ,x+y = n\}[/tex]$
Геометрически имеем два семейства параллельных прямых, а пары (x,y) соответствуют точкам их пересечения. Прямые из семейств однозначно определяются параметрами k и n.

RawonaM · октября 4, 2011, 21:41

Есть отношение эквивалентности S: xSy iff x+2y делится на три.
Как найти его классы? Сижу ломаю голову.

Квас · октября 4, 2011, 22:02

На R?

RawonaM · октября 4, 2011, 22:07

Да.

Квас · октября 4, 2011, 22:26

Или на Z всё-таки? А то число π не эквивалентно самому себе.

RawonaM · октября 4, 2011, 22:27

Сорри, на N.

Квас · октября 4, 2011, 22:56

На Z
$[tex]x+2y \equiv 0 \pmod 3 \Leftrightarrow x-y \equiv 0 \pmod 3,[/tex]$
и классы эквивалентности — это классы вычетов по модулю 3 (то есть числа, которые дают одинаковые остатки). Насчёт N надо подумать.

RawonaM · октября 4, 2011, 23:01

Так на N то же самое, только без отрицательных. Три класса:
0,3,6...
1,4,7...
2,5,8...

Квас · октября 4, 2011, 23:32

А, ну да. Можно сказать, что разбиение Z индуцирует разбиение N, если кому привычней с целыми числами.

RawonaM · октября 6, 2011, 19:20

K_n — количество разбиений множества {1,2,3..n} так, что в каждом классе не более двух элементов.
Нужно найти рекуррентную формулу.

Думал-думал, ничего не придумал.

RawonaM · октября 6, 2011, 19:36

Какую можно найти биективную функцию из R в RxR (например из [0,1] в квадрат 1x1)?

Лингвофорум

Дискретная математика

RawonaM

RawonaM

RawonaM

Квас

RawonaM

RawonaM

RawonaM

Квас

RawonaM

Квас

RawonaM

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

RawonaM

Быстрый ответ