Автор |
Сообщение |
atakga
|
Заголовок сообщения: Разбиение множества Добавлено: 24 мар 2015, 08:50 |
|
Зарегистрирован: 20 дек 2013, 17:51 Сообщений: 118 Откуда: Занзибар
|
Подскажите пожалуйста идею решения этой задачи: Найти количество способов разбиения множества `{1,2,.......,2006}` на три не пустых подмножества, в каждом из которых нет двух последовательных чисел. Спасибо заранее!
|
|
|
|
|
|
|
vyv2
|
Заголовок сообщения: Re: Разбиение множества Добавлено: 24 мар 2015, 20:49 |
|
Зарегистрирован: 31 янв 2011, 17:37 Сообщений: 4974 Откуда: Санкт-Петербург
|
atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Найти количество способов разбиения множества `{1,2,.......,2006}` на три не пустых подмножества, в каждом из которых нет двух последовательных чисел. Спасибо заранее! Обозначим число способов разбиения множества `{1,2,.......,n}` при `n>=3`, отвечающих условию задачи, `S_n`. Каждое разбиение из n элементов при добавлении n+1 -го элемента увеличивается в два раза, т.к. только одно из трех подмножеств содержит число n , а два других подмножества допускают добавление n+1 -го элемента, не нарушая условия образования подмножеств. Значит `S_(n+1)=2S_n`. При n=3 `S_3=1`. По индукции `S_n=2^(n-3)` и `S_2006=2^2003`. Как-то так, если не ошибся.
_________________ Сопротивление бесполезно.
|
|
|
|
|
Иваныч
|
Заголовок сообщения: Re: Разбиение множества Добавлено: 24 мар 2015, 21:27 |
|
Зарегистрирован: 10 сен 2011, 23:41 Сообщений: 968 Откуда: Казань
|
vyv2 писал(а): Обозначим число способов разбиения множества `{1,2,.......,n}` при `n>=3`, отвечающих условию задачи, `S_n`. Каждое разбиение из n элементов при добавлении n+1 -го элемента увеличивается в два раза, т.к. только одно из трех подмножеств содержит число n , а два других подмножества допускают добавление n+1 -го элемента, не нарушая условия образования подмножеств. Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`. Кто больше?
|
|
|
|
|
vyv2
|
Заголовок сообщения: Re: Разбиение множества Добавлено: 24 мар 2015, 21:51 |
|
Зарегистрирован: 31 янв 2011, 17:37 Сообщений: 4974 Откуда: Санкт-Петербург
|
Иваныч писал(а): Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`. Кто больше? Согласен.
_________________ Сопротивление бесполезно.
|
|
|
|
|
atakga
|
Заголовок сообщения: Разбиение множества Добавлено: 24 мар 2015, 22:47 |
|
Зарегистрирован: 20 дек 2013, 17:51 Сообщений: 118 Откуда: Занзибар
|
Иваныч писал(а): Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`. Кто больше? Спасибо vy2 и Иваныч! Иваныч можно ли подробно написать Ваше решение. Как-то я не понял Вашу идею решения.
|
|
|
|
|
vyv2
|
Заголовок сообщения: Re: Разбиение множества Добавлено: 24 мар 2015, 23:52 |
|
Зарегистрирован: 31 янв 2011, 17:37 Сообщений: 4974 Откуда: Санкт-Петербург
|
atakga писал(а): Иваныч писал(а): Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`. Кто больше? Спасибо vy2 и Иваныч! Иваныч можно ли подробно написать Ваше решение. Как-то я не понял Вашу идею решения. Иваныч помимо моего способа увеличения числа способов разбиений из n элементов на три подмножества за счет добавления п+1-го числа, которое увеличивает число способов разбиений в два раза, добавил еще одно разбиение, состоящее в одном подмножестве из одного элемента {n+1} и двух других подмножеств {1,3,...,n}, если n - нечетное, и {2,4,...,n), если n -четное.
_________________ Сопротивление бесполезно.
|
|
|
|
|
atakga
|
Заголовок сообщения: Re: Разбиение множества Добавлено: 25 мар 2015, 11:59 |
|
Зарегистрирован: 20 дек 2013, 17:51 Сообщений: 118 Откуда: Занзибар
|
Очень благодарен Вам vyv2!
|
|
|
|
|
|
|
|