Графическое построение (Central polygonal numbers) A002061

[Ascar]

Я так думаю это построение наверное широко известно, поскольку оно достаточно простое.
Количество позиций занимаемых элементами образует последовательность A002061
А общее количество элементов соответсвует последовательности A000225



тут можно получить достаточно много известных последовательностей
неподскажите где можно подробнее почитать про эту графическую интерпретацию

-- Вт июн 07, 2011 16:08:19 --

если рассмотреть каждую $4i+1$ итерацию и подсчитать количество элементов в центральной позиции получим последовательность
A115257
Partial sums of binomial(2n,n)^2

-- Вт июн 07, 2011 16:35:35 --

если на каждой $2i+1$ итерации подсчитывать количество элементов по главной диагонали
получим последовательность A006134

[Ascar]

Пусть центральная часть этого построения лежить в начале кооординат (x,y)-(0,0)
Любой шаг равен 1.

Тоесть координаты первой итерации
0,0

вторая итерация (добавляются 2 элемента)
-1;0
1;0

третья итерация (добавляются 4 элемента)
-1;-1
-1;1
1;-1
1;1

и т.д.
------------------------------------
Можно рассмотреть два интересных построения последовательностей
1)
Подсчитаем количество элементов на каждой $2i+1$ итерации в точках удовлетворяющих условию $y=3-x$, получим последовательность
0, 0, 1, 6, 27, 111, 441, 1728, 6733, 26181, 101763, ...
чемто напоминет последовательность A005284 (1, 6, 27, 111, 440, 1717, 6655, 25728, 99412, ...)

2)
Подсчитаем количество элементов на каждой $4i+3$ итерации в точках удовлетворяющих условию $yx=3$ другими словами сумма элементов в четырех точках (1,3)(3,1)(-1,-3)(-3,-1),
получим последовательность
0, 12, 212, 3152, 45488, ...
каждый элемент представляет число вида $2^{x}p$, где $p$-простое число
0, 2*2*3, 2*2*53, 2*2*2*2*197, 2*2*2*2*28437, ...
к сожелению я смог вычислить только 21 итерацию графического построения ($2^{22}-1$ - элементов)
поэтому утверждать что все элементы последовательности будут иметь данное свойство не могу

[Ascar]

Ascar в сообщении #456108 писал(а):

....
2)
Подсчитаем количество элементов на каждой $4i+3$ итерации в точках удовлетворяющих условию $yx=3$ другими словами сумма элементов в четырех точках (1,3)(3,1)(-1,-3)(-3,-1),
получим последовательность
0, 12, 212, 3152, 45488, ...
каждый элемент представляет число вида $2^{x}p$, где $p$-простое число
0, 2*2*3, 2*2*53, 2*2*2*2*197, 2*2*2*2*28437, ...
к сожелению я смог вычислить только 21 итерацию графического построения ($2^{22}-1$ - элементов)
поэтому утверждать что все элементы последовательности будут иметь данное свойство не могу

ошибся

0, 12, 212, 3152, 45488, 655328,...
соответственно
0, 2*2*3, 2*2*53, 2*2*2*2*197, 2*2*2*2*2843, 2*2*2*2*2*20479,...
к сожелению я смог вычислить только 23 итерации графического построения ($2^{23}-1$ - элементов)
поэтому утверждать что все элементы последовательности будут иметь данное свойство не могу

[Ascar]

Ascar в сообщении #456351 писал(а):

Ascar в сообщении #456108 писал(а):

....
2)
Подсчитаем количество элементов на каждой $4i+3$ итерации в точках удовлетворяющих условию $yx=3$ другими словами сумма элементов в четырех точках (1,3)(3,1)(-1,-3)(-3,-1),
получим последовательность
0, 12, 212, 3152, 45488, ...
каждый элемент представляет число вида $2^{x}p$, где $p$-простое число
0, 2*2*3, 2*2*53, 2*2*2*2*197, 2*2*2*2*28437, ...
к сожелению я смог вычислить только 21 итерацию графического построения ($2^{22}-1$ - элементов)
поэтому утверждать что все элементы последовательности будут иметь данное свойство не могу

ошибся

0, 12, 212, 3152, 45488, 655328,...
соответственно
0, 2*2*3, 2*2*53, 2*2*2*2*197, 2*2*2*2*2843, 2*2*2*2*2*20479,...
к сожелению я смог вычислить только 23 итерации графического построения ($2^{23}-1$ - элементов)
поэтому утверждать что все элементы последовательности будут иметь данное свойство не могу

с условием $yx=3$ немного погарячился, графическое построение является симитричным поэтому достаточно рассмотреть сумму элементов в одной точке (1,3) $x=1$, $y=3$
получаем последовательность (сумма элементов в точке (1,3) на каждой $4i+3$ итерации)
{0, 3, 53, 788, 11372, 163832,...}
факторизация {0, 3, 53, 2*2*197, 2*2*2843, 2*2*2*20479,...}

причем приципиальным является разница между координатами $x$ и $y$ равная 2, и значения координат должны быть нечетными(положительными) числами
так как я смог построить только 23 итерации, я смог рассмотреть точки (1,3) (3,5) (5,7) (сумма элементов в этих точках на каждой $4i+3$ итерации) и то только начальные значения рядов, но выглядит интересно

y   x   последовательность                  факторизация последовательности
3   1   {0, 3, 53, 788, 11372, 163832,...}   {0, 3, 53, 2*2*197, 2*2*2843, 2*2*2*20479,...} 
5   3   {0, 0, 5, 152, 3176, 57626,...}      {0, 0, 5, 2*2*2*19, 2*2*2*397, 2*28813,...} 
7   5   {0, 0, 0, 7, 331, 9406,...}         {0, 0, 0, 7, 331, 2*4703,...}
9   7   {0, 0, 0, 0, 9, 614,...}            {0, 0, 0, 0, 3*3, 2*307,...}

[Ascar]

Ascar в сообщении #456108 писал(а):

2)
Подсчитаем количество элементов на каждой $4i+3$ итерации в точках удовлетворяющих условию $yx=3$ другими словами сумма элементов в четырех точках (1,3)(3,1)(-1,-3)(-3,-1),
получим последовательность
0, 12, 212, 3152, 45488, ...
каждый элемент представляет число вида $2^{x}p$, где $p$-простое число
0, 2*2*3, 2*2*53, 2*2*2*2*197, 2*2*2*2*28437, ...
к сожелению я смог вычислить только 21 итерацию графического построения ($2^{22}-1$ - элементов)
поэтому утверждать что все элементы последовательности будут иметь данное свойство не могу

это утверждение неверно

-- Пт июн 10, 2011 17:44:44 --

Ascar в сообщении #456505 писал(а):

y   x   последовательность                  факторизация последовательности
3   1   {0, 3, 53, 788, 11372, 163832,...}   {0, 3, 53, 2*2*197, 2*2*2843, 2*2*2*20479,...} 
5   3   {0, 0, 5, 152, 3176, 57626,...}      {0, 0, 5, 2*2*2*19, 2*2*2*397, 2*28813,...} 
7   5   {0, 0, 0, 7, 331, 9406,...}         {0, 0, 0, 7, 331, 2*4703,...}
9   7   {0, 0, 0, 0, 9, 614,...}            {0, 0, 0, 0, 3*3, 2*307,...}

каждое первое,второе и третье положительное число можно вычислить через значение координаты $y$
(остальные тоже вычисляются, но стат данных мало и пока определить как именно вычисляются нет возможности)

первое
$y$
{3,5,7,9...}

второе
$\frac{1}{2}y^{3}+\frac{5}{2}y^{2}+5y+2$
{53,152,331,614...}

третье значение
$\frac{1}{12}y^{5}+\frac{4}{3}y^{4}+\frac{107}{12}y^{3}+\frac{86}{3}y^{2}+45y+26$
{788,3176,9406...}

осталось только понять закон образования данных многочленнов (что бы понять как строить эти последовательности)
может мыть эти многочлены гдето уже описаны и изучены???

самое замечательное свойство последнего многочлена мне кажется :) что при любом ЦЕЛОМ положительном значении $y$ ответ будет целое число
или это очевидно?

[maxal]

Ascar в сообщении #456531 писал(а):

третье значение
$\frac{1}{12}y^{5}+\frac{4}{3}y^{4}+\frac{107}{12}y^{3}+\frac{86}{3}y^{2}+45y+26$
{788,3176,9406...}

самое замечательное свойство последнего многочлена мне кажется :) что при любом ЦЕЛОМ положительном значении $y$ ответ будет целое число
или это очевидно?

Запишите его как $\frac{1}{12}(y^5+16y^4+107y^3+344y^2+540y+312)$ и убедитесь, что для для всех $y=0,1,\dots,11$ (то есть, для всех вычетов по модулю 12) значение многочлена в скобках делится на 12. Этого достаточно, чтобы оно делилось на 12 и для всех остальных значений $y$.

[Ascar]

maxal в сообщении #461716 писал(а):

Ascar в сообщении #456531 писал(а):

третье значение
$\frac{1}{12}y^{5}+\frac{4}{3}y^{4}+\frac{107}{12}y^{3}+\frac{86}{3}y^{2}+45y+26$
{788,3176,9406...}

самое замечательное свойство последнего многочлена мне кажется :) что при любом ЦЕЛОМ положительном значении $y$ ответ будет целое число
или это очевидно?

Запишите его как $\frac{1}{12}(y^5+16y^4+107y^3+344y^2+540y+312)$ и убедитесь, что для для всех $y=0,1,\dots,11$ (то есть, для всех вычетов по модулю 12) значение многочлена в скобках делится на 12. Этого достаточно, чтобы оно делилось на 12 и для всех остальных значений $y$.

спасибо за коментарий
но если строить дальше эти полиномы проверять придется на очень больших интервалах
я рассмотрел эти полиномы до 13 степени

$f_{1}(x)=\frac{1}{1}x$

$f_{2}(x)=\frac{1}{2}x^{3}+\frac{5}{2}x^{2}+5x+2$

$f_{3}(x)=\frac{1}{12}x^{5}+\frac{4}{3}x^{4}+\frac{107}{12}x^{3}+\frac{86}{3}x^{2}+45x+26$

$f_{4}(x)=\frac{1}{144}x^{7}+\frac{11}{48}x^{6}+\frac{475}{144}x^{5}+\frac{419}{16}x^{4}+\frac{4435}{36}x^{3}+\frac{4093}{12}x^{2}+515x+326$

$f_{5}(x)=\frac{1}{2880}x^{9}+\frac{7}{360}x^{8}+\frac{703}{1440}x^{7}+\frac{571}{80}x^{6}+\frac{192029}{2880}x^{5}+\frac{32919}{80}x^{4}+\frac{1206121}{720}x^{3}+\frac{195046}{45}x^{2}+\frac{19409}{3}x+4246$

$f_{6}(x)=\frac{1}{86400}x^{11}+\frac{17}{17280}x^{10}+\frac{11}{288}x^{9}+\frac{2561}{2880}x^{8}+\frac{396151}{28800}x^{7}+\frac{853363}{5760}x^{6}+\frac{1956751}{1728}x^{5}+\frac{828548}{135}x^{4}+\frac{27729793}{1200}x^{3}+\frac{20721803}{360}x^{2}+\frac{256163}{3}x+57166$

$f_{7}(x)=\frac{1}{3628800}(x^{13}+120x^{12}+6665x^{11}+226164x^{10}+5221203x^{9}[phone]x^{8}[phone]x^{7}[phone]x^{6}[phone]x^{5}[phone]x^{4}[phone]x^{3}[phone]x^{2}[phone]x)+788974$

и т.д.
но если честно дальше я построить несмог, но очевидно что этот процесс бесконечен
общее представление начинается

$f_{n}(x)=\frac{1}{(n-1)!n!}(x^{2n-1}+(3n^{2}-4n+1)x^{2n-2}+(\frac{9}{2}n^{4}-\frac{43}{3}n^{3}+17n^{2}-\frac{49}{6}n+1)x^{2n-3}+(\frac{68}{15}n^{6}-\frac{388}{15}n^{5}+\frac{202}{3}n^{4}-\frac{733}{6}n^{3}+\frac{2777}{15}n^{2}-\frac{5819}{30}n+85)x^{2n-4}+...)$

но вывести общую формулу тоже не смог

очевидно что есть связь с числами Моцкина A110236
более подробно здесь https://oeis.org/wiki/Graphical_structure_of_the_sequence_A002061(Central_polygonal_numbers)

убеждатся для следующих полиномов на значениях $x=0,1,\dots,(n-1)!n!$ , будет уже проблематично, но я утверждаю что эти полиномы дают целое значение при любом аргументе являющемся целым числом

[maxal]

Пусть точка $(x,y)$ достигнута за $n$ шагов (звеньев ломаной) из точки $(0,0)$.
Такие ломаные можно прежде всего охарактеризовать количеством шагов на север $N$, юг $S$, запад $W$ и восток $E$. Тогда:

$$\begin{cases} N+S+W+E = n\\ N-S = y\\ E-W = x\\ (E+W) - (N+S) = n\bmod 2\end{cases}$$

Эта система имеет единственное решение:

$$\begin{cases} N = \frac{\lfloor n/2\rfloor + y}{2}\\ S = \frac{\lfloor n/2\rfloor - y}{2}\\ W = \frac{\lceil n/2\rceil - x}{2}\\ E = \frac{\lceil n/2\rceil + x}{2}\end{cases}$$

Эти числа являются целыми тогда и только тогда, когда $x\equiv \lfloor n/2\rfloor\pmod{2}$ and $y\equiv \lceil n/2\rceil\pmod{2}$.

Ну а число различных таких ломанных соответственно равно

$$\binom{N+S}{N} \binom{W+E}{W} = \binom{\lfloor n/2\rfloor}{\frac{\lfloor n/2\rfloor + y}{2}}\binom{\lceil n/2\rceil}{\frac{\lceil n/2\rceil + x}{2}}.$$

Однако, значения расходятся с вашими. Например, для $(x,y)=(1,3)$ количество ломаных из 10 звеньев моя формула дает 50. А вы утверждаете, что их 53. Кто из нас ошибся?

[Ascar]

maxal в сообщении #461817 писал(а):

Однако, значения расходятся с вашими. Например, для $(x,y)=(1,3)$ количество ломаных из 10 звеньев моя формула дает 50. А вы утверждаете, что их 53. Кто из нас ошибся?

скорее всего вы не ошиблись
наверное вы находите новые элементы (элементы созданные 10 звеньями? правильно понял?)
а я говорю о сумме элементов через определенное число шагов в заданной точке
$3+50=53$
т.е. до 10 звений было еще 3 элемента созданные меньшим количеством звений? наверное так
извините если ошибся :)

количество элементов я считаю напрямую
тоесть создаю графическое построение приведенное на первом рисунке
исходный код Delphi http://www.2shared.com/file/i1NnJTVy/A191004.html
текст программы без коментариев, разобрать сложно, но если интересно на все вопросы отвечу
проверял несколько раз, вроде я не ошибся в логике

[maxal]

Ну что ж, теперь все встало на свои места. Можно вывести формулу для ваших многочленов.

Итак, пусть

$$L(x,y,n) = \binom{\lfloor n/2\rfloor}{\frac{\lfloor n/2\rfloor + y}{2}}\binom{\lceil n/2\rceil}{\frac{\lceil n/2\rceil + x}{2}}.$$

Тогда для нечетного $z$,

$$f_k(z) = \sum_{n\leq 2z+4k\atop n\equiv 2\pmod{4}} \binom{\lfloor n/2\rfloor}{\frac{\lfloor n/2\rfloor + z+2}{2}}\binom{\lceil n/2\rceil}{\frac{\lceil n/2\rceil + z}{2}} = \sum_{m\leq t+k} \binom{2m+1}{m+2+t}\binom{2m+1}{m+1+t} .$$

Здесь мы сделали подстановку $n=4m+2$ и $z=2t+1$.

Осталось свернуть эту сумму...

[maxal]

А сворачивается легко:

$$f_k(z) = \sum_{m\leq t+k} \binom{2m+1}{m+2+t}\binom{2m+1}{m+1+t} = \sum_{j=1}^k \binom{2j+z}{j-1}\binom{2j+z}{j},$$

где мы сделали замену $m=j+t$.

Так как $\binom{2j+z}{j}$ является полиномом $j$-й степени от $z$, то $f_k(z)$ является полиномом степени $2k+1$. Отсюда же также получается и целочисленность значений $f_k(z)$, так как многочлены биномиальных коэффициентов целочисленны.

[Ascar]

или в виде многочлена

$f_{n}(x)=\frac{1}{(n-1)!n!}(x+n-1)\prod_{i=1}^{n-1}(x+n-1+i)^{2}+f_{n-1}(x)$

где
$f_{1}(x)=x$
$n=2,3,4,5....$

[Ascar]

собственно понятно что построение в первом посте есть бином

треугольник Паскаля - есть бином построенный в одномерном пространстве, просто данное построение растягивают в треугольник, что бы легче его анализировать

мое построение есть бином в двухмерном пространстве


анологично можно построить бином в трех мерном пространстве


и т.д. в 4-х 5-и .... мерном
бином обладает свойством равномерно заполнять пространство любой размерности