Обсуждение FindStat

[kthxbye]

Относительно недавно узнал о существовании ресурса FindStat.

Из чего он состоит? В базе данных сайта имеются коллекции, отображения и statistic. Коллекция - это какой-нибудь комбинаторный объект (например перестановки, бинарные слова, бинарные деревья, слова Дика, разбиения множества и т.п.), отображение - это преобразование элементов одной коллекции в элементы другой коллекции, и, наконец, statistic - это преобразование элементов коллекции в целые числа.

Для чего все это нужно? Сайт автоматически находит последовательность отображений начиная с определенной коллекции и заканчивая на statistic.

Возьмем, к примеру,

$$b_1(2^m(2n+1))=\sum\limits_{k=0}^{m}b_1(2^kn)$$

Тогда если

$$s_1(n)=\sum\limits_{k=0}^{2^n-1}b_1(k)$$

то у нас получается что $b_1(n)$ это A347205, а $s_1(n)$ это числа Каталана (A000108).

Теперь смотрим какие коллекции у нас содержат $s_1(n)$ элементов для заданного $n$. На выбор у нас аж три коллекции: бинарные деревья, слова Дика и упорядоченные деревья. Начнем с бинарных деревьев. Заходим на SageMathCell и суем в окошко следующий код:

@cached_function
def b(x):
    if x == 0: return 1

    n = x // 2
    fn = n & -n
    return b(n) + b(n - fn) if x % 2 == 0 else b(n)

avd = lambda n: BinaryTrees(n)
dst = lambda n: [i for i in range(2^(n-1)) for _ in range(b(i))]

qu = findstat([(avd(n), dst(n)) for n in range(1, 8)], depth=4)
qu[:2]

Через какое-то время нам выходит следующее:

0: St000289oMp00131oMp00017 (quality [100, 100])
1: St000289oMp00105oMp00094oMp00102oMp00141 (quality [100, 100])

Если выходит quality [100, 100], значит все удалось. Теперь копируем последовательность отображений и суем ее в адресную строку после последней палочки на вот этой странице. Т.е. до у нас https://www.findstat.org/StatisticsDatabase/, а после https://www.findstat.org/StatisticsDatabase/St000289oMp00131oMp00017.

Что же мы видим на данной странице? Мы начали с коллекции "бинарные деревья". Затем через отображение превратили элементы этой коллекции в элементы коллекции "перестановки". Те, в свою очередь, превратили в элементы коллекции "бинарные слова", а завершили все это дело с помощью statistic "бинарные слова -> целые числа".

Что получилось в результате? Каждому числу Каталана соответствуют бинарные деревья определенной длины. Им соответствуют числа от $0$ до $2^n-1$. Сколько раз повторяется число $k$ в результирующей последовательности связанной с деревьями определенной длины? Все очень просто - $b_1(k)$ раз.

Для первого поста я думаю пока хватит, дополнительные детали добавлю в ходе обсуждения.

[kthxbye]

Доступно ли я описал идею назначения сайта? Т.е. она сводится к следующему. Пусть $a(n)$ - произвольная целочисленная последовательность, такая, что $a(n)\in\mathbb{N}$. Кроме того, у $a(n)$ должна быть комбинаторная интерпретация, т.е. правило по которому ее можно получить. Комбинаторная интерпретация должна соответствовать определенной коллекции из представленных в базе. Второй вариант - это когда используя определенную коллекцию мы отсеиваем в ней некоторые элементы.

Дальше мы ищем некую последовательность $b(n)$, которая на определенных промежутках суммируется до $a(n)$. Здесь важно, чтобы последовательные количества суммируемых элементов соответствовали количествам элементов определенной длины одной из представленных в базе коллекции. В моем случае это коллекция "бинарные слова". Если слова начинаются не только с единицы (а оно так и есть), то мы получаем для определенной длины слова определенное количество результирующих целых чисел с помощью statistic "бинарные слова - целые числа". Получается, они принадлежат множеству $\left\lbrace0,1,2,\cdots,2^n-1\right\rbrace$. Другие statistic я пока не изучал.

Теперь еще раз приведу пример. Пусть $a(n)$ это A113227,т.е. количество перестановок, в которых отсутствует паттерн $1-23-4$. Т.е. мы начинаем с коллекции "перестановки" и отсеиваем в ней некоторые элементы. Потом ищем последовательность $b(n)$, которая суммируется до $a(n)$ на промежутках от $0$ до $2^n-1$. В моем случае я начинал с $b(n)$ и узнал что она суммируется до $a(n)$. Последовательность задается следующим образом:

$$b(2^m(2n+1))=\sum\limits_{k=0}^{m}(k+1)b(2^kn)$$

Далее используем следующий код:

def occurrences(pi):
    n = len(pi)
    return sum(1 for k in range(n) for j in range(k-1) for i in range(j) 
               if pi[i] < pi[j] < pi[j+1] < pi[k])
                                
@cached_function
def b(N):
    if not N:
        return 1
    m = valuation(N, 2)
    n = (N // 2^m - 1) / 2
    return sum((k+1)*b(2^k*n) for k in range(m+1))

avd = lambda n: [pi for pi in Permutations(n) if not occurrences(pi)]
dst = lambda n: [i for i in range(2^(n-1)) for _ in range(b(i))]

qu = findstat([(avd(n), dst(n)) for n in range(1, 8)], depth=4)
qu[:2]

Код был любезно представлен неким Мартином Руби вот здесь. Благодаря нему я как раз узнал о существовании сайта FindStat. Все следующие проверки можно осуществлять чуть-чуть видоизменяя этот код, что я и делал. Далее программа возвращает нам

0: St000289oMp00131oMp00087oMp00235oMp00064 (quality [100, 100])
1: St001879oMp00065oMp00175oMp00081oMp00070 (quality [6, 22])

Т.е. нашлась одна последовательность отображений с абсолютным соответствием, которая стартует с урезанной коллекции "перестановки", осуществляет четыре отображения и завершает все statistic "бинарные слова - целые числа". Вот тут лежит иллюстрация. Таким образом мы получили последовательность отображений, которая результирует в целые числа, а количество целых чисел равных $k$, сопоставляемых с элементами определенной длины равно $b(k)$.

Так что если у вас есть $a(n)$ с определенной комбинаторной интерпретацией и $b(n)$, которая суммируется до $a(n)$ на определенных промежутках, то вы можете поискать последовательность отображений с помощью сайта FindStat. У меня таких последовательностей много, но последовательность отображений находится далеко не всегда.