Задачи по комбинаторике

kalu4ka

Народ выручите срочно, задачки простые, просто в математике не шарю.
Задачи:
1. Есть последовательность (n элементов) из 0 и 1.
а) Найти кол-во тех последовательностей (n элементов в которых встречаются
подряд 2 нуля;
б) Найти кол-во тех последовательностей (n элементов в которых встречаются
подряд 3 нуля;
2. Есть n юношей и m девушек (n<=m). Каждый юноша знает какую-то девушку и каждая девушка знает какого-то юношу (если Петя знает Машу, то и Маша знает Петю). При каких условиях можно переженить всех юношей?

ARTi

насчет второй задачи есть теорема Холла "о свадьбах":
переженить всех мужиков можно тогда и только тогда, когда для любого набора мужиков множество знакомых им баб имеет не меньшую мощность

ARTi

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

kalu4ka

Покатит, обЪясни как?

ARTi

ну тогда помоги человеку, а то мне что-то влом

ARTi

) ищем число последовательностей, в которых НЕ встречается 2 нуля подряд (тогда ответом будет 2^n - найденное число):
это множество можно записать так: (1)^итер (01 (1)^итер)^итер, где "итер" - итерация
тогда производящая функция этого множества равна:
1/(1-x) * 1/(1-x*x*(1/(1-x = 1/(1-x-x*x)
дальше раскладываешь эту дробь в ряд и коэффициент при x^n будет искомым числом

kalu4ka

Первая вроде не сложная, а ко второй совсем не понимаю с какой стороны подойти

ARTi

вторая абсолютно аналогична, если ты понял, как решается первая

ARTi

(1)^итер 0или00)1 (1)^итер)^итер

NHGKU2

а) Будем искать число a_n последовательностей, в которых нет 2х нулей подряд; тогда искомое число будет равно 2^n - a_n.
Выпишем для a_n производящую функцию.
\sum a_n x^n = F_a (x) = (1+x+x^2+x^3+...) * П_{n=0}^\infty (x^2+x^3+...)^n * (1+x)
(первая скобка означает, что в начале последовательности может встретиться 1 сколько угодно раз (а может и не встретиться); второе произведение означает, что далее в последовательности если и есть 0, то за ним обязательно идёт 1; третье - возможно, в конце последовательности есть один 0).
Упрощаем F_a (x получаем F_a (x) = 1/(1-x) * 1/(1-x^2/(1-x * (1+x) = (1+x)/(1-x-x^2).
Отсюда 1+x = (1-x-x^2) \sum a_n x^n. Приравнивая коэффициенты при соотвествующих степенях, получаем
1 = 1*a_0, т.е. а_0 = 1;
1 = a_1 - a_0; т.е. a_1 = 2;
0 = a_k - a_{k-1} - a{k-2} (k>1).
Видим, что это последовательность Фибоначчи, "сдвинутая" на два члена вперёд.
Таким образом, a_n = Ф_{n+2}.
Ответ, стало быть, 2^n - Ф_{n+2}.
P.S. Явную формулу для чисел Фибоначчи посмотри в книжках (я её точно не помню, а выводить неохота).

kalu4ka

Я имею в виду вторая задача

NHGKU2

Вторая задача - это просто вариант .

kiritsev

a 2^n-Fib(n+2)
пока вспоминал сколько ч в слове фибоначчи меня опередили

kalu4ka

А где можно почитать док-во теоремы Холла, из какой это области?

ARTi

это из дискретной математики

kalu4ka

Спасибо я почитаю, правильно я понимаю, у любых К из N мужиков, не меньше К знакомых из М девушек?

ARTi

доказывается теорема Холла индукцией по числу мужиков
попробуй сам, там не сложно
при индукционном переходе надо рассмотреть два случая:
мощность множества баб, знакомых с данным множеством мужиков, строго больше мощности последнего при любом множестве мужиков;
существует множество мужиков, равное по мощности множеству баб, с ними знакомых

ARTi

да, для любого К

kalu4ka

П_{n=0}^\infty (x^2+x^3+...)^n
Что это означает не могу разобрать? Напиши в ворде пожалуйста.
И какой ответ для 3 нулей?

NHGKU2

kalu4ka

какой ответ для 3 нулей?

kalu4ka

А почему П, а не sum

NHGKU2

(1)^итер 0или00)1 (1)^итер)^итер
Неправильно.
(1)^итер 0или00)1 (1)^итер)^итер (00или0или[пусто])
Производящая функция тогда такая будет:
\sum a_n x^n = F_a (x) = (1+x+x^2+x^3+...) * П_{n=0}^\infty [(x^2+x^31+x+x^2+...)]^n * (1+x+x^2) = (1+x+x^2)/(1-x-x^2-x^3).
Здесь, поступая аналогично, получим рекуррентное соотношение
a_k = a_{k-1} + a_{k-2} + a_{k-3}, k>2;
a_0 = 1, a_1 = 2, a_2 = 4.
Решая его, получаем (2^n - ответ к задаче 1б).

NHGKU2

Ну просто свойство такое у производящих функций есть..
Если хочешь понять решение, то почитай про производящие функции в каких-нибудь книжках.

NHGKU2

А вот как решать это рекуррентное соотношение, непонятно...
Я даже на множители многочлен 1-x-x^2-x^3 разложить не могу

kalu4ka

А кто-нибудь какой-нибудь другой способ решения знает, просто срочно надо.

kalu4ka

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

goga7152

Сообщение удалил

kalu4ka

А какой ответ для 3-х нулей?
Для 2-х 2^n-Fib(n+2).
А для 3-х?

goga7152

Сообщение удалил

ARTi

в том то и дело, что по аналогии не получается
у меня такое ощущение, что там ответа в общем виде для n не выпишешь

goga7152

Сообщение удалил

ARTi

это до тебя еще Робин и я нашли
в том то и фигня, что многочлен в знаменателе ты хрен разложишь

goga7152

Сообщение удалил

goga7152

Сообщение удалил

ARTi


это как раз то решение, которое хотел получить

NHGKU2

Я этого не утверждал. У меня получилось 2^n-Fib(n+1) (a_0=a_1=0, a_2=1, a_3=3, ...).
То, что в скобках - это "сдвинутая" на 1 (только теперь влево) последовательность Фибоначчи
(0 + 0 ≠ 1.)
Так что не путай нас, ответ 2^n - Ф_{n+2} правильный
P.S. Если я правильно считаю, что последовательность Фибоначчи - это 0, 1, 1, 2, 3, 5, 8, ...

NHGKU2

Это не совсем то, что надо (знак один различается в рекуррентном соотношении но можно сделать по аналогии...
Кто-нибудь умеет решать кубические уравнения по формуле Кардано?

goga7152

Сообщение удалил

NHGKU2

Да, да, понял. Ты прав.
Оставить комментарий
Имя или ник:
Комментарий: