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

Question

[Skellig]

Очевидно, что для двух чисел это количество равно 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. Поиск по энциклопедии числовых последовательностей не дал результата.

Comments

[Saboteur]

Вы уверены, что для 4 вариантов будет 81, а не 109?

[Skellig]

Saboteur: Да. Когда все четыре числа равны – это 1 случай; когда все четыре числа не равны друг другу – это еще 4! = 24 случая; когда некоторые три числа равны между собой и не равны четвертому – это еще 8 случаев (4 сочетания по 3 из 4 и 2 варианта (больше-меньше оставшегося числа) для каждого из сочетаний). Оставшиеся случаи – это когда между собой равны некоторые два числа из четырех и не равны оставшимся двум. Число таких возможных пар будет равно количеству сочетаний по 2 из 4 = 6. И для каждой из шести таких пар могут быть следующие варианты: 2 оставшихся числа также равны между собой (и тогда есть два варианта: первая пара равных чисел больше или меньше второй пары равных чисел) или два оставшихся числа не равны друг другу (и тогда получается, что у нас есть три неравных друг другу сущности, для которых есть 3!=6 вариантов расстановок). Получается, что для каждой из 6 пар есть 8 вариантов отношений с оставшимися 2 числами – это 48 вариантов всего. И общее количество возможных вариантов: 1 + 24 + 8 + 48 = 81. А как вы получили 109?

Answer 1

[Александр Опарин]

Вообще ваша последовательность похожа на 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.

Comments

[Skellig]

Да весьма похоже, Rsa97 привел привел правильный расчет для N=4 и он совпадает с последовательностью. Спасибо.

Answer 2

[Rsa97]

Для задачи можно рассматривать только неубывающие последовательности, поскольку возрастающие можно получить из них инвертировав порядок.
Имеем N чисел. Пусть n_i - длина подпоследовательности, в которой числа равны. Тогда все варианты можно представить как разложение N на слагаемые. Для каждого такого варианта вычисляем количество перестановок чисел с учётом наличия одинаковых
P = N! / ∏(n_i!)
, затем суммируем полученные значения.

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 вариантов

Comments

[Skellig]

Да, увидел ошибку в своих рассуждениях: я считал A = B < C = D и C = D < A = B за разные случаи, 12 вместо 6. Но и у вас здесь чисто арифметическая ошибка: в [2,1,1] => A = B < C < D должно быть P = 4! / (2! * 1! * 1!) = 12. Такие образом правильное число вариантов для 4 чисел –75. Можете отредактировать ответ, чтобы я отметил его как решение?

[Rsa97]

Skellig: Угу, поправил.

Answer 3

[Антон Федорян]

Если брать только буквенные обозначения, не привязываясь к числу то формула такая:
количество перестановок БУКВ * количество перестановок используемых знаков

буквы: 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

Comments

[Skellig]

В вашем примере можно рассуждать по правилу умножения: первый символ выбираем из букв (любая буква из N), второй символ выбираем из знаков отношений (любой из трёх), третий символ – снова из букв (их осталось N-1) и так далее. Для трёх букв (и соответственно двух знаков) получаем количество возможных сочетаний 3 * 3 * 2 * 3 * 1= 54, когда их должно быть 13 – проблема метода в том, что он не позволяет узнать количество дублирующихся комбинаций.