Skellig
@Skellig
Fratercula arctica

Каково количество возможных отношений между N числами?

Очевидно, что для двух чисел это количество равно 3:
  1. A = B
  2. A < B
  3. B < A

В случае трёх чисел обнаруживаем, что есть 13 вариантов:
  1. A = B = C
  2. A < B < C
  3. B < A < C
  4. A < C < B
  5. C < A < B
  6. B < C < A
  7. C < B < A
  8. A = B < C
  9. C < A = B
  10. B = C < A
  11. A < B = C
  12. A = C < B
  13. B < A = C

Рассуждаем следующим образом: когда все три числа равны - это один вариант; когда все три числа неравны друг другу - это еще 3!=6 вариантов; когда два некоторых числа равны между собой и не равны третьему - это еще 3 (число возможных сочетаний из 3 чисел по 2), умноженное на 2 (больше или меньше третьего числа) = 6 вариантов.

Рассуждая подобным образом можно подсчитать, что для 4 чисел есть 81 вариант, а для пяти – 651. Но перебор случаев становится все более сложным и запутанным. Есть ли формула, отражающая зависимость количество отношений между N числами от количества этих чисел?

PS. Поиск по энциклопедии числовых последовательностей не дал результата.
  • Вопрос задан
  • 273 просмотра
Решения вопроса 2
Вообще ваша последовательность похожа на https://oeis.org/A000670:
Number of ways n competitors can rank in a competition, allowing for the possibility of ties.
Also number of asymmetric generalized weak orders on n points.
Also called the ordered Bell numbers.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Для задачи можно рассматривать только неубывающие последовательности, поскольку возрастающие можно получить из них инвертировав порядок.
Имеем N чисел. Пусть ni - длина подпоследовательности, в которой числа равны. Тогда все варианты можно представить как разложение N на слагаемые. Для каждого такого варианта вычисляем количество перестановок чисел с учётом наличия одинаковых
P = N! / ∏(ni!)
, затем суммируем полученные значения.

N = 4
[4] => A = B = C = D, P = 4! / (4!) = 1
[3,1] => A = B = C < D, P = 4! / (3! * 1!) = 4
[2,2] => A = B < C = D, P = 4! / (2! * 2!) = 6
[2,1,1] => A = B < C < D, P = 4! / (2! * 1! * 1!) = 12
[1,3] => A < B = C = D, P = 4! / (1! * 3!) = 4
[1,2,1] => A < B = C < D, P = 4! / (1! * 2! * 1!) = 12
[1,1,2] => A < B < C = D, P = 4! / (1! * 1! * 2!) = 12
[1,1,1,1] => A < B < C < D, P = 4! / (1! * 1! * 1! * 1!) = 24

Итого 24+12+12+4+12+6+4+1 = 75 вариантов
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
AnnTHony
@AnnTHony
Интроверт
Если брать только буквенные обозначения, не привязываясь к числу то формула такая:
количество перестановок БУКВ * количество перестановок используемых знаков

буквы: A, B
знаки: =, <, >

количество перестановок букв: A B, B A - 2
количество перестановок знаков: =, <, > - 3
2 * 3 = 6

1) A = B
2) B = A
3) A < B
4) B < A
5) A > B
6) B > A
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы