Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Число путей в сети
СообщениеДобавлено: 14 ноя 2018, 18:58 
Не в сети
Оракул
Зарегистрирован:
10 окт 2018, 22:06
Сообщений: 830
Cпасибо сказано: 209
Спасибо получено:
245 раз в 225 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
Добрый день.
Не уверен, что раздел выбран правильно (комбинаторика? дискретная математика?). Просьба модераторам в случае необходимости переместить тему в оответствующий раздел.
Задача выглядит так: имеется прямоугольная доска [math]m \times n[/math]. Где-то в середине удалены вертикальные и горизонтальные линии так, что образовалось пустое пространство. Движение осуществляется (скажем, из левого нижнего угла А в правый верхний В) по периметру клеток (вправо либо вверх). Через пустое пространство переходить нельзя. Сколько существует путей из А в В?
К задаче прилагалась подсказка: воспользоваться формулой включений-исключений. Что-то я не вижу, каким образом это может быть использовано.
Буду признателен за подсказку/намек по поводу решения.
Спасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Число путей в сети
СообщениеДобавлено: 14 ноя 2018, 23:24 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
15 мар 2016, 15:08
Сообщений: 9390
Cпасибо сказано: 122
Спасибо получено:
1726 раз в 1634 сообщениях
Очков репутации: 235

Добавить очки репутацииУменьшить очки репутации
Вы руками собираетесь считать или программу будете писать? Расставить надо несколько ключевых точек. И считать последовательно варианты для этих точек, начиная от конца к началу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю searcher "Спасибо" сказали:
AGN
 Заголовок сообщения: Re: Число путей в сети
СообщениеДобавлено: 15 ноя 2018, 11:39 
Не в сети
Оракул
Зарегистрирован:
10 окт 2018, 22:06
Сообщений: 830
Cпасибо сказано: 209
Спасибо получено:
245 раз в 225 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
Спасибо.
Да, считать придется вручную. А все же - при чем здесь включения-исключения? Может, из количества всех возможных путей следует вычесть количество запрещенных (проходящих через пустую область)?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Число путей в сети
СообщениеДобавлено: 15 ноя 2018, 14:02 
Не в сети
Оракул
Зарегистрирован:
10 окт 2018, 22:06
Сообщений: 830
Cпасибо сказано: 209
Спасибо получено:
245 раз в 225 сообщениях
Очков репутации: 38

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Число путей в сети
СообщениеДобавлено: 16 ноя 2018, 15:13 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
15 мар 2016, 15:08
Сообщений: 9390
Cпасибо сказано: 122
Спасибо получено:
1726 раз в 1634 сообщениях
Очков репутации: 235

Добавить очки репутацииУменьшить очки репутации
AGN писал(а):
Все, разобрался

Интересно, и как решали? Я решал так. По путям следования расставил несколько ключевых точек. Они должны выбираться так, чтобы на любом допустимом пути встретилась одна и только одна ключевая точка. Также прямоугольник, построенной на начальной и ключевой точке, а также на ключевой и конечной, целиком принадлежит исходному прямоугольнику без внутреннего выреза. Я расставлял ключевые точки так: от правого нижнего угла внутреннего прямоугольника вниз - направо. И от левого верхнего угла вверх - налево. В итоге задача сводится к суммированию произведений биномиальных коэффициентов.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Число путей в сети
СообщениеДобавлено: 17 ноя 2018, 01:44 
Не в сети
Оракул
Зарегистрирован:
10 окт 2018, 22:06
Сообщений: 830
Cпасибо сказано: 209
Спасибо получено:
245 раз в 225 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
Если интересно - решал так. Возьмем, к примеру, прямоугольник определенного размера - скажем, 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]
Осталось сложить все запрещенные и вычесть из общего количества возможных.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Число путей в сети
СообщениеДобавлено: 17 ноя 2018, 02:27 
Не в сети
Light & Truth
Зарегистрирован:
10 дек 2013, 02:33
Сообщений: 3268
Cпасибо сказано: 263
Спасибо получено:
417 раз в 407 сообщениях
Очков репутации: 51

Добавить очки репутацииУменьшить очки репутации
В прикладной (перечислительной) комбинаторике рассматриваются производящие функции для такого рода задач.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 7 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Число путей ладьи из угла в угол на шахматной доске

в форуме Дискретная математика, Теория множеств и Логика

K1b0rg

14

1480

29 апр 2018, 21:50

Поиск путей

в форуме Аналитическая геометрия и Векторная алгебра

samorez

8

659

26 апр 2015, 17:33

Поиск путей

в форуме Дискретная математика, Теория множеств и Логика

Ivan Kalita

1

140

07 фев 2024, 00:43

Определить количество путей

в форуме Дискретная математика, Теория множеств и Логика

lolliker228

3

139

13 дек 2020, 23:57

Транспортная задача на сети

в форуме Дискретная математика, Теория множеств и Логика

n_ilyasov1

6

242

04 июн 2020, 13:12

Программирование нейронной сети

в форуме Информатика и Компьютерные науки

samsuser

1

525

31 авг 2014, 10:18

Сети Петри + информационная безопасность

в форуме Дискретная математика, Теория множеств и Логика

80LevelElf

0

249

27 сен 2016, 01:15

Найти оптимальную конфигурацию сети

в форуме Задачи со школьных и студенческих олимпиад

Jimmse

5

340

19 май 2022, 12:29

Определение розничной торговой сети

в форуме Размышления по поводу и без

Xenia1996

2

54

06 фев 2024, 00:54

Схема для расчёта прокладки сети

в форуме Объявления участников Форума

kucher

1

357

25 сен 2015, 10:07


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved