Любителям поэкспериментировать

[kthxbye]

Приветствую всех любителей поэкспериментировать! Сегодня я решил представить вам трансформацию, с помощью которой можно получать кучу разнородных последовательностей из OEIS практически не прилагая при этом никаких усилий. Трансформация следующая: пусть

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

пусть также

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

Вот и все! Каркас готов. Следует отметить, что разложение числа на множители $2^m$ и $2n+1$ единственно (что по сути и так очевидно).

Что мы только что получили из ничего? Посмотрите на значения $s(n)$. Да это же числа Каталана (A000108)! Теперь добавим пару функций для экспериментального творчества:

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

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

Все это опять-таки суммируем через $s(n)$. Что же мы будем иметь? Ну, например для $f(n)$:

• $n$ [ $\to$ ] A036765
• $n+1$ [ $\to$ ] A106228
• $n+2$ [ $\to$ ] A001764
• $n+3$ [ $\to$ ] A108447
• $n+4$ [ $\to$ ] A118346
• $n+5$ [ $\to$ ] A118351
• $2^n$ [ $\to$ ] A006318
• $3^n$ [ $\to$ ] A108524
• $(-1)^n$ [ $\to$ ] A090412
• $\binom{2n}{n}\frac{1}{n+1}$ [ $\to$ ] A224071
• $\binom{2n}{n}\frac{(-1)^n}{n+1}$ [ $\to$ ] A000045
• $\binom{n}{2}$ [ $\to$ ] A198951
• $\binom{n+2}{2}$ [ $\to$ ] A300048
• $\binom{n+3}{2}$ [ $\to$ ] A002293
• $\binom{n+4}{3}$ [ $\to$ ] A002294
• $\binom{n+5}{4}$ [ $\to$ ] A002295
• $\binom{n+6}{5}$ [ $\to$ ] A002296
• $\binom{n+7}{6}$ [ $\to$ ] A007556

Кроме того, для $g(n,m)$ будем иметь

• $\binom{n}{m}$ [ $\to$ ] A000110
• $\binom{n+1}{m}$ [ $\to$ ] A000142
• $\binom{n-1}{m}$ [ $\to$ ] A092920
• $\binom{n+1}{m+1}$ [ $\to$ ] A074664
• $\binom{n}{m+1}$ [ $\to$ ] A006789
• $\binom{n-1}{n-m-1}$ [ $\to$ ] A099950
• $\binom{n-1}{n-m}$ [ $\to$ ] A005001

Несмотря на то, что

$$\binom{n-1}{m}=\binom{n-1}{n-m-1}$$

значения почему-то получаются разные. Поэтому при проверке $\binom{n-q}{m}$ желательно отдельно прогонять $\binom{n-q}{n-m-q}$.

Что я предлагаю вам? Присваивайте все, что душе угодно функциям $f(n)$ и $g(n,m)$ и проверяйте есть ли результат в OEIS (ну и делитесь им в этой теме). Вот простенькая программка на PARI/GP:

f(n)=n
g(n,m)=binomial(n,m)
s1(n)=my(v, v1); v=vector(2^n,i,0); v[1]=1; for(i=1,#v-1,my(A=valuation(i,2), B=i\2^(A+1)); v[i+1]=sum(j=0,A,f(A-j)*v[2^j*B+1])); v1=[1]; for(i=1,n,v1=concat(v1,sum(j=0,2^i-1,v[j+1]))); v1
s2(n)=my(v, v1); v=vector(2^n,i,0); v[1]=1; for(i=1,#v-1,my(A=valuation(i,2), B=i\2^(A+1)); v[i+1]=sum(j=0,A,g(A,j)*v[2^j*B+1])); v1=[1]; for(i=1,n,v1=concat(v1,sum(j=0,2^i-1,v[j+1]))); v1
x=s1(15)
print(x)

В зависимости от используемой функции оставляйте x=s1(15) для $f(n)$ и меняйте на x=s2(15) для $g(n,m)$. Если вы еще никогда не работали с PARI/GP, то никогда не поздно этому научиться (хотя учиться особо не придется: даже без знания специальных функций для некоторых популярных чисел последние всегда можно будет посчитать написав отдельную функцию). Я не спец по PARI/GP, но можете задавать вопросы, на самые простые вероятно отвечу.

На этом все отнюдь не заканчивается, а только начинается. В следующей теме я расскажу как можно применить информацию о наличии соответствия $s(n)$ одной из имеющихся в OEIS последовательностей если у последней имеется относительно простая комбинаторная интерпретация.

Ну и напоследок небольшой челлендж. Попробуйте найти функцию $g(n,m)$, такую, что

$$s_2(n)=\sum\limits_{k=0}^{2^n-1}b_2(k)=\sum\limits_{k=0}^{n}g(n,k)$$

[kthxbye]

Уверен, последовательностей найдется куча. Стоит только начать. Вот еще несколько по горячим следам для $g(n,m)$:

• $2^m\binom{n}{m}$ [ $\to$ ] A135922
• $2^{n-m}\binom{n}{m}$ [ $\to$ ] A007405
• $3^{n-m}\binom{n}{m}$ [ $\to$ ] A003575
• $4^{n-m}\binom{n}{m}$ [ $\to$ ] A003576
• $5^{n-m}\binom{n}{m}$ [ $\to$ ] A003577
• $6^{n-m}\binom{n}{m}$ [ $\to$ ] A003578
• $7^{n-m}\binom{n}{m}$ [ $\to$ ] A003579
• $8^{n-m}\binom{n}{m}$ [ $\to$ ] A003580
• $9^{n-m}\binom{n}{m}$ [ $\to$ ] A003581
• $10^{n-m}\binom{n}{m}$ [ $\to$ ] A003582
• $2^{n-m}\binom{n+1}{m}$ [ $\to$ ] A014307
• $2^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A001147
• $3^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A007559
• $4^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A007696
• $5^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A008548
• $6^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A008542
• $7^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A045754
• 8^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A045755
• $9^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A045756
• $10^{n-m+1}\binom{n+1}{m}$ [ $\to$ ] A144773
• $2^{n-m+1}\binom{n}{m}$ [ $\to$ ] A126390
• $3^{n-m+1}\binom{n}{m}$ [ $\to$ ] A284859
• $4^{n-m+1}\binom{n}{m}$ [ $\to$ ] A285064
• $2^{n-m-1}\binom{n}{m}$ [ $\to$ ] A355165/A000079
• $2^{n-m-1}\binom{n+1}{m}$ [ $\to$ ] A142967/A000079

[kthxbye]

Каким-то образом я пришел к идее обратной трансформации: если известно $s(n)$, то как вычислить $f(n)$? Здесь мне пригодились дополнительные значения

$$s(n,m)=\sum\limits_{k=0}^{2^n-1}b(2^mk)$$

Опытным путем было установлено, что

$$s(n,m) = s(n+1,m-1) - \sum\limits_{k=0}^{m-1}f(m-k-1)s(n,k)$$

Т.е. если мы знаем $s(n,0)$, то можем найти все значения $s(n,m)$ для любого $m>0$. Важно: работает только для возрастающих последовательностей $s(n,0)$ у которых $s(0,0)=1$. Исходя из этих условий мы без проблем можем задавать $s(0,m)=1$.

По сути для вычисления $f(n)$ нам достаточно знать $s(1,n)$ и все предыдущие значения $f(n)$:

$$f(n)=s(1,n)-1-\sum\limits_{k=0}^{n-1}f(k)$$

Отсюда мы также учимся вычислять $s(n,0)$ без суммирования $b(k)$:

$$s(n,m)=s(n-1,m+1)+\sum\limits_{k=0}^{m}f(m-k)s(n-1,k), s(0,m)=1$$

Если сохранять значения в массивы, то скорость счета увеличивается в разы. Данные результаты неоптимальны при вычислении отдельных значений, но для получения списка $n$ первых значений $f(n)$ или $s(n,0)$ они крайне полезны.

Теперь вы можете получать больше значений $s_1(n)$:

f(n)=n
s1(n)=my(v, v1); v=vector(n+1,i,1); v1=v; v2=vector(n+1,i,0); v2[1]=1; for(i=1,n,for(j=1,n-i+1,v1[j]=v[j+1]+sum(k=1,j,f(j-k)*v[k])); v=v1; v2[i+1]=v[1];); v2
w=s1(50)
print(w)

Кроме того, вы можете выбрать любую последовательность в энциклопедии (обязательно возрастающую и с первым членом равным единице!), скопировать несколько первых членов и вставить в следующую программку:

w=[1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525]
f(n)=my(A=w, B=[A,[1]], v); v=vector(n+1,i,0); v[1]=A[2]-A[1]; for(i=2,n+1,B=vector(i+1,j,if(j==1,B[1],vector(i-j+2,k,if(j==i+1,1,if(k<i-j+2,B[j][k]))))); for(j=2,i,B[j][i-j+2]=B[j-1][i-j+3]-sum(k=1,j-1,v[j-k]*B[k][i-j+2])); v[i]=B[i][2]-sum(j=1,i-1,v[j])-1); v
w1=f(#w-2)
print(w1)

Она выполнит обратную трансформацию, т.е. вернет вам $f(n)$, наличие которой вы можете проверить в энциклопедии. Если результат окажется положительным, помещайте исходную и результирующую последовательность в этой теме.

В приведенном выше примере мы берем за $s(n,0)$ последовательность A000041 и получаем гипотезу, что $f(n)$ это A176950, члены которой умножены на $(-1)^n$.

Ну а я пока продолжу работу над обратной трансформацией для $g(n,m)$. Жду ваших постов!

[wrest]

У меня такое чувство, что вы нашли золотую жилу типа такой: берем формулу арифметической прогрессии например $a_i=k+ni$ и для разных комбинаци $k$ и $n$ получаем бесконечное количество последовательностей Или я неправильно понял?

[kthxbye]

wrest в сообщении #1594760 писал(а):

У меня такое чувство, что вы нашли золотую жилу типа такой: берем формулу арифметической прогрессии например $a_i=k+ni$ и для разных комбинаци $k$ и $n$ получаем бесконечное количество последовательностей Или я неправильно понял?

Ради интереса можете понаводить мышкой на номера последовательностей из энциклопедии и примерно оценить насколько интересна приведенная мною трансформация. Лично мне она кажется достаточно интересной. Может быть кто-нибудь даже возьмется ее изучать и тогда экспериментальная математика превратится в настоящую.