The application of Synthetic division in Polynomial theory
by fungarwai, Feb 9, 2023, 4:40 AM
Power sum of polynomial roots
Synthetic division can be applied to find the power sums of roots of a polynomial
by dividing
with 
has two real roots 


The coefficients of the quotient show that

This result is caused by the formula
Reference: The application of Synthetic division in Polynomial theory (Chinese) Section 1.1.5
Proof
Example
Python program to generate Synthetic division in LaTeX code
pywindow code
Synthetic division can be applied to find the power sums of roots of a polynomial

by dividing






The coefficients of the quotient show that

This result is caused by the formula

Reference: The application of Synthetic division in Polynomial theory (Chinese) Section 1.1.5
Proof
Let
,
Suppose
, the Laurent series of
can be expressed as


Each term in the Laurent series is unique.
As the coefficients of the quotient are determined one by one with Synthetic division, the power sums of polynomial roots are computed.

Suppose




Each term in the Laurent series is unique.
As the coefficients of the quotient are determined one by one with Synthetic division, the power sums of polynomial roots are computed.
Example
a,b,c are roots of the equation x³-9x+9 = 0.
Find the value of -
1/a³ + 1/b³ + 1/c³
1/a⁵ + 1/b⁵ + 1/c⁵.
Reference: Sum of powers of roots

Let
Compute
with Synthetic division

i.e.
Find the value of -
1/a³ + 1/b³ + 1/c³
1/a⁵ + 1/b⁵ + 1/c⁵.
Reference: Sum of powers of roots

Let

Compute


i.e.

Python program to generate Synthetic division in LaTeX code
dividend=[27,-18,0];#input by user, 27x^2-18x for example divisor=[9,-9,0,1];#input by user, 9x^3-9x^2+1 for example def roundint(x): if x == int(x): return str(int(x)) else: for k in range(1,100): T=0 if x*k == int(x*k): T=1;break; if T==1: return "\dfrac{"+str(int(x*k))+"}{"+str(k)+"}" else: return str(round(x,3)) qlen=11;e=0; dlen=len(divisor)-1; ddlen=len(dividend); dd="~ " for k in range(0,ddlen): dividend[k]=dividend[k]/divisor[0] dd=dd+"& "+roundint(dividend[k])+" " for k in range(0,qlen-ddlen+1): dividend.append(0) dd=dd+"\\\\\n" for k in range(1,dlen+1): divisor[k]=-divisor[k]/divisor[0] q=[] q.append(dividend[0]) qq="~ & "+roundint(q[0])+" " s="$\\begin{array}{c|" s2=[] for k in range(1,dlen+1): s2.append(roundint(divisor[k])+" ") for k in range(0,dlen): for i in range(0,k+1): s2[k]=s2[k]+"& ~ " for i in range(0,qlen-dlen): t=dividend[i+1] for k in range(0,dlen): tt=q[i]*divisor[k+1] s2[k]=s2[k]+"& "+roundint(tt)+" " if i-k >= 0: t=t+q[i-k]*divisor[k+1] q.append(t) if t==0: e=e+1 else: e=0 if e>=dlen and i>=ddlen-1: break qq=qq+"& "+roundint(t)+" " for i in range(qlen-dlen,qlen-1): if e>=dlen and i>=ddlen-1: break t=dividend[i+1] for k in range(0,dlen): if i-k < qlen-dlen: t=t+q[i-k]*divisor[k+1] q.append(t) qq=qq+"& "+roundint(t)+" " for k in range(0,qlen+1): s=s+"c" s=s+"}\n"+dd for k in range(0,dlen): s=s+s2[k]+"\\\\\n" s=s+"\\hline\n"+qq+"\\end{array}$" print(s)
pywindow code
[pywindow]
dividend=[27,-18,0];#input by user, 27x^2-18x for example
divisor=[9,-9,0,1];#input by user, 9x^3-9x^2+1 for example
def roundint(x):
if x == int(x):
return str(int(x))
else:
for k in range(1,100):
T=0
if x*k == int(x*k):
T=1;break;
if T==1:
return "\dfrac{"+str(int(x*k))+"}{"+str(k)+"}"
else:
return str(round(x,3))
qlen=11;e=0;
dlen=len(divisor)-1;
ddlen=len(dividend);
dd="~ "
for k in range(0,ddlen):
dividend[k]=dividend[k]/divisor[0]
dd=dd+"& "+roundint(dividend[k])+" "
for k in range(0,qlen-ddlen+1):
dividend.append(0)
dd=dd+"\\\\\n"
for k in range(1,dlen+1):
divisor[k]=-divisor[k]/divisor[0]
q=[]
q.append(dividend[0])
qq="~ & "+roundint(q[0])+" "
s="$\\begin{array}{c|"
s2=[]
for k in range(1,dlen+1):
s2.append(roundint(divisor[k])+" ")
for k in range(0,dlen):
for i in range(0,k+1):
s2[k]=s2[k]+"& ~ "
for i in range(0,qlen-dlen):
t=dividend[i+1]
for k in range(0,dlen):
tt=q[i]*divisor[k+1]
s2[k]=s2[k]+"& "+roundint(tt)+" "
if i-k >= 0:
t=t+q[i-k]*divisor[k+1]
q.append(t)
if t==0:
e=e+1
else:
e=0
if e>=dlen and i>=ddlen-1:
break
qq=qq+"& "+roundint(t)+" "
for i in range(qlen-dlen,qlen-1):
if e>=dlen and i>=ddlen-1:
break
t=dividend[i+1]
for k in range(0,dlen):
if i-k < qlen-dlen:
t=t+q[i-k]*divisor[k+1]
q.append(t)
qq=qq+"& "+roundint(t)+" "
for k in range(0,qlen+1):
s=s+"c"
s=s+"}\n"+dd
for k in range(0,dlen):
s=s+s2[k]+"\\\\\n"
s=s+"\\hline\n"+qq+"\\end{array}$"
print(s)
[/pywindow]
This post has been edited 1 time. Last edited by fungarwai, Feb 9, 2023, 4:57 AM
GCD of 2^n-1 and 2^m+1
by fungarwai, Feb 23, 2022, 1:46 PM

Proof



Proof




If


Proof





Proof



Example
Showing gcd(2^m−1,2^n+1)=1 when m is odd
When m is odd,
. Therefore 
有序數對的個數
Count the number of ordered sets
for
when 
That implies counting the number of ordered sets
for 
The number of
when
is ![$[\frac{30}{2^k}]-[\frac{30}{2^{k+1}}]$](//latex.artofproblemsolving.com/2/f/b/2fba818a7be5819cbd5269270d18c4816fe99bc3.png)
![$N(k)=[\frac{30}{2^k}]-[\frac{30}{2^{k+1}}]=\begin{cases}15 & k=0\\8 & k=1\\4 & k=2\\2 & k=3\\1 & k=4\end{cases}$](//latex.artofproblemsolving.com/d/5/6/d5629b1247c77761b91b4695781350960c920b62.png)


When m is odd,


有序數對的個數
Count the number of ordered sets



That implies counting the number of ordered sets


The number of


![$[\frac{30}{2^k}]-[\frac{30}{2^{k+1}}]$](http://latex.artofproblemsolving.com/2/f/b/2fba818a7be5819cbd5269270d18c4816fe99bc3.png)
![$N(k)=[\frac{30}{2^k}]-[\frac{30}{2^{k+1}}]=\begin{cases}15 & k=0\\8 & k=1\\4 & k=2\\2 & k=3\\1 & k=4\end{cases}$](http://latex.artofproblemsolving.com/d/5/6/d5629b1247c77761b91b4695781350960c920b62.png)



Proof






By LTE,








Proof






By LTE,










This post has been edited 3 times. Last edited by fungarwai, Feb 25, 2022, 12:32 PM
modular arithmetic on 1^1+2^2+3^3+...+n^n
by fungarwai, Dec 13, 2021, 1:45 PM
To find the modular residue
,
the main idea is rewriting
as



While
is enough small,
would be simply zero.
has to be calculated manually. Make it as short as it can.
Here
is the main problem.

Proof

(Refer Summation with polynomial)



Note 1


Note 2





Note 3


Proof
Example
Python program for general cases
input values for n, m to get
input values for N, p, s to get
for 

the main idea is rewriting




While



Here


Proof


(Refer Summation with polynomial)



Note 1



Note 2






Note 3
By Kummer's theorem,
is equal to the number of carries
when
is added to
in base p
There are at least
number of carries when 



Otherwise,



when


There are at least





Otherwise,




Proof
Example
Summation
Find the units digit of
program check
program check


A spin off an old USAMTS
Determine the rightmost three digits of the number

program check
program check

(Refer Application of elementary operations in Euclidean algorithm)


Find the units digit of


N = 1010 p = 2 s = 1 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)

N = 404 p = 5 s = 1 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)


sum=0;n=2021;m=10; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
A spin off an old USAMTS
Determine the rightmost three digits of the number


N = 500 p = 2 s = 3 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)

N = 200 p = 5 s = 3 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)

(Refer Application of elementary operations in Euclidean algorithm)


sum=0;n=1000;m=1000; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
Python program for general cases
input values for n, m to get

n = int(input("n=")) m = int(input("m=")) sum=0; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
input values for N, p, s to get


N = int(input("N=")) p = int(input("p=")) s = int(input("s=")) sum=0;m=p**s; for r in range(1,p): for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
This post has been edited 2 times. Last edited by fungarwai, Dec 14, 2021, 12:15 PM
Coincidence on Linear Regression Analysis with president election data
by fungarwai, Feb 16, 2021, 12:58 AM
The Linear Regression model with president election data indicates that a candidate has stolen other candidates averagely 120 votes on each ward in Milwaukee
Here are data sources from Milwaukee
11-3-20 General and Presidential Election - Unofficial Results
My Regression Model is
Candidate's vote = Candidate's voting rate × Total votes
which is no constant term expected
Form data at Nov. 4, 2020
Biden's vote = 5.3191 + 0.5821 × Total votes
R^2=0.9087
Trump's vote = -6.6928 + 0.4002 × Total votes
R^2=0.8255
No constant term is expected.
This constant term is possibly caused by Biden stealing other candidate's vote.
However, the constant term lies on the convincible interval involving 0.
Without constant term, my Linear Regression model at Nov. 4, 2020 becomes:
Biden's vote = 0.5877 × Total votes
R^2=0.9085
Trump's vote = 0.3931 × Total votes
R^2=0.8262
which is Candidate's vote = Candidate's voting rate × Total votes
Guess what?
Form data at Nov. 5, 2020
Biden's vote = 121.6115 + 0.5629 × Total votes
R^2=0.8128
Trump's vote = -120.573 + 0.4171 × Total votes
R^2=0.7051
The constant term lies on the convincible interval far from 0.
My Linear Regression model indicates that Biden has stolen other candidates averagely 120 votes on each ward.
What a Coincidence!
That's all.
Here is my video concerning this Linear Regression Analysis if you're interested.
Possible leakage of this Linear Regression model
Suppose there are two different groups of votes (mail-in ballots and in-person ballots) with different voting rate


holds when 
The nature of mail-in ballots and in-person ballots possibly fluctrates the constant term.
Proof










holds when 
which implies the nature of independent variable remains unchanged.
Here are data sources from Milwaukee
11-3-20 General and Presidential Election - Unofficial Results
My Regression Model is
Candidate's vote = Candidate's voting rate × Total votes
which is no constant term expected
Form data at Nov. 4, 2020
Biden's vote = 5.3191 + 0.5821 × Total votes
R^2=0.9087
Trump's vote = -6.6928 + 0.4002 × Total votes
R^2=0.8255
No constant term is expected.
This constant term is possibly caused by Biden stealing other candidate's vote.
However, the constant term lies on the convincible interval involving 0.
Without constant term, my Linear Regression model at Nov. 4, 2020 becomes:
Biden's vote = 0.5877 × Total votes
R^2=0.9085
Trump's vote = 0.3931 × Total votes
R^2=0.8262
which is Candidate's vote = Candidate's voting rate × Total votes
Guess what?
Form data at Nov. 5, 2020
Biden's vote = 121.6115 + 0.5629 × Total votes
R^2=0.8128
Trump's vote = -120.573 + 0.4171 × Total votes
R^2=0.7051
The constant term lies on the convincible interval far from 0.
My Linear Regression model indicates that Biden has stolen other candidates averagely 120 votes on each ward.
What a Coincidence!
That's all.
Here is my video concerning this Linear Regression Analysis if you're interested.
Possible leakage of this Linear Regression model
Suppose there are two different groups of votes (mail-in ballots and in-person ballots) with different voting rate




The nature of mail-in ballots and in-person ballots possibly fluctrates the constant term.
Proof













which implies the nature of independent variable remains unchanged.
This post has been edited 3 times. Last edited by fungarwai, Feb 18, 2021, 12:40 AM
Subsequent factor of binomial coefficients
by fungarwai, Sep 20, 2020, 11:31 AM

Proof



Proof
![$\nu_p(n!)=\sum_{k=1}^\infty [\frac{n}{p^k}]$](http://latex.artofproblemsolving.com/5/a/e/5ae1aa004c1d4b8aa622a7b37cefb8abd149face.png)
![$\nu_p(m!(n+1-m)!)=\sum_{k=1}^\infty \left([\frac{m}{p^k}]+[\frac{n+1-m}{p^k}]\right)$](http://latex.artofproblemsolving.com/a/2/c/a2c5f3ec5d2ee7f749cec60496cab079b9e1be56.png)
![$p^k\mid m \Rightarrow p^k\nmid n+1-m \Rightarrow [\frac{n+1-m}{p^k}]=[\frac{n-m}{p^k}]$](http://latex.artofproblemsolving.com/0/f/1/0f1909e04f9bb95c3e8a07f20d138ac1d6997da3.png)
![$[\frac{m+n-m}{p^k}]\ge [\frac{m}{p^k}]+[\frac{n-m}{p^k}]$](http://latex.artofproblemsolving.com/5/d/b/5db58029d9bfbd1317b5b172e19ddfe39db2b681.png)
![$p^k\nmid m \Rightarrow [\frac{m}{p^k}]=[\frac{m-1}{p^k}]$](http://latex.artofproblemsolving.com/9/c/d/9cdfbd8c708a428f69ea6188976122989f4f9b6e.png)
![$[\frac{m-1+n+1-m}{p^k}]\ge [\frac{m-1}{p^k}]+[\frac{n+1-m}{p^k}]$](http://latex.artofproblemsolving.com/f/a/7/fa7e3452916f4c8666cdb6684165015927febe7e.png)

Example

Proof
![$\nu_p(n!)=\sum_{k=1}^\infty [\frac{n}{p^k}]$](http://latex.artofproblemsolving.com/5/a/e/5ae1aa004c1d4b8aa622a7b37cefb8abd149face.png)
![$\nu_p((m+1)!(n-m)!)=\sum_{k=1}^\infty \left([\frac{m+1}{p^k}]+[\frac{n-m}{p^k}]\right)$](http://latex.artofproblemsolving.com/4/0/9/40987c5781a36d4c105756171b526bb02730eab2.png)
![$p^k\mid m+1 \Rightarrow p^k\nmid n-m \Rightarrow [\frac{n-m}{p^k}]=[\frac{n-m-1}{p^k}]$](http://latex.artofproblemsolving.com/5/3/2/532f183719986fdd4db139c285c17c3467b9938e.png)
![$[\frac{m+1+n-m-1}{p^k}]\ge [\frac{m+1}{p^k}]+[\frac{n-m-1}{p^k}]$](http://latex.artofproblemsolving.com/5/3/e/53e67d7e6ff142a52aa37519a028245fe0dc44b9.png)
![$p^k\nmid m+1 \Rightarrow [\frac{m+1}{p^k}]=[\frac{m}{p^k}]$](http://latex.artofproblemsolving.com/2/5/4/2549c17560a5b9f7a7ed36416c8682d8465204a0.png)
![$[\frac{m+n-m}{p^k}]\ge [\frac{m}{p^k}]+[\frac{n-m}{p^k}]$](http://latex.artofproblemsolving.com/5/d/b/5db58029d9bfbd1317b5b172e19ddfe39db2b681.png)



Proof
![$\nu_p((n-1)!n!)=\sum_{k=1}^\infty
\left([\frac{n-1}{p^k}]+[\frac{n}{p^k}]\right)$](http://latex.artofproblemsolving.com/2/0/d/20d796a281d7b0dc5829d62189eac635a9cf536c.png)
![$\nu_p(a!(n-a)!b!(n-b)!)
=\sum_{k=1}^\infty \left([\frac{a}{p^k}]+[\frac{n-a}{p^k}]
+[\frac{b}{p^k}]+[\frac{n-b}{p^k}]\right)$](http://latex.artofproblemsolving.com/9/6/3/963e8f63ef2968e4842268b480f892060837bcd9.png)
![$p^k\mid a \Rightarrow p^k\nmid b
\Rightarrow [\frac{b}{p^k}]=[\frac{b-1}{p^k}]$](http://latex.artofproblemsolving.com/c/4/2/c423b38ff4a3d7df92b18376bd5a3f49817ae89e.png)
![$[\frac{a+n-a}{p^k}]+[\frac{b-1+n-b}{p^k}]
\ge [\frac{a}{p^k}]+[\frac{n-a}{p^k}]
+[\frac{b-1}{p^k}]+[\frac{n-b}{p^k}]$](http://latex.artofproblemsolving.com/4/2/1/421c930dc569fafbb740982451bb9d526fff1757.png)
![$p^k\nmid a \Rightarrow [\frac{a}{p^k}]=[\frac{a-1}{p^k}]$](http://latex.artofproblemsolving.com/d/6/d/d6d2e464bff1fe2373520348138de9100dc754f7.png)
![$[\frac{a-1+n-a}{p^k}]+[\frac{b+n-b}{p^k}]
\ge [\frac{a-1}{p^k}]+[\frac{n-a}{p^k}]
+[\frac{b}{p^k}]+[\frac{n-b}{p^k}]$](http://latex.artofproblemsolving.com/8/9/d/89d062aa04824896d3cbe6f5871677c7e98f58dd.png)

Example
This post has been edited 7 times. Last edited by fungarwai, Mar 20, 2021, 12:52 PM
The product of fraction with arithmetic sequence
by fungarwai, Sep 20, 2020, 2:38 AM
An inequality concerning limit of this product

Proof
Example
Concerning the limit
https://artofproblemsolving.com/community/c6h2275801_find_limit
![$\prod_{k=0}^n \frac{3k+1}{3k+2}<\sqrt[3]{\frac{1}{3n+4}}$](//latex.artofproblemsolving.com/c/5/7/c57baf0dc632fe81a716c0e193b3bf66e62d4787.png)
Concerning the limit
https://artofproblemsolving.com/community/u345311h2270603p17759776
An identity of this product

Proof
Example
Summation of this product

Proof
Example

Proof
Example

Concerning the limit

https://artofproblemsolving.com/community/c6h2275801_find_limit
![$\prod_{k=0}^n \frac{3k+1}{3k+2}<\sqrt[3]{\frac{1}{3n+4}}$](http://latex.artofproblemsolving.com/c/5/7/c57baf0dc632fe81a716c0e193b3bf66e62d4787.png)
Concerning the limit

https://artofproblemsolving.com/community/u345311h2270603p17759776
An identity of this product

Proof
Example
Wallis product

https://artofproblemsolving.com/community/c4h2565088_prod_limit_n0infty_frac5n25n35n15n4


https://artofproblemsolving.com/community/c4h2565088_prod_limit_n0infty_frac5n25n35n15n4

Summation of this product

Proof
Idea provided by RagvaloD on 2/3*6 + 2*5/3*6*9 + ... + 2*5*...*2015/3*6...*2019



By Hypergeometric function










By Hypergeometric function







Example
This post has been edited 7 times. Last edited by fungarwai, May 19, 2021, 6:07 AM
Summation with polynomial roots
by fungarwai, May 26, 2020, 12:52 PM
Reciprocal type

Credit to the idea posted by ccmmjj in mathchina forum
Proof

![$\sum_{i=1}^m \frac{-1}{(x-x_i)^2}=\frac{f''(x)f(x)-[f'(x)]^2}{[f(x)]^2}$](//latex.artofproblemsolving.com/a/b/3/ab3a6c2f444a2265b208b177fea06bfc3e7196d8.png)
![$\sum_{i=1}^m \frac{2}{(x-x_i)^3}=\frac{f'''(x)[f(x)]^2-3f''(x)f'(x)f(x)+2[f'(x)]^3}{[f(x)]^3}$](//latex.artofproblemsolving.com/9/d/a/9da9b44ce18202b3021555318f2c8ebe471836e7.png)
Identity of a conditional symmetric polynomial
Let


Proof
Example

Proof
Suppose
is true for 









Example



Lagrange polynomial type

Proof







Best Proof Credit to the idea with four variables posted by natmath at #2
Proof Credit to the idea with three variables posted by gasgous at #10
Other Proof

where




Proof
Example

Credit to the idea posted by ccmmjj in mathchina forum
Proof


![$\sum_{i=1}^m \frac{-1}{(x-x_i)^2}=\frac{f''(x)f(x)-[f'(x)]^2}{[f(x)]^2}$](http://latex.artofproblemsolving.com/a/b/3/ab3a6c2f444a2265b208b177fea06bfc3e7196d8.png)
![$\sum_{i=1}^m \frac{2}{(x-x_i)^3}=\frac{f'''(x)[f(x)]^2-3f''(x)f'(x)f(x)+2[f'(x)]^3}{[f(x)]^3}$](http://latex.artofproblemsolving.com/9/d/a/9da9b44ce18202b3021555318f2c8ebe471836e7.png)
Identity of a conditional symmetric polynomial
Let



Proof
Distribute
balls into
boxes
Each box
has
balls
Let
be the event of box
contains at least one ball
By Inclusion–exclusion principle

satisfies for the number of any combinations of
, therefore




Each box


Let


By Inclusion–exclusion principle

satisfies for the number of any combinations of



Example
For the combination
as example





which is the same as the situation of the coefficient of

Other examples








which is the same as the situation of the coefficient of


Other examples



Proof

Suppose











Example




Lagrange polynomial type

Proof








Best Proof Credit to the idea with four variables posted by natmath at #2
Proof Credit to the idea with three variables posted by gasgous at #10
Other Proof
Let 
such that

where
The coefficient of
should be 0
i.e.![$[x^k]P(x)=0,~\forall m\le k\le n$](//latex.artofproblemsolving.com/e/e/c/eec149e97f1674238203b8de81e4b91781a0214a.png)
And then,![$[x^{m-1}]P(x)=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}$](//latex.artofproblemsolving.com/9/3/3/933e37fd232bc27983ac056623d279f3460a8f12.png)
Let
![$\begin{cases}
[x^n]P(x)=1-1=0\\
[x^{n-1}]P(x)=-\left(q_1-\sigma_{1,m}\right)=0\\
[x^{n-2}]P(x)=-\left(q_2-\sigma_{1,m} q_1+(-1)^{K_2}\sigma_{K_2,m}\right)=0\\
\vdots\\
\displaystyle [x^m]P(x)=-\left(q_{n-m}+\sum_{k=1}^{K_{n-m}-1} (-1)^k \sigma_{k,m} q_{n-m-k}+(-1)^{K_{n-m}}\sigma_{K_{n-m},m}\right)=0\\
\displaystyle [x^{m-1}]P(x)=-\left(\sum_{k=1}^{K_{n-m+1}-1} (-1)^k \sigma_{k,m} q_{n-m+1-k}+(-1)^{K_{n-m+1}}\sigma_{K_{n-m+1},m}\right)\end{cases}$](//latex.artofproblemsolving.com/e/5/f/e5f9aa5011209a8abcb849c61cae2067a13303b9.png)
As


![$[x^{m-1}]P(x)=-\left(-S_{n-m+1,m}\right)=S_{n-m+1,m}$](//latex.artofproblemsolving.com/5/4/9/549b85f0b17c81e85eb9826d6fa829e68d66ec4f.png)
Credit to the proof posted by natmath at #4

such that


where

The coefficient of

i.e.
![$[x^k]P(x)=0,~\forall m\le k\le n$](http://latex.artofproblemsolving.com/e/e/c/eec149e97f1674238203b8de81e4b91781a0214a.png)
And then,
![$[x^{m-1}]P(x)=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}$](http://latex.artofproblemsolving.com/9/3/3/933e37fd232bc27983ac056623d279f3460a8f12.png)
Let

![$\begin{cases}
[x^n]P(x)=1-1=0\\
[x^{n-1}]P(x)=-\left(q_1-\sigma_{1,m}\right)=0\\
[x^{n-2}]P(x)=-\left(q_2-\sigma_{1,m} q_1+(-1)^{K_2}\sigma_{K_2,m}\right)=0\\
\vdots\\
\displaystyle [x^m]P(x)=-\left(q_{n-m}+\sum_{k=1}^{K_{n-m}-1} (-1)^k \sigma_{k,m} q_{n-m-k}+(-1)^{K_{n-m}}\sigma_{K_{n-m},m}\right)=0\\
\displaystyle [x^{m-1}]P(x)=-\left(\sum_{k=1}^{K_{n-m+1}-1} (-1)^k \sigma_{k,m} q_{n-m+1-k}+(-1)^{K_{n-m+1}}\sigma_{K_{n-m+1},m}\right)\end{cases}$](http://latex.artofproblemsolving.com/e/5/f/e5f9aa5011209a8abcb849c61cae2067a13303b9.png)
As



![$[x^{m-1}]P(x)=-\left(-S_{n-m+1,m}\right)=S_{n-m+1,m}$](http://latex.artofproblemsolving.com/5/4/9/549b85f0b17c81e85eb9826d6fa829e68d66ec4f.png)
Credit to the proof posted by natmath at #4
https://artofproblemsolving.com/community/c4h2901132
Consider the polynomial
The desired expression is the coefficient of
of
. We know that
(and cyclically) so
But
is a quadratic so the coefficient of
and
should be
. This means that
So
The coefficient of
is
.
Consider the polynomial














where





Proof
When
,

When
,
Suppose










When

Suppose









Example
This post has been edited 23 times. Last edited by fungarwai, May 19, 2023, 12:07 PM
Chromatic polynomial of a 3×n grid
by fungarwai, Apr 26, 2020, 1:26 AM
Denote Chromatic polynomial of a m×n grid as 
Chromatic polynomial of a 2×n grid has been found and named as ladder graph

My recurrence equation found for Chromatic polynomial of a 3×n grid is as follow





![[asy]
unitsize(5mm);
int i, j, k;
k=0;
for(i=0; i<k+7; i=i+1){
if(i!=2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((0,j)--(k+6,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+7; i=i+1){
if(i!=10){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((k,j)--(k+5,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
dot((k+6,0.5));dot((k+6,1.5));
draw((k+5,0)--(k+6,0.5));
draw((k+5,1)--(k+6,0.5));
draw((k+5,1)--(k+6,1.5));
draw((k+5,2)--(k+6,1.5));
[/asy]](//latex.artofproblemsolving.com/c/c/a/ccad5fb03d2ced72204eb38d6229c6a87af277d3.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
draw((k+6,1)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,1));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (23,1));
k=24;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (31,1));
k=32;
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((k,j)--(k+5,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
dot((k+6,0.5));dot((k+6,1.5));
draw((k+5,0)--(k+6,0.5));
draw((k+5,1)--(k+6,0.5));
draw((k+5,1)--(k+6,1.5));
draw((k+5,2)--(k+6,1.5));
[/asy]](//latex.artofproblemsolving.com/0/0/8/008cd57e022024e061740eba373c9f5fdc60a831.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=[(t-1)^3-(t-2)^2]$", (17,1));
k=22;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (28,1));
k=29;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/5/8/d/58dff26c2b4e23d5dde2a97708f9204f946a1c00.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=(t^3-4t^2+7t-5)$", (17,1));
k=22;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (28,1));
k=29;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/a/3/a/a3a8c515b7c76985dca0801af3ee0ced2fe0d097.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,2)--(k+6,0));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/e/4/1/e4130b105f551a3b95bbc3e78b9e3c0523bb3555.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-7,1));label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (23,1));
k=24;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/8/4/1/841a9f991afce666e147b88b6bbc1fd04f2d5dce.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-14,1));label("$=[(t-1)^2-(t-1)]$", (3,1));
k=8;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (15,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/7/1/4/714494d58ee3a803a519415729713ffdc37b7f69.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-11,1));label("$=(t-1)(t-2)$", (3,1));
k=7;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (14,1));
k=15;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/f/3/f/f3f83503229bcc11d071aa08134eef47bd57746b.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
for(i=0; i<k+7; i=i+1){
if(i!=2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((0,j)--(k+6,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=[(t-1)^3-(t-2)^2]$", (11,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (22,1));
k=23;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/5/5/0/5506ed426381e3eb388ecc348f6b53f3c8da3490.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-10,1));label("$=[(t-1)^3-(t-2)^2-(t-1)^2+(t-1)]$", (11,1));
k=20;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (26,1));
k=27;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/7/3/3/733697e2a3a467e510d7879f3055f05c795c1a85.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=(t^3-5t^2+10t-7)$", (11,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (22,1));
k=23;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/3/4/9/349dd217f185ae317a81907e981089971471f2a0.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+4,0));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));
draw((k+4,2)--(k+6,1));
draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/a/8/f/a8f5fc3cfe6ba188709f0e8b2630944bd06b866d.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/5/1/7/51704fbb6319701529de22e8f81ce492a41c9cd3.png)
![[asy]
unitsize(5mm);int i, j, k;
label("$=$", (7,1));
k=8;draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k+4,2)--(k+5,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+6,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (23,1));
k=24;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,2)--(k+6,1));draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$+$", (31,1));
k=32;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/4/9/3/493ee1edd4e4c9d449607a55c576b9d0b14833d3.png)
![[asy]
unitsize(5mm);int i, j, k;
label("$=$", (7,1));
k=8;draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k+4,2)--(k+5,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+6,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}dot((k+5,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));label("$-$", (23,1));
k=24;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){if(i!=k+2){dot((i,j));}}}
dot((k+6,1));label("...", (k+2,0.5));label("...", (k+2,1.5));label("$+$", (31,1));
k=32;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$+$", (39,1));
k=40;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/b/d/4/bd4ce072118f581f5d3d6dc4885be0787e07f5e4.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-14,1));label("$=[(t-1)^2-(t-1)+1]$", (3,1));
k=8;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-(t-2)$", (14,1));
k=16;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/b/a/5/ba5910812cd1e515e16525ab2fcc921a17a0bd8a.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-10,1));label("$=(t^2-3t+3)$", (3,1));
k=6;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-(t-2)$", (12,1));
k=14;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](//latex.artofproblemsolving.com/0/0/b/00b8214c224cb9ec778201a5d00b3566d09184f9.png)




![$(t^3-5t^2+10t-7)a_n-a_{n+1}=a_n-(t^2-3t+3)a_{n-1}+(t-2)[(t^3-5t^2+10t-7)a_{n-1}-a_n]$](//latex.artofproblemsolving.com/1/3/6/136a5617117c972b269369c99a2286c2caeac6b1.png)

![[asy]
unitsize(5mm);int i, j, k;
label("$a_1:$", (0,1));
k=2;
for(i=k; i<k+1; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){dot((i,j));}}
label("$a_2:$", (5,1));
k=7;
for(i=k; i<k+2; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){
draw((k,j)--(k+1,j));
dot((i,j));}}
label("$a_3:$", (11,1));
k=13;
for(i=k; i<k+3; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){
draw((k,j)--(k+2,j));
dot((i,j));}}
[/asy]](//latex.artofproblemsolving.com/f/3/6/f369465809f70343e7a3bc7e9f094de0c6a5da6a.png)




Chromatic polynomial of a 2×n grid has been found and named as ladder graph

My recurrence equation found for Chromatic polynomial of a 3×n grid is as follow





![[asy]
unitsize(5mm);
int i, j, k;
k=0;
for(i=0; i<k+7; i=i+1){
if(i!=2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((0,j)--(k+6,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+7; i=i+1){
if(i!=10){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((k,j)--(k+5,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
dot((k+6,0.5));dot((k+6,1.5));
draw((k+5,0)--(k+6,0.5));
draw((k+5,1)--(k+6,0.5));
draw((k+5,1)--(k+6,1.5));
draw((k+5,2)--(k+6,1.5));
[/asy]](http://latex.artofproblemsolving.com/c/c/a/ccad5fb03d2ced72204eb38d6229c6a87af277d3.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
draw((k+6,1)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,1));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (23,1));
k=24;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (31,1));
k=32;
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((k,j)--(k+5,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
dot((k+6,0.5));dot((k+6,1.5));
draw((k+5,0)--(k+6,0.5));
draw((k+5,1)--(k+6,0.5));
draw((k+5,1)--(k+6,1.5));
draw((k+5,2)--(k+6,1.5));
[/asy]](http://latex.artofproblemsolving.com/0/0/8/008cd57e022024e061740eba373c9f5fdc60a831.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=[(t-1)^3-(t-2)^2]$", (17,1));
k=22;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (28,1));
k=29;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/5/8/d/58dff26c2b4e23d5dde2a97708f9204f946a1c00.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=(t^3-4t^2+7t-5)$", (17,1));
k=22;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (28,1));
k=29;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/a/3/a/a3a8c515b7c76985dca0801af3ee0ced2fe0d097.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,2)--(k+6,0));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/e/4/1/e4130b105f551a3b95bbc3e78b9e3c0523bb3555.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-7,1));label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (23,1));
k=24;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/8/4/1/841a9f991afce666e147b88b6bbc1fd04f2d5dce.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-14,1));label("$=[(t-1)^2-(t-1)]$", (3,1));
k=8;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (15,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/7/1/4/714494d58ee3a803a519415729713ffdc37b7f69.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-11,1));label("$=(t-1)(t-2)$", (3,1));
k=7;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (14,1));
k=15;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/f/3/f/f3f83503229bcc11d071aa08134eef47bd57746b.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
for(i=0; i<k+7; i=i+1){
if(i!=2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((0,j)--(k+6,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=[(t-1)^3-(t-2)^2]$", (11,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (22,1));
k=23;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/5/5/0/5506ed426381e3eb388ecc348f6b53f3c8da3490.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-10,1));label("$=[(t-1)^3-(t-2)^2-(t-1)^2+(t-1)]$", (11,1));
k=20;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (26,1));
k=27;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/7/3/3/733697e2a3a467e510d7879f3055f05c795c1a85.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=(t^3-5t^2+10t-7)$", (11,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (22,1));
k=23;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/3/4/9/349dd217f185ae317a81907e981089971471f2a0.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+4,0));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));
draw((k+4,2)--(k+6,1));
draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/a/8/f/a8f5fc3cfe6ba188709f0e8b2630944bd06b866d.png)
![[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/5/1/7/51704fbb6319701529de22e8f81ce492a41c9cd3.png)
![[asy]
unitsize(5mm);int i, j, k;
label("$=$", (7,1));
k=8;draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k+4,2)--(k+5,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+6,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (23,1));
k=24;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,2)--(k+6,1));draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$+$", (31,1));
k=32;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/4/9/3/493ee1edd4e4c9d449607a55c576b9d0b14833d3.png)
![[asy]
unitsize(5mm);int i, j, k;
label("$=$", (7,1));
k=8;draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k+4,2)--(k+5,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+6,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}dot((k+5,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));label("$-$", (23,1));
k=24;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){if(i!=k+2){dot((i,j));}}}
dot((k+6,1));label("...", (k+2,0.5));label("...", (k+2,1.5));label("$+$", (31,1));
k=32;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$+$", (39,1));
k=40;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/b/d/4/bd4ce072118f581f5d3d6dc4885be0787e07f5e4.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-14,1));label("$=[(t-1)^2-(t-1)+1]$", (3,1));
k=8;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-(t-2)$", (14,1));
k=16;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/b/a/5/ba5910812cd1e515e16525ab2fcc921a17a0bd8a.png)
![[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-10,1));label("$=(t^2-3t+3)$", (3,1));
k=6;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-(t-2)$", (12,1));
k=14;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]](http://latex.artofproblemsolving.com/0/0/b/00b8214c224cb9ec778201a5d00b3566d09184f9.png)




![$(t^3-5t^2+10t-7)a_n-a_{n+1}=a_n-(t^2-3t+3)a_{n-1}+(t-2)[(t^3-5t^2+10t-7)a_{n-1}-a_n]$](http://latex.artofproblemsolving.com/1/3/6/136a5617117c972b269369c99a2286c2caeac6b1.png)

![[asy]
unitsize(5mm);int i, j, k;
label("$a_1:$", (0,1));
k=2;
for(i=k; i<k+1; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){dot((i,j));}}
label("$a_2:$", (5,1));
k=7;
for(i=k; i<k+2; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){
draw((k,j)--(k+1,j));
dot((i,j));}}
label("$a_3:$", (11,1));
k=13;
for(i=k; i<k+3; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){
draw((k,j)--(k+2,j));
dot((i,j));}}
[/asy]](http://latex.artofproblemsolving.com/f/3/6/f369465809f70343e7a3bc7e9f094de0c6a5da6a.png)



This post has been edited 17 times. Last edited by fungarwai, Aug 27, 2021, 12:50 PM
The module distribution for Pascal's triangle row
by fungarwai, Sep 13, 2019, 12:14 PM
Let 
For p=2,
There are
different ways to choose
for 
For p=3,
There are
different ways to choose
for
and
different ways to choose
for 
Proof



Let

There are
different ways to choose
for 
Consider the sum of coefficient of the odd power of generating function
There are
different ways to choose
for
and
different ways to choose
for 
Multiplying the result
There are
different ways to choose
for
and
different ways to choose
for 
For p=5,
The number of
is 
The number of
is 
The number of
is 
The number of
is 
Proof
Consider generating functions

1
: 
2
: 
4
: 
3
: 

1
: 
3
: 
4
: 
2
: 
Here define
when
to maintain the equivalent

1
: 
4
: 
Combining the results
The number of
is 
The number of
is 
The number of
is 
The number of
is 
Example
The number of
is 
The number of
is 
The number of
is 
The number of
is 

The number of
is 
The number of
is 
The number of
is 
The number of
is 

The number of
is 
The number of
is 
The number of
is 
The number of
is 

For p=2,
There are



For p=3,
There are






Proof




Let


There are



Consider the sum of coefficient of the odd power of generating function

There are






Multiplying the result
There are






For p=5,
The number of


The number of


The number of


The number of


Proof

Consider generating functions


1


2


4


3



1


3


4


2


Here define



1


4


Combining the results
The number of


The number of


The number of


The number of


Example

The number of


The number of


The number of


The number of



The number of


The number of


The number of


The number of



The number of


The number of


The number of


The number of


This post has been edited 1 time. Last edited by fungarwai, Sep 13, 2019, 12:15 PM
Archives









Shouts
Submit
20 shouts
Tags
About Owner
- Posts: 863
- Joined: Mar 11, 2017
Blog Stats
- Blog created: Sep 15, 2018
- Total entries: 18
- Total visits: 6389
- Total comments: 8
Search Blog