Дискретная математика (комбинаторика)

[nync]

а) Найти число B(2k) разбиений на пары 2k-элементного множества, k>0
b) Найти число симметричных матриц перестановки порядка n. //Частные значения n=1,...,9 //

====================
подскажите с какой стороны подойти к решению ....

AKM:

В учебный раздел (из Общей математики). И не надо дублировать темы.

[Профессор Снэйп]

a) Если все числа от $1$ до $2k$ выстроить в ряд и разбить на пары "подряд", то получится разбиение

$$ a_1, a_2 \,|\, a_3, a_4 \,|\, a_5, \ldots, a_{2k-2} \,|\, a_{2k-1}, a_{2k} $$

Получается, что перестановка чисел от $1$ до $2k$ задаёт разбиение на пары. Любое разбиение можно задать таким образом. Осталось лишь выяснить, сколько перестановок задают одни и те же разбиения. Это просто: пары можно переставлять, и можно также переставлять числа внутри каждой пары.

б) А что такое "матрица перестановки"?

[nync]

Матрица перестановки - квадратная бинарная матрица, в каждой строке и столбце которой находится лишь один единичный элемент.

[Профессор Снэйп]

nync в сообщении #305853 писал(а):

Матрица перестановки - квадратная бинарная матрица, в каждой строке и столбце которой находится лишь один единичный элемент.

А... то есть умножение на эту матрицу даёт перестановку компонет вектора.

Ну тогда их столько же, сколько перестановок, то есть $n!$ Разве не так?

-- Сб апр 03, 2010 13:43:19 --

Ой, там не все матрицы перестановки, а симметричные надо считать. Сорри

-- Сб апр 03, 2010 13:46:28 --

Надо подумать. Если матрица симметричная, то какую перестановку она задаёт? Пусть $A = (a_{ij})$ --- такая матрица и $a_{ij}=1$. Тогда $a_{ji} = 1$ и $x_i \to x_j$, $x_j \to x_i$. То есть симметричным матрицам перестановки соответствуют такие перестановки $\sigma$, что $\sigma^2 = 1$. Осталось лишь посчитать количество таких перестановок. Это просто и напрямую связано с предыдущей задачей

-- Сб апр 03, 2010 13:48:45 --

В первой задаче у Вас какой ответ получился?

-- Сб апр 03, 2010 14:09:13 --

Не то, но близко

-- Сб апр 03, 2010 14:19:20 --

Вторая задача! Короткой формулы вроде нет, только через сумму.

[Профессор Снэйп]

Уважаемый ТС!

Не надо слать мне ЛС с вопросами по поводу ответа к первой задаче! Есть же тема, давайте в ней всё и обсуждать.

То, что Вы мне прислали, очевидно, неверно. Правильный ответ проще. Смотрите: всего существует $(2k)!$ перестановок у множества из $2k$ элементов. Далее, среди всех этих перестановок перестановки, переставляющие пары целиком, приводят к одному и тому же разбиению. Так как пар $k$ штук, то полученное значение надо поделить на $k!$. Далее, внутри каждой пары элементы тоже можно переставить и на результат это не повлияет, значит, полученное значение необходимо поделить ещё на...

-- Ср апр 07, 2010 11:27:44 --

Числа Стирлинга тут совершенно не при чём!

[nync]

спасибо, насколько я понял ответ таков..
$\frac{{2k}!}{k!(2!)^k}$

со второй понимание пока что отсутствует...

[Бодигрим]

В первой задаче - да, правильно, можно даже выпендриться и сократить ответ до $(2k-1)!!$

[Профессор Снэйп]

А можно ещё сильнее выпендриться и заменить $2!$ на $2$

[Профессор Снэйп]

nync в сообщении #307404 писал(а):

со второй понимание пока что отсутствует...

А во второй, насколько я понял, простой формулы не существует. Только через сумму.

С суммой же просто. Существует взаимно однозначное соответствие между матрицами перестановки $n \times n$ и перестановками $n$-элементного множества. При этом симметричным матрицам перестановки соответствуют такие перестановки $\sigma$, что $\sigma^2 = 1$. А как устроены перестановки, квадрат которых равен $1$? Это какое-то количество циклов длины $2$ плюс тождественная перестановка на элементах, не входящих в эти циклы. Циклы же задаются разбиениями на пары, а количество таких разбиений Вы уже умеете считать из предыдущей задачи.

Значит, чтобы задать перестановку $\sigma$ со свойством $\sigma^2 = 1$, нужно выделить какое-то подмножество множества $\{ 1, \ldots, n \}$, состоящее из чётного числа элементов, и посчитать количество его разбиений на пары. А потом всё это дело просуммировать по всем выделяемым подмножествам.

При чётном $n = 2k$ получаем ответ

$$ \sum_{i=0}^k \binom{2k}{2i} \frac{(2i)!}{i! \cdot 2^i} = \sum_{i=0}^k \frac{(2k)!}{(2k-2i)! \cdot i! \cdot2^i} $$

Для нечётного $n=2k+1$ найдите ответ самостоятельно.

[TOTAL]

nync в сообщении #305792 писал(а):

а) Найти число B(2k) разбиений на пары 2k-элементного множества, k>0

Можно по индукции
$B_{2k}=B_{2k-2}\left(1+2(k-1) \right)$
(два определённых элемента попадут либо в одну пару, либо в разные)