Комбинаторика

[inspi]

Одна из задач курсовика...
В телефонной сети n абонентов. Каким числом способов можно осуществить k паралельных соединений?

Вообще запуталась как начала считать..
Просто число сочетаний из n по k здесь вряд ли покатит из-за этой параллельности. Здесь еще и непонятно четное ли n. Подскажите формулу, пожалуйста?

Сроки: до завтрашнего утра

Заранее большое спасибо)

@темы: Комбинаторика

Comments

[Trotil]

Привет!
Подсчитай в лоб:

[первое соединение] * [второе соединение] * ... * [k-тое соединение] / ([перестановки соединений] * [перестановки абонентов в соединении] )

[inspi]

Trotil Добрый вечер)
Нам эту лекцию не объясняли, а дали для самостоятельного изучения) Т.е. ни одну задачу подобного рода я еще не решала.
буду пробовать..
больше всего это похоже на размещение без повторений
но как учесть что все эти соединения по 2 абонента?..

[Trotil]

Наврал. Я сейчас проверил на частном случае n=5, k=2, по формуле = 15, по факту =10. На ночь глядя не соображу, где прокол. А через сочетания - так тоже вроде можно, только надо умножать на число различных групп, которые могут получиться...

Я спать.

[Trotil]

.е. ни одну задачу подобного рода я еще не решала.

Тогда настоятельно рекомендую начать с чего-то попроще. А здесь много подводных камней, корабль до берега не доплывет, потонет где-нибудь...

[inspi]

Защита курсовика завтра. Ладно, жаль конечно)

[asdf86181398]

Я может быть немного не понел вашей задачи...
Но если сказано, что k параллельных соединений -- то это значит, что надо соединить проводами 2*k различных абонентов из n.
Т.е. число способов C(n,2k).
Потом, внутри выбранных 2k нужно отобрать k источников запросов, которые однозначно соответствуют k приемникам. Это еще A(2k,k) комбинаций.
В итоге, C(n,2k)A(2k,k)

[inspi]

так...

Потом, внутри выбранных 2k нужно отобрать k источников запросов, которые однозначно соответствуют k приемникам. Это еще A(2k,k) комбинаций.

это можно поподробнее? О_о

C(n,2k).

это у нас просто число разговаривающих абонентов.
а дальше что происходит?)

[Trotil]

Можно посчитать так.

Первая пара: первый может образовать пару сколькими способами? Записываем, выкидываем обоих.
Вторая пара: первый (из оставшихся) может образовать пару сколькими способами? Записываем, выкидываем обоих. И т.д.

Подсказка - записать компактно можно через двойной факториал.

И в n=4 k=2 ответ таки 15 и первая формула правильная тоже.

Короче, у тебя уже два способа выборки. Лучше поразмыслить над тем, и над тем

[inspi]

Trotil
asdf86181398 Спасибо вам)

[Trotil]

Потом, внутри выбранных 2k нужно отобрать k источников запросов, которые однозначно соответствуют k приемникам. Это еще A(2k,k) комбинаций.

А это неверно. Сужает возможность выбора ответного абонента

[Alidoro]

А у меня такая логика: Первую пару можно выбрать C(n,2) способами, вторую C(n-2,2) способами и т. д. Последнюю C(n-2k+2,2) способами.
Если все перемножить, то в числителе будет n(n-1)...(n-2k+1), а в знаменателе 2 в степени k. Чтоб не писать точек можно привести всё к факториалам: n!/(2^k (n-2k)!)

[inspi]

БР
три человека-три мнения(
что за задача...

[Гость]

inspi, Alidoro забыл как минимум еще разделить на число перестановок соединений.

[Alidoro]

Мы обсудили, а вам решать... Оценку же не нам будут ставить, а вам. Ну и попробуйте ее заслужить.

[Гость]

Это был я (Trotil)

[Alidoro]

Гость Да, забыл. Значит ответ еще надо разделить на факториал чего-то там...
В общем-то задача просто требует повторить рассуждения, применяемые при выводе формулы для сочетаний, но немного в других условиях.
Хотя с другой стороны эту формулу тоже можно выводить множеством разных способов...