Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | |
---|---|---|
Cocoa Lapin |
|
|
Готовлюсь к экзамену по дискретной математике. Объясните, как решить несколько задач, пожалуйста : 1. С помощью комбинаторных размышлений доказать, что количество разбиений числа n на попарно различные слагаемые = количеству разбиений числа n на нечётные слагаемые. 2. Доказать, что для счётного универсума множество всех подмножеств с конечным дополнением является счётным. 3. Доказать, что декартовое произведение непустой конечной совокупности континуальных множеств является континуальным множеством. 4. Доказать, что множество всех бесконечных подмножеств конечного множества является континуальным. |
||
Вернуться к началу | ||
3D Homer |
|
|
1. Доказательство взято из Lectures on Integer Partitions by Herbert S. Wilf (документ PDF).
Построим биекцию, которая разбиения на попарно различные слагаемые отображает в разбиения на нечетные слагаемые. Пусть [math]n=d_1+\dots+d_k[/math], где все [math]d_i[/math] различны. Каждое [math]d_i[/math] представляется в виде [math]2^{k_i}m_i[/math], где [math]m_i[/math] нечетное число. Сгруппируем слагаемые с одинаковыми [math]m_i[/math]: [math]\begin{align*} n&= (2^{\alpha_1}+2^{\alpha_2}+\dots)\cdot1+ (2^{\beta_1}+2^{\beta_2}+\dots)\cdot 3+ (2^{\gamma_1}+2^{\gamma_2}+\dots)\cdot5+\dots\\ &=\mu_1\cdot1+\mu_3\cdot2 +\mu_5\cdot5+\dots\end{align*}[/math] Таким образом, [math]n[/math] есть сумма [math]\mu_1[/math] единиц, [math]\mu_3[/math] троек и т.д. Осталось показать, что это отображение инъективно и сюръективно. Сюръективность: пусть дано разбиение [math]n[/math] на нечетные слагаемые [math]n=\mu_1\cdot1+\mu_3\cdot2 +\mu_5\cdot5+\dots[/math]. Напишем каждое [math]\mu_i[/math] (здесь [math]i[/math] нечетно) в двоичной системе: [math]\mu_i=2^{\rho_1}+2^{\rho_2}+\dots[/math], где все [math]\rho_j[/math] различны. Из них получатся слагаемые [math]2^{\rho_1}i+2^{\rho_2}i+\dots[/math] Они отличаются как между собой, так и от слагаемых, соответствующих другим [math]\mu_{i'}[/math]. То есть прообраз действительно есть разбиение на различные слагаемые. Инъективность оставлю в качестве задачи. Есть более простое доказательство с помощью производящих функций. |
||
Вернуться к началу | ||
За это сообщение пользователю 3D Homer "Спасибо" сказали: Cocoa Lapin |
||
Cocoa Lapin |
|
|
Еще несколько задач, с которыми я не могу разобраться...
5. На карусели по кругу размещено n разных детей. Сколькими способами можно переставить детей так, чтоб перед каждым был размещен другой ребёнок, чем прежде ? 6. Сколькими способами на трехугольной шахматной доске со стороной q можно расставить k тур, чтоб ни одна тура не била другую? ( с аналитическим ответом ) 7. Какую мощность имеет множество всех замкнутых подмножеств множества действительных чисел R ? |
||
Вернуться к началу | ||
3D Homer |
|
|
Подсказка для № 7 есть в этой теме. Насчет остальных, я думаю, лучше начать новую тему. У вас больше шансов получить ответ, потому что люди с большей вероятностью просматривают темы без ответов, чем темы, уже содержащие несколько сообщений.
|
||
Вернуться к началу | ||
За это сообщение пользователю 3D Homer "Спасибо" сказали: Cocoa Lapin |
||
[ Сообщений: 4 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задачи по дискретной математике | 7 |
782 |
07 июн 2014, 12:51 |
|
Задачи по дискретной математике | 1 |
211 |
26 дек 2019, 19:08 |
|
Решить задачи по дискретной математике | 1 |
125 |
29 июн 2022, 00:11 |
|
Задания по дискретной математике | 1 |
383 |
24 авг 2017, 20:48 |
|
Задание по дискретной математике | 1 |
383 |
27 янв 2015, 21:46 |
|
Учебники по дискретной математике | 6 |
827 |
11 ноя 2015, 19:29 |
|
Экзамен по дискретной математике | 1 |
119 |
18 июн 2022, 22:30 |
|
Задача по дискретной математике | 1 |
111 |
24 дек 2023, 17:15 |
|
Где скачать книжку по дискретной математике? | 2 |
233 |
20 май 2016, 20:49 |
|
Задача по дискретной математике (1 курс | 7 |
618 |
02 ноя 2020, 21:12 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 27 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |