Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 7 ] |
|
Автор | Сообщение | |
---|---|---|
AGN |
|
|
Не уверен, что раздел выбран правильно (комбинаторика? дискретная математика?). Просьба модераторам в случае необходимости переместить тему в оответствующий раздел. Задача выглядит так: имеется прямоугольная доска [math]m \times n[/math]. Где-то в середине удалены вертикальные и горизонтальные линии так, что образовалось пустое пространство. Движение осуществляется (скажем, из левого нижнего угла А в правый верхний В) по периметру клеток (вправо либо вверх). Через пустое пространство переходить нельзя. Сколько существует путей из А в В? К задаче прилагалась подсказка: воспользоваться формулой включений-исключений. Что-то я не вижу, каким образом это может быть использовано. Буду признателен за подсказку/намек по поводу решения. Спасибо. |
||
Вернуться к началу | ||
searcher |
|
|
Вы руками собираетесь считать или программу будете писать? Расставить надо несколько ключевых точек. И считать последовательно варианты для этих точек, начиная от конца к началу.
|
||
Вернуться к началу | ||
За это сообщение пользователю searcher "Спасибо" сказали: AGN |
||
AGN |
|
|
Спасибо.
Да, считать придется вручную. А все же - при чем здесь включения-исключения? Может, из количества всех возможных путей следует вычесть количество запрещенных (проходящих через пустую область)? |
||
Вернуться к началу | ||
AGN |
|
|
Все, разобрался. Благодарю.
|
||
Вернуться к началу | ||
searcher |
|
|
AGN писал(а): Все, разобрался Интересно, и как решали? Я решал так. По путям следования расставил несколько ключевых точек. Они должны выбираться так, чтобы на любом допустимом пути встретилась одна и только одна ключевая точка. Также прямоугольник, построенной на начальной и ключевой точке, а также на ключевой и конечной, целиком принадлежит исходному прямоугольнику без внутреннего выреза. Я расставлял ключевые точки так: от правого нижнего угла внутреннего прямоугольника вниз - направо. И от левого верхнего угла вверх - налево. В итоге задача сводится к суммированию произведений биномиальных коэффициентов. |
||
Вернуться к началу | ||
AGN |
|
|
Если интересно - решал так. Возьмем, к примеру, прямоугольник определенного размера - скажем, 7*8 (я понимаю, сюда нельзя вставлять рисунки?) и обзовем его вертикали и горизонтали подобно шахматной доске. Скажем, клетки d4, d5, d6, e6 - пустые (путь запрещен). Определяем три множества запрещенных путей. Первый - из правого верхнего угла клетки с4 в правый верхний d4 (напоминаю, двигаемся только вправо или вверх). Второй - из с5 в d5. Третий - из d4 в d7.
Число всех путей из a1 в g8 равно [math]C_{7+8}^{8}[/math] или, если угодно, [math]\widetilde{P}\left( 7,8 \right)[/math]. Число запрещенных в первом множестве: [math]C_{3}^{3+4}*1*C_{3}^{3+4}[/math] Во втором: [math]C_{3}^{3+5}*1*C_{3}^{3+3}[/math] В третьем: [math]C_{3}^{3+4}*1*1*1*C_{3}^{3+2}[/math] Осталось сложить все запрещенные и вычесть из общего количества возможных. |
||
Вернуться к началу | ||
sergebsl |
|
|
В прикладной (перечислительной) комбинаторике рассматриваются производящие функции для такого рода задач.
Возможно непосредственное отношение к вашему вопросу имеют ладейные числа, которые выводят через производящие функции. |
||
Вернуться к началу | ||
[ Сообщений: 7 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Число путей ладьи из угла в угол на шахматной доске | 14 |
1480 |
29 апр 2018, 21:50 |
|
Поиск путей | 8 |
659 |
26 апр 2015, 17:33 |
|
Поиск путей | 1 |
140 |
07 фев 2024, 00:43 |
|
Определить количество путей | 3 |
139 |
13 дек 2020, 23:57 |
|
Транспортная задача на сети | 6 |
242 |
04 июн 2020, 13:12 |
|
Программирование нейронной сети
в форуме Информатика и Компьютерные науки |
1 |
525 |
31 авг 2014, 10:18 |
|
Сети Петри + информационная безопасность | 0 |
249 |
27 сен 2016, 01:15 |
|
Найти оптимальную конфигурацию сети | 5 |
340 |
19 май 2022, 12:29 |
|
Определение розничной торговой сети
в форуме Размышления по поводу и без |
2 |
54 |
06 фев 2024, 00:54 |
|
Схема для расчёта прокладки сети
в форуме Объявления участников Форума |
1 |
357 |
25 сен 2015, 10:07 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |