2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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


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

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение03.04.2010, 08:48 
Аватара пользователя
a) Если все числа от $1$ до $2k$ выстроить в ряд и разбить на пары "подряд", то получится разбиение
$$
a_1, a_2 \,|\, a_3, a_4 \,|\, a_5, \ldots, a_{2k-2} \,|\, a_{2k-1}, a_{2k}
$$
Получается, что перестановка чисел от $1$ до $2k$ задаёт разбиение на пары. Любое разбиение можно задать таким образом. Осталось лишь выяснить, сколько перестановок задают одни и те же разбиения. Это просто: пары можно переставлять, и можно также переставлять числа внутри каждой пары.

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

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение03.04.2010, 10:05 
Матрица перестановки - квадратная бинарная матрица, в каждой строке и столбце которой находится лишь один единичный элемент.

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение03.04.2010, 10:42 
Аватара пользователя
nync в сообщении #305853 писал(а):
Матрица перестановки - квадратная бинарная матрица, в каждой строке и столбце которой находится лишь один единичный элемент.

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

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

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

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

-- Сб апр 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 --

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

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение07.04.2010, 08:26 
Аватара пользователя
Уважаемый ТС!

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

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

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

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

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение07.04.2010, 19:15 
спасибо, насколько я понял ответ таков..
$\frac{{2k}!}{k!(2!)^k}$

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

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение08.04.2010, 01:20 
Аватара пользователя
В первой задаче - да, правильно, можно даже выпендриться и сократить ответ до $(2k-1)!!$

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение08.04.2010, 05:32 
Аватара пользователя
А можно ещё сильнее выпендриться и заменить $2!$ на $2$ :-)

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение08.04.2010, 12:14 
Аватара пользователя
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$ найдите ответ самостоятельно.

 
 
 
 Re: Дискретная математика (комбинаторика)
Сообщение08.04.2010, 13:21 
Аватара пользователя
nync в сообщении #305792 писал(а):
а) Найти число B(2k) разбиений на пары 2k-элементного множества, k>0

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group