Pattern in Sequence of Polynomials

139 Views Asked by At

I generate these polynomials from a counting experiment. There are some obvious patterns i.e the order of $f(n)$ is $n(n+1)/2$. Also, each $f(n)$ has repeated binomial coefficeints corresponding to ${(n+1)\choose k}$ , but each coefficient is repeated twice. I am not able to figure out a closed form function for this. Any help would be much appreciated. $$1 \; 1 \; 3 \; 3 \; 3 \; 1 \; 1$$ $$f(2)=n_{0}^{3} + 3 n_{0} n_{1}^{2} + n_{1}^{3} + 3 n_{1}^{2} n_{2} + 3 n_{1} n_{2}^{2} + n_{2}^{3} + 3 n_{2}^{2} n_{3} + n_{3}^{3}$$ $$1 \; 4 \; 6 \;8 \; 6 \; 1 \; $$ $$\text{This one is a slight exception as there is 8, which is again 4+4 }$$ $$f(3)=n_{0}^{6} + 4 n_{0}^{3} n_{1}^{3} + 6 n_{0} n_{1}^{4} n_{2} + n_{1}^{6} + 8 n_{1}^{3} n_{2}^{3} + 6 n_{1} n_{2}^{4} n_{3} + n_{2}^{6} + 4 n_{2}^{3} n_{3}^{3} + n_{3}^{6}$$ $$1\;1 \; 5 \; 5 \; 10 \; 10 \; 10 \; 10 \; 5\;5\;1\;1 $$ $$f(4)=n_{0}^{10} + 5 n_{0}^{6} n_{1}^{4} + 10 n_{0}^{3} n_{1}^{6} n_{2} + 10 n_{0} n_{1}^{6} n_{2}^{3} + n_{1}^{10} + 5 n_{1}^{6} n_{2}^{4} + 5 n_{1}^{4} n_{2}^{6} + 10 n_{1}^{3} n_{2}^{6} n_{3} + 10 n_{1} n_{2}^{6} n_{3}^{3} + n_{2}^{10} + 5 n_{2}^{4} n_{3}^{6} + n_{3}^{10}$$ $$f(5)=n_{0}^{15} + 6 n_{0}^{10} n_{1}^{5} + 15 n_{0}^{6} n_{1}^{8} n_{2} + 20 n_{0}^{3} n_{1}^{9} n_{2}^{3} + 15 n_{0} n_{1}^{8} n_{2}^{6} + n_{1}^{15} + 6 n_{1}^{10} n_{2}^{5} + 15 n_{1}^{6} n_{2}^{8} n_{3} + 6 n_{1}^{5} n_{2}^{10} + 20 n_{1}^{3} n_{2}^{9} n_{3}^{3} + 15 n_{1} n_{2}^{8} n_{3}^{6} + n_{2}^{15} + 6 n_{2}^{5} n_{3}^{10} + n_{3}^{15}$$ $$f(6)=n_{0}^{21} + 7 n_{0}^{15} n_{1}^{6} + 21 n_{0}^{10} n_{1}^{10} n_{2} + 35 n_{0}^{6} n_{1}^{12} n_{2}^{3} + 35 n_{0}^{3} n_{1}^{12} n_{2}^{6} + 21 n_{0} n_{1}^{10} n_{2}^{10} + n_{1}^{21} + 7 n_{1}^{15} n_{2}^{6} + 21 n_{1}^{10} n_{2}^{10} n_{3} + 7 n_{1}^{6} n_{2}^{15} + 35 n_{1}^{6} n_{2}^{12} n_{3}^{3} + 35 n_{1}^{3} n_{2}^{12} n_{3}^{6} + 21 n_{1} n_{2}^{10} n_{3}^{10} + n_{2}^{21} + 7 n_{2}^{6} n_{3}^{15} + n_{3}^{21}$$ $$f(7)=n_{0}^{28} + 8 n_{0}^{21} n_{1}^{7} + 28 n_{0}^{15} n_{1}^{12} n_{2} + 56 n_{0}^{10} n_{1}^{15} n_{2}^{3} + 70 n_{0}^{6} n_{1}^{16} n_{2}^{6} + 56 n_{0}^{3} n_{1}^{15} n_{2}^{10} + 28 n_{0} n_{1}^{12} n_{2}^{15} + n_{1}^{28} + 8 n_{1}^{21} n_{2}^{7} + 28 n_{1}^{15} n_{2}^{12} n_{3} + 56 n_{1}^{10} n_{2}^{15} n_{3}^{3} + 8 n_{1}^{7} n_{2}^{21} + 70 n_{1}^{6} n_{2}^{16} n_{3}^{6} + 56 n_{1}^{3} n_{2}^{15} n_{3}^{10} + 28 n_{1} n_{2}^{12} n_{3}^{15} + n_{2}^{28} + 8 n_{2}^{7} n_{3}^{21} + n_{3}^{28}$$

Also, more polynomials can be generated upon request. The problem is a slightly more complicated form of Finding pattern in a sequence of polynomials

2

There are 2 best solutions below

4
On BEST ANSWER

Write $t_k=k(k+1)/2$ for the $k$th triangular number and note that $t_{-1} = t_0 = 0$. I think the pattern is $$ f(n) = \sum_{i=-1}^n \binom{n+1}{i+1} [n_0^{t_{n-1-i}} n_1^{t_n-t_{n-1-i}-t_i} n_2^{t_i} + n_3^{t_{n-1-i}} n_2^{t_n-t_{n-1-i}-t_i} n_1^{t_i} ]. $$

My observations that led to this: Each $f(n)$ breaks into two polynomials where the roles of $(n_0, n_1, n_2)$ and $(n_3, n_2, n_1)$ are parallel, e.g., writing out all exponents, $$ f(2) = (n_0^3 n_1^0 n_2^0 + 3n_0^1 n_1^2 n_2^0 + 3n_0^0 n_1^2 n_2^1 + n_0^0 n_1^0 n_2^3)+(n_1^0 n_2^0 n_3^3 + 3n_1^0 n_2^2 n_3^1 + 3n_1^1 n_2^2 n_3^0 + n_1^3n_2^0 n_3^0). $$

Letting $f(n) = g_n(n_0, n_1, n_2) + g_n(n_3, n_2, n_1)$, here are the next two examples: \begin{gather*} g_3(n_0, n_1, n_2) = n_0^6 n_1^0 n_2^0 + 4n_0^3 n_1^3 n_2^0 + 6n_0^1 n_1^4 n_2^1 + 4 n_0^0 n_1^3 n_2^3 + n_0^0 n_1^0 n_2^6,\\ g_4(n_0, n_1, n_2) = n_0^{10} n_1^0 n_2^0 + 5n_0^6 n_1^4 n_2^0 + 10n_0^3 n_1^6 n_2^1 + 10 n_0^1 n_1^6 n_2^3 + 5n_0^0 n_1^4 n_2^6 +n_0^0 n_1^0 n_2^{10}. \end{gather*} So it seems in $g_n(n_0, n_1, n_2)$ that the exponents of $n_0$ and $n_2$ are triangular numbers with the exponent of $n_1$ adding enough so that the degree of each term is $t_n$.

By the way, the coefficient 8 occurs in $f(3)$ since $t_3 - t_2 = t_2$ so that $g_3(n_0,n_1,n_2)$ and $g_3(n_3,n_2,n_1)$ both have a $4n_1^3n_2^3$ term. I don't think that kind of thing happens again, so that every other coefficient will be a binomial coefficient.

1
On

I found out the write answer and it is very much related to Finding pattern in a sequence of polynomials, and also to the answer by @Brian Hopkins (which is incorrect and I cant figure out exactly what). Considering, $$ g_{1}(k)=\sum\limits_{j = 0}^{k} \binom{k}{j}n_0^{\frac{(k - j)(k - j - 1)}{2}} n_1^{(k-j)j} n_2^{\frac{j(j - 1)}{2}} $$ $$ g_{2}(k)=\sum\limits_{j = 0}^{k} \binom{k}{j}n_1^{\frac{(k - j)(k - j - 1)}{2}} n_2^{(k-j)j} n_3^{\frac{j(j - 1)}{2}} $$ We can write the above polynomials as, $$f(k) = g_1(k+1) + g_2(k+1)$$

Note: This answer may seem similar to @Brian Hopkins but try to figure out some terms for expressions with k>3 and you will see the difference. In the Brian Hopkins notation, considering $t_{k} = k(k-1)/2$, the solution becomes, $$f(n) = \sum_{j=0}^{k+1} \binom{k+1}{j} n_0^{t_{k-j}}n_1^{t_k - t_{k-j}-t_{j}}n_2^{t_{j}} + n_1^{t_{k-j}}n_2^{t_k - t_{k-j}-t_{j}}n_3^{t_{j}} $$