Печать страницы - Дискретная математика

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:01

Вопрос по отношениям. Русской терминологии не знаю, поправляйте.

Дано М множество отношений над А={1,2,3}.

Также дано отношение К={(1,1),(2,1),(3,1)}.

Пусть будет f:M->M определен как f(R)=RK

1) Сколько элементов в образе f?

2) Определим отношение Е над М как (R,S) in E iff f(R)=f(S).
Е - отношение эквивалентности ("натуральная функция"?).
На сколько секций разбивает Е множество М?

Мои ответы:
1) 3
2) 8=2³ (т.е. 2 в степени количества элементов)

Верно ли?

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:06

Цитата: RawonaM от апреля 9, 2011, 22:01
f(R)=RK

Qu'est-ce que c'est ? Ça ne me semble pas standard.

Цитата: RawonaM от апреля 9, 2011, 22:01
На сколько секций разбивает Е множество М?

На сколько классов эквивалентности...

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:11

Цитата: Квас от апреля 9, 2011, 22:06
Цитироватьf(R)=RK
Qu'est-ce que c'est ? Ça ne me semble pas standard.

Умножение отношений, наложение то есть. aRx && xKb ==> aRKb.
Что-то я не так написал?

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:11

Цитата: Квас от апреля 9, 2011, 22:06
ЦитироватьНа сколько секций разбивает Е множество М?
На сколько классов эквивалентности...

мерси :)

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:13

Цитата: RawonaM от апреля 9, 2011, 22:01
Пусть будет f:M->M определен как f(R)=RK

Цитата: RawonaM от апреля 9, 2011, 22:11
Цитата: Квас от Сегодня в 23:06
ЦитироватьЦитировать
Цитироватьf(R)=RK
Qu'est-ce que c'est ? Ça ne me semble pas standard.
Умножение отношений, наложение то есть. aRx && xKb ==> aRKb.
Что-то я не так написал?

Тогда я ничего не понимаю вообще. Определяется отображение на M; значит, R — произвольный элемент M. Или как?

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:16

Цитата: Квас от апреля 9, 2011, 22:13
Тогда я ничего не понимаю вообще. Определяется отображение на M; значит, R — произвольный элемент M. Или как?

Хм. R - это же аргумент функции.
f(x)=xK, где х некая релация.

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:23

J'y suis ! По обыкновению я невнимательно прочитал. Сейчас соображу.

Offtop

Надо французский назначить официальным языком раздела наряду с русским. :-\

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:26

Цитата: Квас от апреля 9, 2011, 22:23
Надо французский назначить официальным языком раздела наряду с русским. :-\

Tres bien, je suis d'accord :)

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:33

Цитата: RawonaM от апреля 9, 2011, 22:01
1) 3

Их гораздо больше. Значение f(R) определяется только парами (1,x), которые входят в R. Поскольку x может пробегать любое подмножество из {1,2,3}, то получается 2^3 = 8 отображений.

Аналогично с 2): в классе эквивалентности столько элементов, сколько можно задать множеств из пар вида (2,y), (3,z), то есть (2^3)^2.

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:45

Цитата: Квас от апреля 9, 2011, 22:33
Цитировать1) 3
Их гораздо больше. Значение f(R) определяется только парами (1,x), которые входят в R. Поскольку x может пробегать любое подмножество из {1,2,3}, то получается 2^3 = 8 отображений.

Vous etes sur?
Regardez:
любой элемент из RK имеет форму (a,1), ибо в К все элементы (x,1). a элемент А, а в нем три элемента, поэтому максимум в RK три элемента.
Легко найти пример, что все три являются рейнджем (например если R=K), поэтому их три.

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:46

Цитата: Квас от апреля 9, 2011, 22:33
Значение f(R) определяется только парами (1,x), которые входят в R.

Собственно, тут что-то неладно. f(R) определяется еще и К.

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:48

Естественно! Я в своём решении перемножал в обратном порядке! >(

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:50

Короче, я согласен с обоими вашими ответами. (Хотя при моей сегодняшней «гипервнимательности» это, скорее, в минус идёт. :( )

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 22:54

Ничего, бывает :)

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

Больше всего взбесило, что первая задача в очередном домашнем задании акурат задача из матана, кто бы мог подумать! Это ж дискретка блин!

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 22:55

Постойте.

Цитата: RawonaM от апреля 9, 2011, 22:45
любой элемент из RK имеет форму (a,1)

Да. А какие варианты для a? Оно пробегает некоторое подмножество. Следовательно, у нас могут получиться отношения
$[tex]\varnothing[/tex]$
{(1,1)}
{(2,1)}
{(3,1)}
{(1,1), (2,1)}
...
M.

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:04

Действительно. Что-то тут не так. Ведь f функция в М...
Значит получается, что элемент ее образа (т.е. отношение) имеет 0-3 элемента, т.е. 2^3+1=9 отношений.
Так выходит?..

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:05

Цитата: Квас от апреля 9, 2011, 22:55
...
M.

М не может быть, ибо в М есть еще такие, у которых второе число в паре не 1.

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:06

В М сколько элементов есть? 2^9?

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 23:09

Цитата: RawonaM от апреля 9, 2011, 23:05
Цитата: Квас от Вчера в 23:55
Цитировать...
M.
М не может быть, ибо в М есть еще такие, у которых второе число в паре не 1.

Ага.

В общем, их столько, сколько подмножеств в {1,2,3}, т. е. 8.

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:13

Цитата: Квас от апреля 9, 2011, 23:09
В общем, их столько, сколько подмножеств в {1,2,3}, т. е. 8.

А точно, не нужно сюда 1 добавлять.

Давайте со вторым разбираться. :)

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:16

Чой-то я уже запутался вообще. Во втором тоже что ли 8 выходит?!

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:17

Собственно, логично. Оно делит на столько классов, сколько элементов есть в образе.

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 23:26

Цитата: RawonaM от апреля 9, 2011, 23:17
Собственно, логично. Оно делит на столько классов, сколько элементов есть в образе.

Точно! :)

Название: Дискретная математика
Отправлено: RawonaM от апреля 9, 2011, 23:31

Ну значит потихоньку начинаю понимать :)

А вот это верно:

Цитата: RawonaM от апреля 9, 2011, 23:06
В М сколько элементов есть? 2^9?

Название: Дискретная математика
Отправлено: Квас от апреля 9, 2011, 23:36

Цитата: RawonaM от апреля 9, 2011, 23:31
А вот это верно:
Цитата: RawonaM от Сегодня в 00:06
ЦитироватьВ М сколько элементов есть? 2^9?
?

Ага. В декартовом квадрате 9 элементов, а отношения — его подмножества.

Название: Дискретная математика
Отправлено: RawonaM от апреля 15, 2011, 15:08

По дискретке блин задание:
Доказать, что
$[tex]\frac{x}{1-x^2}[/tex]$
(-1<x<1) сюръективна (какой термин придумали, осспади...).
В анализе это доказывалось долго и нудно с помощью среднего значения. Не хоцца этим заниматься, что делать? Перевернуть и найти обратную функцию че-то не получается, там квадратное уравнение, которое мне не удается раскусить.

Название: Дискретная математика
Отправлено: RawonaM от апреля 15, 2011, 15:10

А что если просто показать, что у квадратного уравнения только один корень в пределах (-1,1)?.. Этого достаточно?

Название: Дискретная математика
Отправлено: RawonaM от апреля 15, 2011, 16:53

Вроде сделал. С помощью трюка, напрямую никак не решалось.

Название: Дискретная математика
Отправлено: Квас от апреля 15, 2011, 18:23

Сюръективно как отображение (-1,1) → R, насколько понимаю? Нужно показать, что каждое значение принимается; неважно, сколько раз. Проще всего аналитически: функция непрерывна, а односторонние пределы в концах интервала бесконечны с разными знаками.

Можно и через квадратное уравнение.
$[tex]\frac {x}{1-x^2}=y[/tex]$
$[tex]x^2 y + x - y = 0[/tex]$
При фиксированном y левая часть — квадратичная или линейная функция (⇒ непрерывная), при x=1 равна 1, при x=-1 равна -1. Значит, между -1 и 1 есть нуль этой функции.

Название: Дискретная математика
Отправлено: Квас от апреля 15, 2011, 18:28

Наверно, можно применить формулу корней квадратного уравнения, но там корень не извлекается, решение получилось бы неэлегантное.

Название: Дискретная математика
Отправлено: RawonaM от апреля 15, 2011, 18:29

Цитата: Квас от апреля 15, 2011, 18:23
При фиксированном y левая часть — квадратичная или линейная функция (⇒ непрерывная), при x=1 равна 1, при x=-1 равна -1. Значит, между -1 и 1 есть нуль этой функции.

У-у, точно, я уже весь анализ забыл! :)

Название: Дискретная математика
Отправлено: RawonaM от апреля 15, 2011, 18:30

Цитата: Квас от апреля 15, 2011, 18:28
Наверно, можно применить формулу корней квадратного уравнения, но там корень не извлекается, решение получилось бы неэлегантное.

Не извлекается. Я сделал с помощью свойства, что x1*x2=c/a.

Название: Дискретная математика
Отправлено: Квас от апреля 15, 2011, 18:34

Цитата: RawonaM от апреля 15, 2011, 18:30
Цитата: Квас от Сегодня в 19:28
ЦитироватьНаверно, можно применить формулу корней квадратного уравнения, но там корень не извлекается, решение получилось бы неэлегантное.
Не извлекается. Я сделал с помощью свойства, что x1*x2=c/a.

А, теорема Виета! ;up:

В решении надо обязательно отметить исключительный случай y=0, когда уравнение вырождается.

Название: Дискретная математика
Отправлено: RawonaM от апреля 15, 2011, 18:43

А я уже переписал по вашей подсказке, таки элегантней получается и неплохо было бы кусочек анализа вспомнить :))
Летом буду учить матан 2, надо будет еще хоть че-то помнить))

Название: Дискретная математика
Отправлено: RawonaM от апреля 30, 2011, 10:19

Есть множество с мощностью алеф-ноль. Верно ли, что любое бесконечно подмножество тоже алеф-ноль? Вроде довольно очевидно и легко доказать: если исходное множество пронумеровано, то и подмножество можно пронумеровать.

П.С. Как вошло в математику обозначение мощности с помощью алефов? :)

Название: Дискретная математика
Отправлено: Квас от апреля 30, 2011, 10:47

Цитата: RawonaM от апреля 30, 2011, 10:19
Есть множество с мощностью алеф-ноль. Верно ли, что любое бесконечно подмножество тоже алеф-ноль? Вроде довольно очевидно и легко доказать: если исходное множество пронумеровано, то и подмножество можно пронумеровать.

Со всем согласен. Нумерацию можно построить по индукции: элементу подмножества B с наименьшим номером в A даём номер 1; если элементы x1,... xk занумерованы в B, то номер k+1 даём элементу множества B\{x1,...xk}, имеющему наименьший номер в A. Проверка того, что получается биективное соответствие B и множества натуральных чисел, тривиальна.

Название: Дискретная математика
Отправлено: RawonaM от апреля 30, 2011, 11:02

Пасибо :)

Название: Дискретная математика
Отправлено: RawonaM от апреля 30, 2011, 13:50

Допустим есть мощности k,m,n. Верно ли что $[tex]k \le m \Rightarrow kn \le mn[/tex]$ ?
То есть, я уверен, что это верно, но пытаюсь построить доказательство, не вижу на чем основываться.

Название: Дискретная математика
Отправлено: Квас от апреля 30, 2011, 13:54

Пусть A, B, C — множества мощностей k, m, n соответственно. Известно, что есть инъективное отображение f: A→B, надо построить инъективное отображение $[tex]\inline g \colon A \times C \to B \times C[/tex]$ . Достаточно взять $[tex]\inline g = f \times \mathrm{id}[/tex]$ , то есть g(x,y) = (f(x), y); инъективность очевидна.

Название: Дискретная математика
Отправлено: RawonaM от апреля 30, 2011, 13:57

А, точно! Не понял только, что такое id.

Название: Дискретная математика
Отправлено: Квас от апреля 30, 2011, 13:59

Цитата: RawonaM от апреля 30, 2011, 13:57
Не понял только, что такое id.

Стандартное обозначение для тождественного отображения. Иногда для ясности индексом указывается множество, на котором это отображение действует.

Название: Дискретная математика
Отправлено: RawonaM от апреля 30, 2011, 14:09

Цитата: Квас от апреля 30, 2011, 13:59
ЦитироватьНе понял только, что такое id.
Стандартное обозначение для тождественного отображения. Иногда для ясности индексом указывается множество, на котором это отображение действует.

У нас I обозначают с индексом снизу над каким множеством.

Название: Дискретная математика
Отправлено: Alone Coder от апреля 30, 2011, 14:16

Цитата: RawonaM от апреля 15, 2011, 15:08
По дискретке блин задание:
Доказать, что
$[tex]\frac{x}{1-x^2}[/tex]$
(-1<x<1) сюръективна (какой термин придумали, осспади...).

И в какой же точке она принимает значение 0?

Название: Дискретная математика
Отправлено: Квас от апреля 30, 2011, 14:22

Цитата: Alone Coder от апреля 30, 2011, 14:16
Цитата: RawonaM от Апрель 15, 2011, 16:08
ЦитироватьПо дискретке блин задание:
Доказать, что
$[tex]\frac{x}{1-x^2}[/tex]$
(-1<x<1) сюръективна (какой термин придумали, осспади...).
И в какой же точке она принимает значение 0?

При x=0.

Название: Помощь по математике (анализ)
Отправлено: Karakurt от мая 3, 2011, 14:02

Как решать задачи типа сколько делителей имеет число х?

Название: Помощь по математике (анализ)
Отправлено: Квас от мая 3, 2011, 14:10

Цитата: Karakurt от мая 3, 2011, 14:02
Как решать задачи типа сколько делителей имеет число х?

Конкретно эта задача комбинаторная. Раскладываем x на простые множители:
$[tex]x = p_1^{k_1}\ldots p_s^{k_s}[/tex]$
На какие числа делится x? Только на такие, которые «составлены» из тех же простых множителей, причём в степенях не больше, чем у x. Точнее говоря, всякий делитель x имеет разложение
$[tex]p_1^{l_1}\ldots p_s^{l_s},[/tex]$
где $[tex]\inline l_i \leqslant k_i[/tex]$ .

Стало быть, каждый набор чисел $[tex]\inline (l_1,\ldots, l_s)[/tex]$ с $[tex]l_i \leqslant k_i[/tex]$ задаёт некоторый делитель x, причём разным наборам соответствуют разные делители (в силу единственности разложения на простые множители), и каждый делитель может быть так получен. Значит, делителей столько же, сколько наборов, то есть
$[tex](k_1+1)\ldots(k_s+1).[/tex]$

Пример: число $[tex]\inline 60 = 2^2 \cdot 3 \cdot 5[/tex]$ имеет $[tex]\inline 3\cdot2\cdot2=12[/tex]$ натуральных делителей.

Название: Помощь по математике (анализ)
Отправлено: Karakurt от мая 3, 2011, 15:14

Квас, спасибо! Стало ясно как решать. А вот почему именно так... :)

Название: Помощь по математике (анализ)
Отправлено: Квас от мая 3, 2011, 15:49

Цитата: Karakurt от мая 3, 2011, 15:14
А вот почему именно так... :)

Ну, решение задач — творческий процесс. :) Может, мне следовало просто идею подкинуть, что стоит воспользоваться разложением на простые множители.

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 17:38

Вопрос: сколько инъективных функций есть из А в В? Допустим |A|=4, |B|=7.
Решаю таким способом: 7*6*5*4=840.

Теперь окольным путем: если общее количество фукнций — 7^4, то инъективных из них 7^4-(неинъективные).
Неинъективные это значит что хотя бы один из В не используется, значит сплюсуем варианты, в которых используется <7, т.е. 6^4+5^4+...+1.
Ответы не сходятся. Где ошибка?

Название: Дискретная математика
Отправлено: Квас от мая 20, 2011, 17:55

Цитата: RawonaM от мая 20, 2011, 17:38
Неинъективные это значит что хотя бы один из В не используется

Это несюръективные. А нас интересуют только размещения без повторений элементов из B: 7 ∙ 6 ∙ 5 ∙ 4.

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 18:00

Цитата: Квас от мая 20, 2011, 17:55
Это несюръективные.

Точно.

Цитата: Квас от мая 20, 2011, 17:55
А нас интересуют только размещения без повторений элементов из B: 7 ∙ 6 ∙ 5 ∙ 4.

Ну это я уже знаю. А другого пути нет? Чтоб из 7^4 повычитать.

Название: Дискретная математика
Отправлено: Квас от мая 20, 2011, 18:03

Цитата: RawonaM от мая 20, 2011, 18:00
Цитата: Квас от Сегодня в 18:55
ЦитироватьА нас интересуют только размещения без повторений элементов из B: 7 ∙ 6 ∙ 5 ∙ 4.
Ну это я уже знаю. А другого пути нет? Чтоб из 7^4 повычитать.

Мне кажется, будет сложно. Потому что надо учитывать, что разное число элементов B могут иметь прообразы с числом элементов >1, и число элементов в этих прообразах тоже может быть разным. На самом деле размещения без повторений — это именно ответ на вопрос о числе инъективных отображений, ибо что есть инъективное отображение?

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 18:05

Ладно, уговорили. Мудрить не буду.

Собственно, у меня есть тут второй пункт, посложнее. Я пока над ним думаю.

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 20:33

Теперь такой вопрос по тому же: сколько инъективных фукций из А в В, при условии что для любого i в А, f(i)!=i?

Моя версия: $[tex]7\cdot 6\cdot 5\cdot 4 - 4\cdot 6^3 + 6\cdot 5^3 - 4\cdot 4 + 1 = 711[/tex]$

Кёскё ву дит?

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 21:50

Еще из той же области: четыре семьи вышли на день независимости в парк на барбекью. На общем мангале пожарили 9 стэйков и 12 шампуров. Сколько вариантов поделить еду между всеми, так чтобы каждая семья получила хотя бы один стэйк или шампур?

У меня вышло 80856, если у кого есть желание тоже поковыряться и перепроверить, буду рад :)

Название: Дискретная математика
Отправлено: Квас от мая 20, 2011, 21:50

Цитата: RawonaM от мая 20, 2011, 20:33
f(i)!=i?

Это как? Они же разным множествам принадлежат.

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 21:53

Цитата: Квас от мая 20, 2011, 21:50
Цитироватьf(i)!=i?
Это как? Они же разным множествам принадлежат.

i — натуральное число.
Т.е. чтобы f(1)!=1 и т.п.

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 21:54

А тьфу, пардон. Забыл сказать, что А={1,2,3,4}, В={x|1<=х<=7, х натурал}. :)

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 21:57

Цитата: RawonaM от мая 20, 2011, 21:54
В={x|1<=х<=7, х натурал}

От блин, быстрее было все набрать в ряд эксплицитно.

Название: Дискретная математика
Отправлено: Квас от мая 20, 2011, 23:00

Озадачилсо.

Название: Дискретная математика
Отправлено: RawonaM от мая 20, 2011, 23:02

Цитата: Квас от мая 20, 2011, 23:00
Озадачилсо.

А что, разве не тривиально? inclusion-exclusion principle desu. Вот я и хотел узнать, есть ли другой способ решения.

Название: Дискретная математика
Отправлено: Квас от мая 20, 2011, 23:04

Цитата: RawonaM от мая 20, 2011, 23:02
А что, разве не тривиально? inclusion-exclusion principle desu. Вот я и хотел узнать, есть ли другой способ решения.

Многовато множеств. :-\

Название: Дискретная математика
Отправлено: RawonaM от мая 21, 2011, 12:26

Дано множество {4,5,6,...,60,61} и его подмножество А с 9 элементами.
С помощью принципа Дирихле доказывается, что в А есть по меньшей мере два подмножества, у которых сумма элементов равна.

Как отсюда следует, что существует по меньшей мере два непересекаемых подмножества А, у которых сумма равна?

Название: Дискретная математика
Отправлено: Квас от мая 21, 2011, 23:09

Цитата: RawonaM от мая 20, 2011, 21:50
У меня вышло 80856, если у кого есть желание тоже поковыряться и перепроверить, буду рад

Да!!! Я делил на 2 и ещё раз каждую на 2. Основывался на следующей формуле: a стейков и b шампуров можно разделить на 2 части так, чтобы все что-нибудь досталось, (a+1)(b+1)-2 способами, формула сбоит только при a=0=b. Вроде там сводится к суммированию арифметической прогрессии и квадратов, но я предпочёл напрячь комп.

Название: Дискретная математика
Отправлено: Квас от мая 21, 2011, 23:32

Цитата: RawonaM от мая 20, 2011, 20:33
Теперь такой вопрос по тому же: сколько инъективных фукций из А в В, при условии что для любого i в А, f(i)!=i?

Моя версия: $[tex]7\cdot 6\cdot 5\cdot 4 - 4\cdot 6^3 + 6\cdot 5^3 - 4\cdot 4 + 1 = 711[/tex]$

Кёскё ву дит?

А почему степени а не 6*5*4 и т. д.?

Брут форс даёт 465 вариантов. :o Ничего не сображаю. :'(

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 09:21

Цитата: Квас от мая 21, 2011, 23:09
ЦитироватьУ меня вышло 80856, если у кого есть желание тоже поковыряться и перепроверить, буду рад
Да!!! Я делил на 2 и ещё раз каждую на 2. Основывался на следующей формуле: a стейков и b шампуров можно разделить на 2 части так, чтобы все что-нибудь досталось, (a+1)(b+1)-2 способами, формула сбоит только при a=0=b. Вроде там сводится к суммированию арифметической прогрессии и квадратов, но я предпочёл напрячь комп.

Ну хорошо, что совпало. ;up: Это вообще-то решается инклужном-экслужном без прогрессий и компа. :)

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 09:25

Цитата: Квас от мая 21, 2011, 23:32
А почему степени а не 6*5*4 и т. д.?

И правда, почему?.. Наверное ошибка.
Но все равно ответ выходит 705, далеко от вашего брутфорса. А брутфорсу можно доверять?

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 09:55

Цитата: RawonaM от мая 22, 2011, 09:25
ЦитироватьА почему степени а не 6*5*4 и т. д.?
И правда, почему?.. Наверное ошибка.
Но все равно ответ выходит 705, далеко от вашего брутфорса. А брутфорсу можно доверять?

Мой калькулятор ошибся. Если сделать 6*4*5 и 5*4 вместо степеней, то как раз 465 и выходит. :)

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 10:02

Цитата: RawonaM от мая 21, 2011, 12:26
Дано множество {4,5,6,...,60,61} и его подмножество А с 9 элементами.
С помощью принципа Дирихле доказывается, что в А есть по меньшей мере два подмножества, у которых сумма элементов равна.

Как отсюда следует, что существует по меньшей мере два непересекаемых подмножества А, у которых сумма равна?

Тут что-нибудь подсказать можете? У меня в задании написано, как будто второе из первого банально следует. А я туплю :(

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 11:25

Дошло!!! :=

Название: Дискретная математика
Отправлено: Квас от мая 22, 2011, 20:19

Цитата: RawonaM от мая 21, 2011, 12:26
Дано множество {4,5,6,...,60,61} и его подмножество А с 9 элементами.
С помощью принципа Дирихле доказывается, что в А есть по меньшей мере два подмножества, у которых сумма элементов равна.

Как отсюда следует, что существует по меньшей мере два непересекаемых подмножества А, у которых сумма равна?

$[tex]A \setminus (A \cap B) \text{ et } B \setminus (A \cap B)[/tex]$
Кириллицу игнорирует.

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 23:24

Да я уже сам дошел. :) Но спасибо все равно :)

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 23:24

Никак до конца не врублюсь в рекурсивные определения. Странно это.

Название: Дискретная математика
Отправлено: Квас от мая 22, 2011, 23:26

Цитата: RawonaM от мая 22, 2011, 23:24
Никак до конца не врублюсь в рекурсивные определения. Странно это.

Что за зверь?

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 23:40

"Формула отката".

Вот простой пример: найти рекурсивную формулу вариантов расположения в линию эн метров из следующих досок: белые и желтые доски длиной два метра и зеленые длиной один метр?

Это я решаю легко: рекурсивная формула A_n=A_n-1+2A_n-2.

А вот это затрудняюсь:
Найти рекурсивную формулу для количества кусков образуемых эн окружностями на плоскости. Три окружности не пересекаются в одной точке.

Название: Дискретная математика
Отправлено: Квас от мая 22, 2011, 23:48

А, у нас их зовут рекуррентными формулами.

Цитата: RawonaM от мая 22, 2011, 23:40
Найти рекурсивную формулу для количества кусков образуемых эн окружностями на плоскости.

Топология, однако! Но тут же нет единственного решения: две непересекающиеся окружности делять плоскость на три куска, а две пересекающиеся — на 4.

Название: Дискретная математика
Отправлено: RawonaM от мая 22, 2011, 23:50

Цитата: Квас от мая 22, 2011, 23:48
Топология, однако! Но тут же нет единственного решения: две непересекающиеся окружности делять плоскость на три куска, а две пересекающиеся — на 4.

Забыл сказать, что указано что обязательно пересекаются и три окружности не пересекаются в одной точке никогда.

Название: Дискретная математика
Отправлено: Квас от мая 23, 2011, 00:30

Та-ак... Значит, у нас лежат n окружностей, которые делят плоскость на A_n частей. Предположим, что будем исходить из таких предпосылок:
1. Если «новая» окружность встречается с границей куска, то она встречается с ней ровно два раза и делит его на 2 части.
2. Всякая точка пересечения «новой» окружности со старой лежит на границе ровно двух смежных кусков.

Постулат 2 очевиден, а постулат 1 — что-то не очень. Из постулата 1 следует, что число полученных кусков равно
A_n+1 = A_n + B_n,
где B_n — число кусков, с которыми встретилась окружность. Из постулатов следует, что B_n равно числу точек пересечения новой окружности с имеющимися, то есть B_n = 2(n-1). Ainsi, on a
A_n+1 = A_n + 2(n-1).

Для n=2, 3, 4 работает.

Название: Дискретная математика
Отправлено: RawonaM от июня 2, 2011, 21:16

Цитата: Квас от мая 23, 2011, 00:30
где B_n — число кусков, с которыми встретилась окружность. Из постулатов следует, что B_n равно числу точек пересечения новой окружности с имеющимися, то есть B_n = 2(n-1). Ainsi, on a
A_n+1 = A_n + 2(n-1).

Для n=2, 3, 4 работает.

По ответу из учебника A_n+1 = A_n + 2n.
Вроде как понятно, но не знаю, за какое время я дошел бы до этого сам.

Вот этого не понимаю даже после того как прочитал ответ:
Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).
Если надо, напишу ответ, но может вам будет интереснее без ответа :)

Название: Дискретная математика
Отправлено: Квас от июня 2, 2011, 21:51

Цитата: RawonaM от июня 2, 2011, 21:16
Цитата: Квас от мая 23, 2011, 00:30где B_n — число кусков, с которыми встретилась окружность. Из постулатов следует, что B_n равно числу точек пересечения новой окружности с имеющимися, то есть B_n = 2(n-1). Ainsi, on a
A_n+1 = A_n + 2(n-1).

Для n=2, 3, 4 работает.
По ответу из учебника A_n+1 = A_n + 2n.

Другой ответ?! А у меня для n = 2, 3, 4 работает!

Цитата: RawonaM от июня 2, 2011, 21:16
Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).

То есть нужно найти число способов выбрать наборы $[tex](k_1,\ldots,k_n)[/tex]$ из целых неотрицательных чисел так, чтобы $[tex]k_1+\ldots+k_n=k[/tex]$ ?

Обозначим эту величину A_nk. Все способы выбора делятся на 2 группы: имеется предмет 1 типа или не имеется. Число групп, в которых предмета 1 типа нет, есть A^n-1,k. Пусть предмет 1 типа есть. Уберём один такой предмет и получим выбор k-1 предмета из n типов, число способов выбора равно A^n,k-1. Получаем
$[tex]A_{nk}= A_{n-1,k}+A_{n,k-1}.[/tex]$
Если дополнить очевидными соотношениями
$[tex]A_{1k}=1, \quad A_{n1}=n,[/tex]$
можно вычислить A_kn для любых натуральных k, n.

Название: Дискретная математика
Отправлено: RawonaM от июня 2, 2011, 22:09

Цитата: Квас от июня 2, 2011, 21:51
Цитата: RawonaM от июня 2, 2011, 21:16По ответу из учебника A_n+1 = A_n + 2n.
Другой ответ?! А у меня для n = 2, 3, 4 работает!

Ну вероятно вы плохо посчитали :)
По вашей формуле: А₂=А₁+2*0=2

Название: Дискретная математика
Отправлено: RawonaM от июня 2, 2011, 22:10

Цитата: Квас от июня 2, 2011, 21:51
Цитата: RawonaM от июня 2, 2011, 21:16Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).
То есть нужно найти число способов выбрать наборы $[tex](k_1,\ldots,k_n)[/tex]$ из целых неотрицательных чисел так, чтобы $[tex]k_1+\ldots+k_n=k[/tex]$ ?

Обозначим эту величину A_nk. Все способы выбора делятся на 2 группы: имеется предмет 1 типа или не имеется. Число групп, в которых предмета 1 типа нет, есть A^n-1,k. Пусть предмет 1 типа есть. Уберём один такой предмет и получим выбор k-1 предмета из n типов, число способов выбора равно A^n,k-1. Получаем
$[tex]A_{nk}= A_{n-1,k}+A_{n,k-1}.[/tex]$
Если дополнить очевидными соотношениями
$[tex]A_{1k}=1, \quad A_{n1}=n,[/tex]$
можно вычислить A_kn для любых натуральных k, n.

Не дается мне это сегодня :(

Название: Дискретная математика
Отправлено: RawonaM от июня 2, 2011, 22:51

Цитата: Квас от июня 2, 2011, 21:51
Цитата: RawonaM от июня 2, 2011, 21:16Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).
То есть нужно найти число способов выбрать наборы $[tex](k_1,\ldots,k_n)[/tex]$ из целых неотрицательных чисел так, чтобы $[tex]k_1+\ldots+k_n=k[/tex]$ ?

Обозначим эту величину A_nk. Все способы выбора делятся на 2 группы: имеется предмет 1 типа или не имеется. Число групп, в которых предмета 1 типа нет, есть A^n-1,k. Пусть предмет 1 типа есть. Уберём один такой предмет и получим выбор k-1 предмета из n типов, число способов выбора равно A^n,k-1. Получаем
$[tex]A_{nk}= A_{n-1,k}+A_{n,k-1}.[/tex]$
Если дополнить очевидными соотношениями
$[tex]A_{1k}=1, \quad A_{n1}=n,[/tex]$

Как я рассуждал над этой задачей: рассмотрим выбор k-1 предметов, их можно дополнить еще одним из n предметов и будет A_nk, поэтому A_n,k=n*А_n,k-1.
Это неправильно? Недостаточно рекурсивно?

В книге ответ совершенно отличный и от вашего и от моего подавно. Ответ такой:
f(n,k)=f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,1)+1

Название: Дискретная математика
Отправлено: RawonaM от июня 2, 2011, 23:46

f(n) — количество последовательностей цифр 1-8 длиной n, таких, в которых четные цифры не стоят рядом друг с другом. Найти рекурсивное отношение f(n). Мое решение:

Обозначим fodd(n) — количество таких последовательностей, в которых первая цифра нечетная.
feven(n) — количество таких последовательностей, в которых первая цифра четная.

Следовательно:
$[tex]f(n)=fodd(n)+feven(n)\\ fodd(n)=4f(n-1)\\ feven(n)=4fodd(n-1)=4\cdot4f(n-2)\\ f(n)=4f(n-1)+16f(n-2)[/tex]$

С помощью комбинаторики:
$[tex]f(0)=1[/tex]$
$[tex]f(1)=8[/tex]$
$[tex]f(2)=8^2-4^2=48[/tex]$

С другой стороны по найденной формуле:
$[tex]f(2)=4\cdot8+16\cdot1=48 [/tex]$

Все верно?

Название: Дискретная математика
Отправлено: Квас от июня 2, 2011, 23:50

Цитата: RawonaM от июня 2, 2011, 22:51
Как я рассуждал над этой задачей: рассмотрим выбор k-1 предметов, их можно дополнить еще одним из n предметов и будет A_nk, поэтому A_n,k=n*А_n,k-1.
Это неправильно? Недостаточно рекурсивно?

Эта формула должна порушиться уже на небольших n и k.

Цитата: RawonaM от июня 2, 2011, 22:51
f(n,k)=f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,1)+1

Если моё расписать, вроде то же получается.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 08:24

Цитата: Квас от июня 2, 2011, 23:50
Эта формула должна порушиться уже на небольших n и k.

А где ошибка в рассуждении?

Обращаю внимание:

Цитата: RawonaM от июня 2, 2011, 23:46
f(n) — количество последовательностей цифр 1-8 длиной n, таких, в которых четные цифры не стоят рядом друг с другом. Найти рекурсивное отношение f(n). Мое решение:

А то вы часто сообщения пропускаете, несмотря на предупреждение о новых сообщениях :)

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 10:59

Цитата: RawonaM от июня 2, 2011, 23:46
$[tex]f(n)=4f(n-1)+16f(n-2)[/tex]$

Отсюда также надо вывести прямую функцию, у меня получилось так:
$[tex]f(n)=\left(\frac12+\frac3{\sqrt{20}}\right)\left(2+\sqrt{20}\right)^n+\left(\frac12-\frac3{\sqrt{20}}\right)\left(2-\sqrt{20}\right)^n[/tex]$

Что думаете? :)

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 16:40

У меня есть $[tex](1+x+x^2+x^3)^2[/tex]$ , как это представить сигмой от 0 до бесконечность? Должен быть или D(n,k) какой-нить что ли...

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 16:57

Цитата: RawonaM от июня 2, 2011, 23:46
Все верно?

Ошибок не нашёл.

Цитата: RawonaM от июня 3, 2011, 08:24

Цитата: Квас от июня 2, 2011, 23:50Эта формула должна порушиться уже на небольших n и k.
А где ошибка в рассуждении?

Вы выбираете набор $[tex]x = (k_1,\ldots,k_n)[/tex]$ и на его основе делаете набор y, прибавив 1 к одной из компонент. Но таким путём y можно получить из разных х.

Стоит помнить, что за общими рассуждениями стоят судьбы совершенно конкретных k и n. Поэтому никогда не повредит изучить, что происходит при их небольших значениях.

Цитата: RawonaM от июня 3, 2011, 08:24
Цитата: RawonaM от июня 2, 2011, 23:46f(n) — количество последовательностей цифр 1-8 длиной n, таких, в которых четные цифры не стоят рядом друг с другом. Найти рекурсивное отношение f(n). Мое решение:

А то вы часто сообщения пропускаете, несмотря на предупреждение о новых сообщениях :)

Я не пропустил, я не имел переваренным (плюсквамперфект!). :)

Цитата: RawonaM от июня 3, 2011, 10:59
Что думаете? :)

Формула правильная. :yes:

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 16:59

Цитата: RawonaM от июня 3, 2011, 16:40
У меня есть $[tex](1+x+x^2+x^3)^2[/tex]$ , как это представить сигмой от 0 до бесконечность? Должен быть или D(n,k) какой-нить что ли...

Многочлен бесконечной суммой? :???

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 17:01

Цитата: Квас от июня 3, 2011, 16:59
Цитата: RawonaM от июня 3, 2011, 16:40У меня есть $[tex](1+x+x^2+x^3)^2[/tex]$ , как это представить сигмой от 0 до бесконечность? Должен быть или D(n,k) какой-нить что ли...
Многочлен бесконечной суммой? :???

А что, нельзя? Просто лишние слагаемые будут нули.

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 17:08

Если раскрыть скобки, будет
$[tex]1+2\,x+3\,{x}^{2}+4\,{x}^{3}+3\,{x}^{4}+2\,{x}^{5}+{x}^{6}[/tex]$

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 17:37

У меня есть полином $[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2[/tex]$ , нужно найти f(n) — коэффициент хⁿ в этом полиноме.

Я вот что сделал:
(по формулам)
$[tex](1+x+x^2+x^3)=\frac{1-x^{4}}{1-x}[/tex]$ $[tex](1+x+x^2+x^3...)=\frac{1}{1-x}[/tex]$

Отсюда:

$[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2=\frac{(1-x^{4})^2}{(1-x)^2}\cdot\frac{1}{(1-x)^2}=\\\\=(1-x^4)^2(1-x)^{-4}=(1-x)^{-4}-2x^4(1-x)^{-4}+x^8(1-x)^{-4}[/tex]$

Поэтому:

$[tex]f(n)=D(4,n)-2D(4,n-4)+D(4,n-8)=\\\\=\binom{3+n}n - 2 \binom{3+n}{n-4} + \binom{3+n}{n-8}[/tex]$

Нормально?

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 20:30

Цитата: RawonaM от июня 3, 2011, 17:37
Я вот что сделал:
(по формулам)
$[tex](1+x+x^2+x^3)=\frac{1-x^{4}}{1-x}[/tex]$ $[tex](1+x+x^2+x^3...)=\frac{1}{1-x}[/tex]$

Отсюда:

$[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2=\frac{1-x^{4}}{1-x}\cdot\frac{1}{(1-x)^2}=\\\\=(1-x^4)^2(1-x)^{-4}=(1-x)^{-4}-2x^4(1-x)^{-4}+x^8(1-x)^{-4}[/tex]$

Поэтому:

Вообще не понимаю эти выкладки.
$[tex]1+x+x^2+x^3 = \frac{1-x^4}{1-x}[/tex]$
$[tex]1+x+x^2+x^3+\ldots = \frac{1}{1-x} \quad(|x|<1)[/tex]$
$[tex](1+x+x^2+x^3)^2(1+x+x^2+x^3+\ldots) = \frac{(1-x^4)^2}{(1-x)^3}\quad(|x|<1)[/tex]$

А D(k,n) — что за обозначение?

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 20:34

Цитата: Квас от июня 3, 2011, 20:30
Вообще не понимаю эти выкладки.

А что именно непонятно? Вы же то же самое повторили... Только начало.

Цитата: Квас от июня 3, 2011, 20:30
А D(k,n) — что за обозначение?

$[tex]D(k,n)=\binom{n+k-1}{n}[/tex]$

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 20:38

Там небольшая ошибка закралась, я поправил, но она какбе ни на что не влияет.

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 21:07

Цитата: RawonaM от июня 3, 2011, 17:37
Отсюда:

$[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2=\frac{(1-x^{4})^2}{(1-x)^2}\cdot\frac{1}{(1-x)^2}=\\\\=(1-x^4)^2(1-x)^{-4}=(1-x)^{-4}-2x^4(1-x)^{-4}+x^8(1-x)^{-4}[/tex]$

Поэтому:

$[tex]f(n)=D(4,n)-2D(4,n-4)+D(4,n-8)=\\\\=\binom{3+n}n - 2 \binom{3+n}{n-4} + \binom{3+n}{n-8}[/tex]$

Нормально?

Ah, ça y est ! В первой строке я принял пробел за умножение, и недопонимание усугубилось четвёртой степенью в знаменателе. (Мне сегодня простительно: студенты сокрушили. Последняя пересдача, зачёт получили 3 из 8. :green:)

Ваша идея ясна. Но прямое вычисление показывает, что ответ неправильный. Разложение, на которое мы опираемся, имеет вид
$[tex](1-x)^{-4}=\Sum_{n=0}^\infty \frac{(3+n)!}{3!n!}[/tex]$ ,
и если вместо D(4,n) взять
$[tex]k(n) = \frac{(3+n)!}{3!n!},[/tex]$
то получается то, что надо.

(Я уже начинаю вам завидовать белой завистью. А откуда задания, это задачники такие?)

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 21:18

Цитата: Квас от июня 3, 2011, 21:07
(Мне сегодня простительно: студенты сокрушили. Последняя пересдача, зачёт получили 3 из 8. :green:)

Действительно простительно. Сочувствую :)

Цитата: Квас от июня 3, 2011, 21:07
и если вместо D(4,n) взять
$[tex]k(n) = \frac{(3+n)!}{3!n!},[/tex]$
то получается то, что надо.

Так $[tex]D(4,n)=\binom{n+3}{n}=\frac{(3+n)!}{3!n!}[/tex]$ .
Чего ж тогда не сходится?

Цитата: Квас от июня 3, 2011, 21:07
(Я уже начинаю вам завидовать белой завистью. А откуда задания, это задачники такие?)

Это домашнее задание :) Ну я в книге все прорешал, вот делаю работу на сдачу, но че-то сложноватый это материал немножко, целый день сижу.

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 21:31

Цитата: RawonaM от июня 3, 2011, 21:18
Так $[tex]D(4,n)=\binom{n+3}{n}=\frac{(3+n)!}{3!n!}[/tex]$ .
Чего ж тогда не сходится?

А, сообразил! Я сравнивал разложение в ряд и вычисленные коэффициенты. Если коэффициенты забивать через факториалы, то работает начиная с 8-й степени (потому что должно быть n-8 ≥ 0); если забить формулу для D, работает начиная с $[tex]\inline x^5[/tex]$ . А меня несовпадение первых членов смутило.

Цитата: RawonaM от июня 3, 2011, 21:18
Цитата: Квас от июня 3, 2011, 21:07(Я уже начинаю вам завидовать белой завистью. А откуда задания, это задачники такие?)
Это домашнее задание :) Ну я в книге все прорешал, вот делаю работу на сдачу, но че-то сложноватый это материал немножко, целый день сижу.

Классные дидактические материалы! ;up: По всем предметам. Мне в универе отродясь таких интересных задач решать не приходилось. Но, блин, наши студенты — лучший демотиватор.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 21:45

Цитата: Квас от июня 3, 2011, 21:31
А, сообразил! Я сравнивал разложение в ряд и вычисленные коэффициенты. Если коэффициенты забивать через факториалы, то работает начиная с 8-й степени (потому что должно быть n-8 ≥ 0); если забить формулу для D, работает начиная с $[tex]\inline x^5[/tex]$ . А меня несовпадение первых членов смутило.

Так все правильно значит? А то я уже на чистовик написал))

Цитата: Квас от июня 3, 2011, 21:31
Классные дидактические материалы! ;up: По всем предметам. Мне в универе отродясь таких интересных задач решать не приходилось. Но, блин, наши студенты — лучший демотиватор.

Ваши слова придают мне гордости и мотивации. ;D А что, сильно могут отличаться эти задачки? Плюс-минус ведь все одно и то же. Может это сейчас они вам интересными кажутся, а раньше как-то были не очень?

Я вот курсом логики совсем не доволен. Просто беспредел какой-то, а не логика. :(

Название: Дискретная математика
Отправлено: Bhudh от июня 3, 2011, 21:46

Так у тебя же свой есть!
«Хочешь выучить предмет — ~~начни~~ продолжь его преподавать!»

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 21:53

Цитата: RawonaM от июня 3, 2011, 21:45
А то я уже на чистовик написал))

Не забудьте пояснить, что для первых нескольких степеней формула не работает. Потому что во втором или третьем слагаемых младшие степени отсутствуют.

Цитата: RawonaM от июня 3, 2011, 21:45
А что, сильно могут отличаться эти задачки? Плюс-минус ведь все одно и то же. Может это сейчас они вам интересными кажутся, а раньше как-то были не очень?

Одно дело — где считать надо, другое — где думать. У вас думательные, а техника получается как само собой разумеющееся. У нас такие задачи бывали главным образом для теоретических экзаменов, и не все ими занимались; на практических занятиях — более или менее рутинные вычисления.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 22:13

Цитата: Bhudh от июня 3, 2011, 21:46
«Хочешь выучить предмет — ~~начни~~ продолжь его преподавать!»

Я все хочу продолжить вместе с ходом курса в универе, но никак не доберусь. Вероятно опять отложится. Месяц до сессии, а у меня три курса и еще куча всего не сделано.
Хотя кто его знает, может оно того стоит, это поможет к экзамену подготовиться... В воскресение попробую че-нить написать, если не забуду.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 22:14

Цитата: Квас от июня 3, 2011, 21:53
Цитата: RawonaM от июня 3, 2011, 21:45А то я уже на чистовик написал))
Не забудьте пояснить, что для первых нескольких степеней формула не работает. Потому что во втором или третьем слагаемых младшие степени отсутствуют.

Почему не работает? Степени отсутствуют, значит 0 прибавится.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 22:15

Бином же определен, что если нижнее число отрицательное, то все значение — 0.

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 22:36

Цитата: RawonaM от июня 3, 2011, 22:15
Бином же определен, что если нижнее число отрицательное, то все значение — 0.

Значит, мэпл этого не знает. Тогда ладно, живите. :)

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 23:27

Вот тут последнее задание, замучился с ним нет сил уже, и не хочу на завтра оставлять. Помогайте :)

Дано тождество $[tex]\frac{(1-x^2)}{(1-x)^n}=(1+x)^n[/tex]$ .

Нужно вычислить функцию f(m) коэффициентов x^2m с обоих сторон независимо. Справа банально — $[tex]\binom{n}{2m}[/tex]$ .

Слева нужно чтобы была сигма. Есть вариант разложить на три суммы, есть на две. Там где на три, выходит слишком запутанно, и требование 2m намекает, что должно быть похоже две суммы. Итак:

$[tex](1-x^2)^n\cdot \frac1{(1-x)^n}=\sum_{i=1}^\infty a_i x^{2i} \sum_{i=1}^\infty b_i x^{i}[/tex]$

$[tex]a_i=(-1)^i\binom n{i}[/tex]$

$[tex]b_i=D(n,i)[/tex]$

Дальше по формуле умножения таких функций коэффициенты x^k будут:
$[tex]c_k=\sum_{i=0}^k a_i b_{k-i}[/tex]$

Но у меня ниче не выходит :( Застрял тут и все.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 23:36

Цитата: RawonaM от июня 3, 2011, 23:27
$[tex]c_k=\sum_{i=0}^k a_i b_{k-i}[/tex]$

Вроде как теперь просто подставить 2m:
$[tex]c_{2m}=\sum_{i=0}^{2m} a_i b_{2m-i}[/tex]$ ?
Надо посчитать...

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 23:38

Цитата: RawonaM от июня 3, 2011, 23:27
Дальше по формуле умножения таких функций коэффициенты x^k будут:
$[tex]c_k=\sum_{i=0}^k a_i b_{k-i}[/tex]$

Так как a_i — коэффициент при степени 2i, то
$[tex]c_{2m}=\sum_{i=0}^m a_i b_{2m-2i}[/tex]$
Теперь надо доказывать, что это равно $[tex]\binom{n}{2m}[/tex]$ ?

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 23:46

Цитата: Квас от июня 3, 2011, 23:38
Теперь надо доказывать, что это равно $[tex]\binom{n}{2m}[/tex]$ ?

Достаточно проверить для n=5, m=2,3. Попытался вычислить, вроде не сошлось :(

Название: Дискретная математика
Отправлено: Квас от июня 3, 2011, 23:52

Цитата: RawonaM от июня 3, 2011, 23:46
Цитата: Квас от июня 3, 2011, 23:38Теперь надо доказывать, что это равно $[tex]\binom{n}{2m}[/tex]$ ?
Достаточно проверить для n=5, m=2,3. Попытался вычислить, вроде не сошлось :(

А по моей формуле сходится: 5 и 0.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 23:53

Цитата: Квас от июня 3, 2011, 23:52
А по моей формуле сходится: 5 и 0.

Я по вашей и считал. Сейчас опять попробую.

Название: Дискретная математика
Отправлено: RawonaM от июня 3, 2011, 23:56

Цитата: Квас от июня 3, 2011, 23:38
$[tex]c_{2m}=\sum_{i=0}^m a_i b_{2m-2i}[/tex]$

А почему у вас сумма бежит до m?..

Название: Дискретная математика
Отправлено: RawonaM от июня 4, 2011, 00:02

По вашему варианту: при n=5, m=2, c₄=30.

4 из 5 будет 5. Не сходится. Как у вас сошлось?

Название: Дискретная математика
Отправлено: Квас от июня 4, 2011, 00:04

Цитата: RawonaM от июня 3, 2011, 23:56
Цитата: Квас от июня 3, 2011, 23:38 $[tex]c_{2m}=\sum_{i=0}^m a_i b_{2m-2i}[/tex]$
А почему у вас сумма бежит до m?..

Поскольку a_i стоит при x²ⁱ, то перебираем как раз степени от 0 до 2m.

Название: Дискретная математика
Отправлено: RawonaM от июня 4, 2011, 00:07

Цитата: Квас от июня 4, 2011, 00:04
Поскольку a_i стоит при x²ⁱ, то перебираем как раз степени от 0 до 2m.

Получается мы скачем через один? У меня три слагаемых в с₄:
D(5,4)-5D(5,2)+10D(5,0)=30.

Название: Дискретная математика
Отправлено: Квас от июня 4, 2011, 00:09

n = 5:
a₀ = 1, a₁ = -5, a₂ = 10
b₄ = 70, b₂ = 15, b₀ = 1

1 ∙ 70 - 5 ∙ 15 + 10 ∙ 1 = 5

Название: Дискретная математика
Отправлено: RawonaM от июня 4, 2011, 00:14

Точно, это я прогнал. :scl:

Я все-таки не понимаю, почему мы бежим через один. Разве не пропускаются таким образом множители и слагаемые? Но над этим я уже буду размышлять в другой раз...

Название: Дискретная математика
Отправлено: Квас от июня 4, 2011, 00:16

Цитата: RawonaM от июня 4, 2011, 00:14
Я все-таки не понимаю, почему мы бежим через один. Разве не пропускаются таким образом множители и слагаемые? Но над этим я уже буду размышлять в другой раз...

Слагаемые из первой скобки автоматом получаются только чётной степени. Поэтому чтобы получить чётную суммарную степень, нужно брать только чётные степени и из второй скобки.

Название: Дискретная математика
Отправлено: RawonaM от июня 4, 2011, 00:21

Цитата: Квас от июня 4, 2011, 00:16
Цитата: RawonaM от июня 4, 2011, 00:14Я все-таки не понимаю, почему мы бежим через один. Разве не пропускаются таким образом множители и слагаемые? Но над этим я уже буду размышлять в другой раз...
Слагаемые из первой скобки автоматом получаются только чётной степени. Поэтому чтобы получить чётную суммарную степень, нужно брать только чётные степени и из второй скобки.

А, точно!

Спасибо, Квас!)

Дописываю и иду спать с опозданием. :)

Название: Дискретная математика
Отправлено: Квас от июня 4, 2011, 00:23

Спокойной ночи! :)

Название: Дискретная математика
Отправлено: RawonaM от июня 4, 2011, 00:32

Bonne nuit :)

Название: Дискретная математика
Отправлено: RawonaM от июня 10, 2011, 20:19

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

Представить натуральные числа как бесконечное объединение бесконечных непересекаемых множеств.

Название: Дискретная математика
Отправлено: Bhudh от июня 10, 2011, 20:22

{{1}, {2}, {3}, {...}, {n}}

Название: Дискретная математика
Отправлено: Квас от июня 10, 2011, 20:25

Цитата: Bhudh от июня 10, 2011, 20:22
{{1}, {2}, {3}, {...}, {n}}

Надо, чтобы объединяемые множества были бесконечными.

Название: Дискретная математика
Отправлено: RawonaM от июня 10, 2011, 20:27

Ага. Я знаю два варианта ответа, если кто придумал один, продолжайте искать второй :) В принципе вариантов можно построить бесконечное количество.

Название: Дискретная математика
Отправлено: Alone Coder от июня 10, 2011, 20:33

Сходу придумал два варианта:
1. 2n-1, 2(2n-1), 4(2n-1), ...
2. Строки таблицы, заполняемой с угла.
1 3 6 10 15 ... = ((n+1)²-(n+1))/2 - 0
2 5 9 14 ... = ((n+2)²-(n+2))/2 - 1
4 8 13 ... = ((n+3)²-(n+3))/2 - 2
7 12 ... = ((n+4)²-(n+4))/2 - 3
11 ... = ((n+5)²-(n+5))/2 - 4
...

Название: Дискретная математика
Отправлено: Alone Coder от июня 10, 2011, 20:34

3. Сумма цифр равна 1, 2, 3, 4, ... (разные системы счисления дают разное разбиение)

Название: Дискретная математика
Отправлено: Alone Coder от июня 10, 2011, 20:36

4. Наименьший простой множитель равен m-му простому числу (где m - номер множества).

Название: Дискретная математика
Отправлено: Alone Coder от июня 10, 2011, 20:37

5. Имеет m простых множителей.

Название: Дискретная математика
Отправлено: RawonaM от июня 11, 2011, 11:35

Вопрос: дана таблица отношения, как визуально определить, является ли релация транзитивной?
Уже долго пытаюсь построить алгоритм в голове, получается запутанно.

Симметричность/антисимметричность, рефлексивность — это легко видно визуально и легко дополняется. А вот с транзитивностью непонятно.

Название: Дискретная математика
Отправлено: RawonaM от июня 11, 2011, 11:38

Как быстро построить в голове R²?

Название: Дискретная математика
Отправлено: arseniiv от июня 11, 2011, 11:54

Визуально транзитивность определить, наверно, трудно. Но есть алгоритм построения транзитивного замыкания, который можно провести над матрицей отношения, и если в результате получится то же отношение — оно транзитивно. Алгоритм имени двух забыл кого.

Название: Дискретная математика
Отправлено: Квас от июня 11, 2011, 14:10

Цитата: RawonaM от июня 11, 2011, 11:35
Как быстро построить в голове R²?

Возможно ли это? «Знакомые знакомых»? :-\

Название: Дискретная математика
Отправлено: Квас от июня 11, 2011, 14:12

Цитата: Alone Coder от июня 10, 2011, 20:33
2. Строки таблицы, заполняемой с угла.

И ещё можно по-разному заполнять: прямоугольниками разной формы или другими фигурами.

Название: Дискретная математика
Отправлено: RawonaM от июня 13, 2011, 23:05

У нас в книге quasi-order названо транзитивное и антирефлексивное отношение, а на педии

Цитата: http://en.wikipedia.org/wiki/Quasi-orderingIn mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.

... The name quasi-order is also common for preorders.

Чем это можно объяснить?..

Вопрос: матрица частично упорядоченного отношения всегда может принять треугольный вид?

Название: Дискретная математика
Отправлено: RawonaM от июня 13, 2011, 23:21

http://books.google.com/books?id=TSmQYJplg0cC (http://books.google.com/books?id=TSmQYJplg0cC&pg=PA41&lpg=PA41&dq=quasi+order+antireflexive&source=bl&ots=MbsYsazZ_S&sig=BIJokIOJvdx3GVYvd1GHw-QO6Hk&hl=fr&ei=3m32TcLPKIGVOtiOqZ8H&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDQQ6AEwAw#v=onepage&q=quasi%20order%20antireflexive&f=false)

Тут даны определения отношений, судя по этому у нас в книге имелось в виду pseudo-order, но на педии опять же pseudo-order определен с еще одним условием:
(wiki/en) Pseudo-order (http://en.wikipedia.org/wiki/Pseudo-order)

Запутался вообще.

Название: Дискретная математика
Отправлено: Квас от июня 13, 2011, 23:23

Цитата: RawonaM от июня 13, 2011, 23:05
У нас в книге quasi-order названо транзитивное и антирефлексивное отношение, а на педии

ЦитироватьIn mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.

... The name quasi-order is also common for preorders.
Чем это можно объяснить?..

Существенной разницы нет, как между < и ≤. Однако обычно используют рефлексивные отношения.

Цитата: RawonaM от июня 13, 2011, 23:05
Вопрос: матрица частично упорядоченного отношения всегда может принять треугольный вид?

Простейшие примеры вроде подтверждают. Может, по индукции? Есть конечное множество X с отношением частичного порядка. Выберем некоторый максимальный элемент a (очевидно, существует) и занумеруем его 1. По предположению индукции множество X\{a} можно занумеровать так, что i ≺ j ⇒ i ≤ j (элементы отождествляю с номерами). Получаем нумерацию, для которой матрицы диагональна.

Название: Дискретная математика
Отправлено: RawonaM от июня 13, 2011, 23:36

Цитата: Квас от июня 13, 2011, 23:23
Существенной разницы нет

В точности формулировок и терминов нет разницы??!! :o

Там ошибка в определении же, похоже.

Название: Дискретная математика
Отправлено: RawonaM от июня 13, 2011, 23:37

Цитата: Квас от июня 13, 2011, 23:23
Цитата: RawonaM от июня 13, 2011, 23:05Вопрос: матрица частично упорядоченного отношения всегда может принять треугольный вид?
Простейшие примеры вроде подтверждают. Может, по индукции? Есть конечное множество X с отношением частичного порядка. Выберем некоторый максимальный элемент a (очевидно, существует) и занумеруем его 1. По предположению индукции множество X\{a} можно занумеровать так, что i ≺ j ⇒ i ≤ j (элементы отождествляю с номерами). Получаем нумерацию, для которой матрицы диагональна.

Это я вывел методом рисования на бумаге многих отношений. Просто хотелось понять, вот я дошел до этого свойства :)

Название: Дискретная математика
Отправлено: Квас от июня 13, 2011, 23:45

Цитата: RawonaM от июня 13, 2011, 23:37
Это я вывел методом рисования на бумаге многих отношений. Просто хотелось понять, вот я дошел до этого свойства :)

:up: Это настоящий математический подход!

Цитата: RawonaM от июня 13, 2011, 23:36
В точности формулировок и терминов нет разницы??!! :o

Комильфо считать отношения порядка рефлексивными. Но если автор в определении пишет «антирефлексивный», остаётся только развести руками и читать дальше. Как Кэррол сказал: «If I find an author saying, at the beginning of his book. "Let it be understood that by the word 'black' I shall always mean 'white', and that by the word 'white' I shall always mean 'black', " I meekly accept his ruling, however injudicious I may think it.»

Ошибка в определение могла вкрасться.

В виноградовской энциклопедии насчёт псевдопорядка ничего не нашёл. Предпорядком или квазипорядком у него названо рефлексивное и транзитивное отношение.

Название: Дискретная математика
Отправлено: RawonaM от июня 13, 2011, 23:54

Цитата: Квас от июня 13, 2011, 23:45
Цитата: RawonaM от июня 13, 2011, 23:37Это я вывел методом рисования на бумаге многих отношений. Просто хотелось понять, вот я дошел до этого свойства :)
:up: Это настоящий математический подход!

По-моему не очень :) Я еще вот что вывел: если есть наименьший элемент, то это первая строка в матрице и она будет вся заполнена. Если она не вся заполнена, нет наименьшего. Точно так же если есть наибольший элемент, то весь последний столбец заполнен. Я правда в этом еще не очень уверен. С минимальными и максимальными еще не понял.

Цитата: Квас от июня 13, 2011, 23:45
Предпорядком или квазипорядком у него названо рефлексивное и транзитивное отношение.

Ну вот, а у нас почему-то антирефлексивное и транзитивное. Ошибка видимо. И не могу на форум курса написать...

Название: Дискретная математика
Отправлено: RawonaM от июня 13, 2011, 23:55

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

Название: Дискретная математика
Отправлено: RawonaM от июня 18, 2011, 22:02

Я задавал этот вопрос выше, вот нашел ответ:

Цитата: http://jeff560.tripod.com/set.htmlThe aleph null symbol was conceived by Georg Cantor (1845-1918) around 1893, and became widely known after "Beiträge zur Begründung der transfiniten Mengenlehre" [Contributions to the Foundation of Transfinite Set Theory] saw the light in Mathematische Annalen, Band XLVI [vol. 46], B. G. Teubner, Leipzig, 1895.

On page 492 of this prestigious journal we find the paragraph Die kleinste transfinite Cardinalzahl Alef-null [The minimum transfinite cardinal number Aleph null], and the following:

...wir nennen die ihr zukommende Cardinalzahl, in Zeichen, *Alef-null* ... [We call the cardinal number related to that (set); in symbol, *Alef-null*]

In a letter dated April 30, 1895, Cantor wrote, "it seemed to me that for this purpose, other alphabets were [already] over-used" (translation by Martin Davis).

In Georg Cantor, Dauben (page 179) says that Cantor did not want to use Roman or Greek alphabets, because they were already widely used, and "His new numbers deserved something unique. ... Not wishing to invent a new symbol himself, he chose the aleph, the first letter of the Hebrew alphabet...the aleph could be taken to represent new beginnings...." Avinoam Mann points out that aleph is also the first letter of the Hebrew word "Einsof," which means infinity and that the Kabbalists use "einsof" for the Godhead.

(wiki/he) אלף_אפס

ב тоже используется.

Название: Дискретная математика
Отправлено: RawonaM от июня 24, 2011, 17:09

Интересная задачка: K_n — количество вариантов разбиений множества {1,2,3...n} так, что в каждой группе будет не более двух элементов. Например для {1,2,3,4,5,6} возможный вариант {{1},{2,3},{4},{5,6}}.

Найти рекурсивую формулу для K_n.

Я ниасилил :( То есть может быть если бы я на нее еще два часа убил, осилил бы, но времени жалко.

Название: Дискретная математика
Отправлено: RawonaM от июня 24, 2011, 20:25

Никто не хочет попытаться?

Вот еще классная задача (решение я знаю, просто кому интересно):

Дано множество А из 100 чисел. Докажите, что есть непустое подмножество, чья сумма членов делится на 100.

Название: Дискретная математика
Отправлено: Квас от июня 24, 2011, 21:06

Цитата: RawonaM от июня 24, 2011, 17:09
Интересная задачка: K_n — количество вариантов разбиений множества {1,2,3...n} так, что в каждой группе будет не более двух элементов. Например для {1,2,3,4,5,6} возможный вариант {{1},{2,3},{4},{5,6}}.

Найти рекурсивую формулу для K_n.

Та-ак. Разбиения рассматриваемого типа назовём хорошими. Множество хороших разбиений множества {1,2,3...n} разбивается на два класса: 1) разбиения, содержащие {n}; 2) разбиения, не содержащие {n}.

Разбиения первого класса находятся в биективном соответствии с хорошими разбиениями множества {1,...n-1}, поэтому первый класс содержит K_n-1 разбиений.

Каждое из разбиений второго класса содержит единственное множество вида {n, k}, где k ≠ n. Следовательно, второй класс разбивается на n-1 подкласс в зависимости от k. Ясно, что каждый подкласс находится в биективном соответствии с множеством хороших разбиений множества {1,...,n-2}, поэтому число разбиений класса 2) равно (n-1)K_n-2.

Всего
K_n = K_n-1 + (n-1)K_n-2, n ≥ 3.
Для полного счастья: K₁=1, K₂=2.

Название: Дискретная математика
Отправлено: RawonaM от июня 24, 2011, 21:15

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

Название: Дискретная математика
Отправлено: RawonaM от июня 24, 2011, 21:19

Оказывается такие разбиения называются инволюциями: (wiki/en) Involution_(mathematics) (http://en.wikipedia.org/wiki/Involution_%28mathematics%29)

Название: Дискретная математика
Отправлено: RawonaM от июня 24, 2011, 21:19

Там есть и рекуррентная формула, и прямая.

Название: Дискретная математика
Отправлено: 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

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

Название: Дискретная математика
Отправлено: 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

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

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

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

Название: Дискретная математика
Отправлено: 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 от октября 6, 2011, 20:02

Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

Название: Дискретная математика
Отправлено: Квас от октября 6, 2011, 20:28

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

Отображение $[tex][0,1)\to [0,1)\times [0,1)[/tex]$ — вообще легко.

Возьмём x ∈ [0, 1], x ≠ 1. Это число однозначно записывается бесконечной десятичной дробью, не оканчивающейся последовательностью девяток:
$[tex]x = 0{,}x_1x_2\ldots[/tex]$
Положим
$[tex]f_1 (x) = 0{,}x_1x_3x_5\ldots[/tex]$
$[tex]f_2 (x) = 0{,}x_2x_4x_6\ldots[/tex]$
Отображение f(x) = (f₁(x), f₁(x)) будет биекцией.

Но это мы две стороны квадрата выбросили. В принципе, можно взять отрезок [0,2], полуинтервал [0,1) отобразить на квадрат без двух сторон, а отрезок [1,2] — биективно на две оставшиеся стороны.

Название: Дискретная математика
Отправлено: RawonaM от октября 6, 2011, 20:39

Цитата: Квас от октября 6, 2011, 20:28
Возьмём x ∈ [0, 1], x ≠ 1. Это число однозначно записывается бесконечной десятичной дробью, не оканчивающейся последовательностью девяток:
$[tex]x = 0{,}x_1x_2\ldots[/tex]$
Положим
$[tex]f_1 (x) = 0{,}x_1x_3x_5\ldots[/tex]$
$[tex]f_2 (x) = 0{,}x_2x_4x_6\ldots[/tex]$
Отображение f(x) = (f₁(x), f₁(x)) будет биекцией.

У меня была такая идея. Но как доказать, что это биекция? Как можно знать, что мы все покроем?

Цитата: Квас от октября 6, 2011, 20:28
Но это мы две стороны квадрата выбросили. В принципе, можно взять отрезок [0,2], полуинтервал [0,1) отобразить на квадрат без двух сторон, а отрезок [1,2] — биективно на две оставшиеся стороны.

Ну тогда можно просто взять [0;0.5) отобразить на квадрат без двух сторон, а [0.5,1] на две стороны.

Название: Дискретная математика
Отправлено: Квас от октября 6, 2011, 21:05

Цитата: RawonaM от октября 6, 2011, 20:39
Цитата: Квас от октября 6, 2011, 20:28Возьмём x ∈ [0, 1], x ≠ 1. Это число однозначно записывается бесконечной десятичной дробью, не оканчивающейся последовательностью девяток:
$[tex]x = 0{,}x_1x_2\ldots[/tex]$
Положим
$[tex]f_1 (x) = 0{,}x_1x_3x_5\ldots[/tex]$
$[tex]f_2 (x) = 0{,}x_2x_4x_6\ldots[/tex]$
Отображение f(x) = (f₁(x), f₁(x)) будет биекцией.
У меня была такая идея. Но как доказать, что это биекция? Как можно знать, что мы все покроем?

Так очевидно же. Инъективность вообще очевидна. Сюръективность: пара
$[tex](y,z)\colon y=0{,}y_1y_2\ldots,\ z=0{,}z_1z_2\ldots[/tex]$
покрывается числом
$[tex]0{,}y_1z_1y_2z_2\ldots[/tex]$
Единственное, надо иногда делать оговорки насчёт хвоста из девяток, но он нигде не появляется на самом деле.

Цитата: RawonaM от октября 6, 2011, 20:39
Ну тогда можно просто взять [0;0.5) отобразить на квадрат без двух сторон, а [0.5,1] на две стороны.

Или так.

Раз уж мы явно построили отображение [0,1)→[0,1)x[0,1), то можно сначала отрезок [0,1] вдвое растянуть, а потом задать отображение частичными отображениями.

Название: Дискретная математика
Отправлено: RawonaM от октября 6, 2011, 22:30

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

Цитата: RawonaM от октября 6, 2011, 20:02
Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

А с этими что? :-[

Название: Дискретная математика
Отправлено: Квас от октября 6, 2011, 22:42

Надо подумать. Я сегодня вечером не очень в форме. :)

Название: Дискретная математика
Отправлено: RawonaM от октября 6, 2011, 22:44

А, хорошо :) Это я решал экзамен, на который у меня нет ответов. Если мне такой попадется, пиши пропало. Все вопросы как на подбор очень сложные мне показались. Обычно как бы есть баланс, что одни легкие, другие тяжелые, а это прямо получился весь сложный.

Название: Дискретная математика
Отправлено: Bhudh от октября 6, 2011, 22:45

Цитата: Квас от Инъективность вообще очевидна.

/me жалеет, что нет сглатывающего смайлика...

Название: Дискретная математика
Отправлено: RawonaM от октября 7, 2011, 10:51

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

Это какой-то песец вообще. Как это можно было дать на экзамене?!!

Мне кажется я нашел прямую формулу, а вот рекуррентную не получается. Из прямой рекуррентную как вывести? Хотя конечно по заданию надо вывести рекуррентную и написано что не надо находить прямую, возмжно рекуррентную проще, но я туплю.

Прямая получается так: посчитаем отдельно для каждого количества пар (классов из двух элементов), сколько есть вариантов, затем их сложим. Итого выходит:

$[tex]\sum_{i=0}^{\lfloor \frac n2 \rfloor} \prod_{j=0}^i \binom{n-2j}2[/tex]$

Как думаете, верно ли?..

Название: Дискретная математика
Отправлено: arseniiv от октября 7, 2011, 12:24

Давайте попробуем!

K₀ = 1. ().
K₁ = 1. (1).
K₂ = 2. (1)(2) (12) можно оба связать с (1).
K₃ = 4. (1)(2)(3) (13)(2) (1)(23) можно связать с первым из предыдущих разбиений, (12)(3) со вторым.
K₄ = 10. (1)(2)(3)(4) (14)(2)(3) (1)(24)(3) (1)(2)(34) из первого, (13)(2)(4) (13)(24) из второго, (1)(23)(4) (14)(23) из третьего, (12)(3)(4) (12)(34) из четвёртого.

Не вижу способа учесть ограничение на два простым способом. Только если каждому разбиению сопоставлять количества одноэлементных и двуэлементных его элементов, пусть они будут s и d. (А d оказывается ненужным.)

Тогда из каждого из разбиений A_{k, n} n-элементного множества можно получить 1 + s_{k, n} разбиений (n + 1)-элементного. Притом числа s для каждого из порождённых разбиений такие: для первого s_{k, n} + 1, для остальных s_{k, n} − 1. Количество всех разбиений получим, суммируя A_{k, n} по k.

Хм. Может, пицца мне поможет.

UPD. Пицца только сказала, что запись (abc)(d)(ef) удобочитаемее, чем abc.d.ef.

Название: Дискретная математика
Отправлено: RawonaM от октября 7, 2011, 21:02

Цитата: arseniiv от октября 7, 2011, 12:24
UPD. Пицца только сказала, что запись (abc)(d)(ef) удобочитаемее, чем abc.d.ef.

+1, я как раз хотел об этом сказать.

Название: Дискретная математика
Отправлено: arseniiv от октября 7, 2011, 21:10

А первый вариант вы не видели, я его не показывал. В виде множеств, как обычно. Читалось похуже. Хотя лучше, чем точки.

Название: Дискретная математика
Отправлено: RawonaM от октября 8, 2011, 20:10

Функция Эйлера, что она возвращает? Вроде как по определению количество числа, которые меньше данного и не делят его (а также 1), я правильно понимаю?
Тогда получается, что если к значению функции Эйлера для некоего числа прибавить количество делителей оного (без 1), должно выйти как раз заданное число, не так ли?
Но у меня рассчеты совсем не сходятся.
Допустим для 120 Эйлер возвращает 32, у 120 вроде как 15 делителей, 32+15 никак не получаются 120.

Название: Дискретная математика
Отправлено: arseniiv от октября 8, 2011, 23:27

(wiki/ru) Функция_Эйлера (http://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0)

С вшим определением не сходится. Не все, которые не делят, взаимно просты с.

Название: Дискретная математика
Отправлено: Квас от октября 9, 2011, 12:23

Насчёт K_n: мне очевидной кажется формула
$[tex]K_n = \sum_{k=0}^n \binom nk \binom {n-k}2.[/tex]$
Может быть, воспользоваться рекуррентным соотношением для биномиальных коэффициентов и получить искомое рекуррентное соотношение путём преобразования формулы?

Название: Дискретная математика
Отправлено: Квас от октября 9, 2011, 12:30

Цитата: RawonaM от октября 6, 2011, 20:02
Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

Преложенные множества не подходят: например, пары (5, 10) и (6, 9) принадлежат первому множеству и несравнимы.

В качестве примера можно привести
$[tex]\{(a,1) \colon a\in\mathbb N \} \cup \{(1,b) \colon b\in\mathbb N \}[/tex]$
Насчёт универсального способа построения примеров сомневаюсь.

Название: Дискретная математика
Отправлено: RawonaM от октября 9, 2011, 12:33

Цитата: Квас от октября 9, 2011, 12:23
Насчёт K_n: мне очевидной кажется формула
$[tex]K_n = \sum_{k=0}^n \binom nk \binom {n-k}2.[/tex]$

Может пояснить?

Название: Дискретная математика
Отправлено: Квас от октября 9, 2011, 12:36

Выбираем k элементов, которые по одному, а остальные разбиваем на пары.

Название: Дискретная математика
Отправлено: RawonaM от октября 9, 2011, 12:41

Цитата: Квас от октября 9, 2011, 12:36
Выбираем k элементов, которые по одному, а остальные разбиваем на пары.

$[tex]\binom {n-k}2[/tex]$ — разве это разбитие на пары? :what:
Допустим осталось 5 разбить на пары, это вроде не С(5,2), а $[tex]\binom {5}{2,2}[/tex]$

Название: Дискретная математика
Отправлено: Квас от октября 9, 2011, 12:42

:fp:

Ладно, думаем дальше.

Название: Дискретная математика
Отправлено: RawonaM от октября 9, 2011, 12:46

Цитата: Квас от октября 9, 2011, 12:30
Цитата: RawonaM от октября 6, 2011, 20:02Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?
Преложенные множества не подходят: например, пары (5, 10) и (6, 9) принадлежат первому множеству и несравнимы.

В качестве примера можно привести
$[tex]\{(a,1) \colon a\in\mathbb N \} \cup \{(1,b) \colon b\in\mathbb N \}[/tex]$
Насчёт универсального способа построения примеров сомневаюсь.

А точно нет надмножеств, которые тоже упорядочены?

Название: Дискретная математика
Отправлено: Квас от октября 9, 2011, 12:49

Цитата: RawonaM от октября 9, 2011, 12:46
А точно нет надмножеств, которые тоже упорядочены?

Добавляем (c, d), тогда d > 1, и пара несравнима с (c+1,1).

Мне этот пример из каких-то геометрических соображений в голову пришёл. Можно ещё другие «кресты» рассматривать (то же самое, но фиксированные k и l вместо 1).

Название: Дискретная математика
Отправлено: RawonaM от октября 9, 2011, 12:51

Я вроде как потом придумал $[tex]\{(a,b) | a < b\}[/tex]$ .
Такой не пройдет?

Название: Дискретная математика
Отправлено: Квас от октября 9, 2011, 13:00

Цитата: RawonaM от октября 9, 2011, 12:51
Я вроде как потом придумал $[tex]\{(a,b) | a < b\}[/tex]$ .
Такой не пройдет?

Срабатывает тот же мой контрпример.

Нужно такое множество, что если точка (a,b) ему принадлежит, то остальные точки обязательно будут или выше и справа, или ниже и слева (равенство допускается). А у вас — точки, лежащие под прямой a=b; очевидно, они этому условию не удовлетворяют.

Название: Дискретная математика
Отправлено: RawonaM от октября 9, 2011, 13:01

Эх, что-то у меня сегодня совсем голова не варит :(

Название: Дискретная математика
Отправлено: RawonaM от октября 10, 2011, 20:58

Это был только что самый странный экзамен эвер для меня.

Пришел на экзамен, раздали бланки и тетради. Нужно выбрать четыре из пяти. За десять минут сделал первое задание, так же быстро третье, четвертое... Время пять с четвертью, т.е. менее половины экзамена, а я все уже сделал. Думаю, странно это, не может такого быть. Попил водички, сходил в одно место, сижу перепроверяю. Уже по пятому кругу читаю - все вроде правильно! Тут было раз уже сдавать собирался относить, смотрю - ошибка! Причем такая арифметическая ошибка, которая делает все дальнейшее решение в корне не верным. Ёмаё. Давай думать по новой над этим заданием по теории графов. Кручу-верчу, не решается. Еще час до конца, думаю надо решить тот вопрос, который я не выбрал. Взял его тоже за 5 минут решил. Опять 20 раз перекрутил в голове, перечитал, вроде все правильно. Еще минут 45 до конца. Думаю, ради спортивного интереса надо же решить задачу по теории графов. Но уже сложно было сосредоточиться, так и не решил. В последние полчаса из всего класса осталось 3 человека и все мы трое по этому курсу экзамен сдаем (в классе смешаные экзамены, со всех курсов). Они там что-то усердно уже в последние минуты пишут-пишут страницами, а я сижу и сижу, у меня весь экзамен с трудом на четыре листа, и писать вроде как нечего. В общем не стал их дожидаться, сдал за 10 минут до конца и ушел.

Сам не знаю, что это было, всегда было так, что я в последние минуты чего-то пишу быстро-быстро, и на проверку мне времени уже не хватает :)

Щас напишу задание по теории графов. Оно легкое, я уверен что никаких трюков там не требуется, просто по определениям все подставить и показать, но что-то не сходилось у меня.

Название: Дискретная математика
Отправлено: arseniiv от октября 10, 2011, 21:02

Давайте! Вдруг у меня получится. Я на экзамене забыл формулировку теоремы и доказал не ту. Которая вообще никому, видимо, не нужна и неизвестна. :D

Название: Дискретная математика
Отправлено: RawonaM от октября 10, 2011, 21:12

Цитата: arseniiv от октября 10, 2011, 21:02
Давайте! Вдруг у меня получится.

Написал в теорию графов. Там еще перед этим, в предпоследнем сообщении, еще задачка невостребованная, тоже можете попробовать :)

Название: Дискретная математика
Отправлено: Квас от октября 10, 2011, 21:34

RawonaM, принимайте поздравления. Вы молодчина! ;up:

Название: Дискретная математика
Отправлено: RawonaM от октября 10, 2011, 21:37

Спасибо :) На форуме курса уже все обсуждают во всю, ответы сравнивают - у меня все правильно :) Ну может плюс-минус объяснения какие напортачил. Обидно за вопрос по теории графов, прямо не могу себе этого простить. :fp:

Название: Дискретная математика
Отправлено: arseniiv от октября 10, 2011, 22:08

Главное, что вы его сейчас решили.

Название: Дискретная математика
Отправлено: RawonaM от октября 10, 2011, 22:11

Цитата: arseniiv от октября 10, 2011, 22:08
Главное, что вы его сейчас решили.

Да вот и нет, как грится "после драки кулаками не машут", так и тут, на экзамене не решил — в пролете.
Главное, что я смог решить другое задание на экзамене вместо этого, так что оценка не должна пострадать :)

Название: Дискретная математика
Отправлено: arseniiv от октября 10, 2011, 22:16

Я это подразумевал, т. к. вы это и сами знаете. ;D

Название: Дискретная математика
Отправлено: RawonaM от октября 24, 2011, 22:01

Получил 100 по экзамену и по курсу.

Название: Дискретная математика
Отправлено: arseniiv от октября 24, 2011, 23:10

Это замечательно!

[Квас сейчас временно недоступен, наверно, уже.]

Название: Дискретная математика
Отправлено: Квас от октября 26, 2011, 05:58

Цитата: RawonaM от октября 24, 2011, 22:01
Получил 100 по экзамену и по курсу.

Оле-оле-оле-оле! RawonaM — чемпион! :=

Название: Дискретная математика
Отправлено: RawonaM от октября 26, 2011, 08:10

Спасибо :-[ ;D

Лингвофорум

Общий раздел => Наука и техника => Математика => Тема начата: RawonaM от апреля 9, 2011, 22:01