[комбинаторика] Простая задача

Первую пару можно выбрать C(2,n) способами, вторую - C(2,n-2), третью - C(2,n-4) и так до n/2. Потом взять и перемножить, не?

n!

Пары/список упорядочены?

Это если и пары и список упорядочены.

>n!

Ибо можно любую последовательность неповторяющихся элементов тупо разбить на пары. А таких последовательностей n!.

Нет

Т.е. ((1 2) (3 4)) == ((2 1) (3 4)) == ((3 4) (2 1)) ?

Тогда n!/((n/2)!*2!^(n/2))

> Т.е. ((1 2) (3 4)) == ((2 1) (3 4)) == ((3 4) (2 1)) ?

Да

>Это если и пары и список упорядочены.

Ну а если не упорядочены, то взять число разных пар n(n-1) и поличество сочетаний по n/2. Будет C(n(n-1), n/2)

О, спасибо! Тока, наверно, n-1, а не n(n-1).

Например, для элементов (1 2 ... n) Будет (k 1) (k 2) ... (k k-1) (k k+1) ... (k n) k<n

Для 4 эл-тов будет 3 списка:

((1 2) (3 4))
((1 3) (2 4))
((2 3) (1 4)). Вроде все перечислил.

Ещё раз уточню, что в списке нет одинаковых элементов (т.е. все пары состоят из разных элементов)

Моё решение для 4 тоже даёт 3. Посчитай для больших n...

Для 12:

C(11,6) = 462

12!/(6!*2^6) = 10395

Досадно, что сам не допёр :(

>О, спасибо! Тока, наверно, n-1, а не n(n-1).

ты неправильно используешь обозначение. Оттого и многие не понимают.

Упорядоченныу пары обозначаются как (a b), а не упорядоченные {a b}

Нет общепринятых обозначений в этой области. В каждом учебнике по-своему.

Формула Yareg-а вроде точна. Она получается делением n! на число эквивалентных перестановок.

Ну или если как adriano32 в первом посте сказал - произведение C(2,n) C(2,n-2) C(2,n-4) и так всего n/2 сомножителей, но потом поделить на количество способов переставить эти пары - (n/2)!

Плюсую, у меня та же формула вышла. n!/((n/2)!*2!^(n/2))

Ясно. Я ошибся, значит. Thx