# Dominating Sets and Domination Polynomials of Paths

Authors: Saeid Alikhani; Yee-Hock Peng
Journal: International Journal of Mathematics and Mathematical Sciences
 (2009)

---

## Abstract

LetG=(V,E) be a simple graph. A set S⊆V is a dominating set of G, if every vertex in V\S is adjacent to at least one vertex in S. Let 𝒫ni be the family of all dominating sets of a path Pn with cardinality i, and let d(Pn,j)=|𝒫nj|. In this paper, we construct 𝒫ni, and obtain a recursive formula for d(Pn,i). Using this recursive formula, we consider the polynomial D(Pn,x)=∑i=⌈n/3⌉nd(Pn,i)xi, which we call domination polynomial of paths and obtain some properties of this polynomial.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple
graph of order |V|=n. For any vertex v∈V, the open neighborhood of v is the set N(v)={u∈V∣uv∈E} and the closed
neighborhood of v is the set N[v]=N(v)∪{v}. For a set S⊆V, the open neighborhood of S is N(S)=∪v∈SN(v) and the closed
neighborhood of S is N[S]=N(S)∪S. A set S⊆V is a dominating
set of G, if N[S]=V, or equivalently, every vertex in V\S is adjacent to
at least one vertex in S. The domination number γ(G) is the minimum
cardinality of a dominating set in G. A dominating set with cardinality γ(G) is called a γ-set, and the
family of γ-sets is
denoted by Γ(G). For a detailed treatment of this parameter, the
reader is referred to [1]. It is well known and generally accepted that the
problemof determining the dominating sets of an arbitrary graph is a difficult
one (see [2]). A path
is a connected graph in which two vertices have degree 1 and the remaining
vertices have degree 2. Let Pn be the path
with n vertices. Let 𝒫ni be the family of dominating
sets of a path Pn with
cardinality i and let d(Pn,i)=|𝒫ni|. We call the polynomial D(Pn,x)=∑i=⌈n/3⌉nd(Pn,i)xi, the domination polynomial of
the path Pn. For a detailed treatment of the domination
polynomial of a graph, the reader is referred to [3].In the next section we construct the families of the
dominating sets of paths by a recursive method. In Section3, we use the results obtained in Section 2 to study the domination polynomial of paths.As usual we use⌈x⌉, for the smallest integer
greater than or equal to x. In this article we denote the set {1,2,…,n} simply by [n].


## 2. Dominating Sets of Paths

Let𝒫ni be the family of dominating
sets of Pn with
cardinality i. We will investigate dominating sets of path. We
need the following lemmas to prove our main results in this article.Lemma 2.1 (see [4, page 371]).
γ(Pn)=⌈n/3⌉.By Lemma2.1 and the definition of domination number, one has the following lemma.Lemma 2.2.
𝒫ji=∅, if and only if i>j or i<⌈j/3⌉.Asimple
path is a path in which all its internal vertices have degree two. The
following lemma follows from observation.Lemma 2.3.
If a graphG contains a
simple path of length 3k−1, then every dominating set of G must contain
at least k vertices of the path.To find a dominating set ofPn with
cardinality i, we do not need to consider dominating sets of Pn−4 with
cardinality i−1. We show this in Lemma 2.4. Therefore, we only need to consider 𝒫n−1i−1,𝒫n−2i−1, and 𝒫n−3i−1. The families of these
dominating sets can be empty or otherwise. Thus, we have eight combinations of
whether these three families are empty or not. Two of these combinations are
not possible (see Lemma 2.5(i) and (ii)). Also, the
combination that 𝒫n−1i−1=𝒫n−2i−1=𝒫n−3i−1=∅ does not need to be
considered because it implies 𝒫ni=∅ (see Lemma 2.5(iii)). Thus we only
need to consider five combinations or cases. We consider these cases in Theorem 	2.7.Lemma 2.4.
IfY∈𝒫n−4i−1, and there exists x∈[n] such that Y∪{x}∈𝒫ni, then Y∈𝒫n−3i−1.Proof.
Suppose thatY∉𝒫n−3i−1. Since Y∈𝒫n−4i−1, Y contains at
least one vertex labeled n−5 or n−4. If n−4∈Y, then Y∈𝒫n−3i−1, a contradiction. Hence, n−5∈Y, but then in this case, Y∪{x}∉𝒫ni, for any x∈[n], also a contradiction.Lemma 2.5.
(i) If𝒫n−1i−1=𝒫n−3i−1=∅, then 𝒫n−2i−1=∅.
(ii) If𝒫n−1i−1≠∅ and 𝒫n−3i−1≠∅, then 𝒫n−2i−1≠∅.
(iii) If𝒫n−1i−1=𝒫n−2i−1=𝒫n−3i−1=∅, then 𝒫ni=∅.Proof.
(i) Since𝒫n−1i−1=𝒫n−3i−1=∅, by Lemma 2.2, i−1>n−1 or i−1<⌈(n−3)/3⌉. In either case we have 𝒫n−2i−1=∅.
(ii) Suppose that𝒫n−2i−1=∅, so by Lemma 2.2, we have i−1>n−2 or i−1<⌈(n−2)/3⌉. If i−1>n−2, then i−1>n−3, and hence, 𝒫n−3i−1=∅, a contradiction. Hence i−1<⌈(n−2)/3⌉. So i−1<⌈(n−1)/3⌉, and hence, 𝒫n−1i−1=∅, also a contradiction.
(iii)
Suppose that𝒫ni≠∅. Let Y∈𝒫ni. Then at least one vertex
labeled n or n−1 is in Y. If n∈Y, then by Lemma 2.3, at least one vertex labeled n−1,n−2 or n−3 is in Y. If n−1∈Y or n−2∈Y, then Y−{n}∈𝒫n−1i−1, a contradiction. If n−3∈Y, then Y−{n}∈𝒫n−2i−1, a contradiction. Now suppose
that n−1∈Y. Then by Lemma 2.3, at least one vertex labeled n−2,n−3 or n−4 is in Y. If n−2∈Y or n−3∈Y, then Y−{n−1}∈𝒫n−2i−1, a contradiction. If n−4∈Y, then Y−{n−1}∈𝒫n−3i−1, a contradiction. Therefore 𝒫ni=∅.Lemma 2.6.
If𝒫ni≠∅, then(i)
𝒫n−1i−1=𝒫n−2i−1=∅, and 𝒫n−3i−1≠∅ if and only if n=3k and i=k for some k∈ℕ;(ii)
𝒫n−2i−1=𝒫n−3i−1=∅ and 𝒫n−1i−1≠∅ if and only if i=n;(iii)
𝒫n−1i−1=∅,𝒫n−2i−1≠∅ and 𝒫n−3i−1≠∅ if and only if n=3k+2 and i=⌈(3k+2)/3⌉ for some k∈ℕ;(iv)
𝒫n−1i−1≠∅,𝒫n−2i−1≠∅ and 𝒫n−3i−1=∅ if and only if i=n−1;(v)
𝒫n−1i−1≠∅,𝒫n−2i−1≠∅ and 𝒫n−3i−1≠∅ if and only if ⌈(n−1)/3⌉+1≤i≤n−2.Proof.
(i) (⇒) Since 𝒫n−1i−1=𝒫n−2i−1=∅, by Lemma 2.2, i−1>n−1 or i−1<⌈(n−2)/3⌉. If i−1>n−1, then i>n, and by Lemma 2.2, 𝒫ni=∅, a contradiction. So i<⌈(n−2)/3⌉+1, and since 𝒫ni≠∅, together ⌈n/3⌉≤i<⌈(n−2)/3⌉+1, which give us n=3k and i=k for some k∈ℕ.
(⇐) If n=3k and i=k for some k∈ℕ, then by Lemma 2.2, 𝒫n−1i−1=𝒫n−2i−1=∅, and 𝒫n−3i−1≠∅.
(ii)
(⇒) Since 𝒫n−2i−1=𝒫n−3i−1=∅, by Lemma 2.2, i−1>n−2 or i−1<⌈(n−3)/3⌉. If i−1<⌈(n−3)/3⌉, then i−1<⌈(n−1)/3⌉, and hence 𝒫n−1i−1=∅, a contradiction. So i>n−1. Also since 𝒫n−1i−1≠∅, i−1≤n−1. Therefore i=n.
(⇐) If i=n, then by Lemma 2.2, 𝒫n−2i−1=𝒫n−3i−1=∅ and 𝒫n−1i−1≠∅.(iii)
(⇒) Since 𝒫n−1i−1=∅, by Lemma 2.2, i−1>n−1 or i−1<⌈(n−1)/3⌉. If i−1>n−1, then i−1>n−2 and by Lemma 2.2, 𝒫n−2i−1=𝒫n−3i−1=∅, a contradiction. So i<⌈(n−1)/3⌉+1, but i−1≥⌈(n−2)/3⌉ because 𝒫n−2i−1≠∅. Hence, ⌈(n−2)/3⌉+1≤i<⌈(n−1)/3⌉+1. Therefore n=3k+2 and i=k+1=⌈(3k+2)/3⌉ for some k∈ℕ.
(⇐) If n=3k+2 and i=⌈(3k+2)/3⌉ for some k∈ℕ, then by Lemma 2.2, 𝒫n−1i−1=𝒫3k+1k=∅, 𝒫n−2i−1≠∅, and 𝒫n−3i−1≠∅.(iv)
(⇒) Since 𝒫n−3i−1=∅, by Lemma 2.2, i−1>n−3 or i−1<⌈(n−3)/3⌉. Since 𝒫n−2i−1≠∅, by Lemma 2.2, ⌈(n−2)/3⌉+1≤i≤n−1. Therefore i−1<⌈(n−3)/3⌉ is not possible. Hence i−1>n−3. Thus i=n−1 or n, but i≠n because 𝒫n−3i−1=∅. So i=n−1.
(⇐) If i=n−1, then by Lemma 2.2, 𝒫n−1i−1≠∅, 𝒫n−2i−1≠∅, and 𝒫n−3i−1=∅.(v)
(⇒) Since 𝒫n−1i−1≠∅,𝒫n−2i−1≠∅, and 𝒫n−3i−1≠∅, then by applying Lemma 2.2, ⌈(n−1)/3⌉≤i−1≤n−1,⌈(n−2)/3⌉≤i−1≤n−2, and ⌈(n−3)/3⌉≤i−1≤n−3. So ⌈(n−1)/3⌉≤i−1≤n−3 and
hence ⌈(n−1)/3⌉+1≤i≤n−2.
(⇐) If ⌈(n−1)/3⌉+1≤i≤n−2,thenthe result follows
from Lemma 2.2.By Lemma2.4, for the construction of 𝒫ni, it's sufficient to consider 𝒫n−1i−1,𝒫n−2i−1, and 𝒫n−3i−1. By Lemma 2.5, we need only to
consider the following five cases.Theorem 2.7.
For everyn≥4 and i≥⌈n/3⌉.(i)
If𝒫n−1i−1=𝒫n−2i−1=∅ and 𝒫n−3i−1≠∅, then 𝒫ni={{2,5,…,n−4,n−1}}.(ii)
If𝒫n−2i−1=𝒫n−3i−1=∅, and 𝒫n−1i−1≠∅, then 𝒫ni={[n]}.(iii)
If𝒫n−1i−1=∅,𝒫n−2i−1≠∅ and 𝒫n−3i−1≠∅, then (2.1)𝒫ni={{2,5,…,n−3,n}}∪{X∪{n−1}∣X∈𝒫n−3i−1}.(iv)
If𝒫n−3i−1=∅,𝒫n−2i−1≠∅ and 𝒫n−1i−1≠∅, then 𝒫ni={[n]−{x}∣x∈[n]}.(v)
If𝒫n−1i−1≠∅,𝒫n−2i−1≠∅ and 𝒫n−3i−1≠∅, then (2.2)𝒫ni={{n}∪X1,{n−1}∪X2∣X1∈𝒫n−1i−1,X2∈𝒫n−2i−1}∪{{n−1}∪X∣X∈𝒫n−3i−1∖𝒫n−2i−1}∪{{n}∪X∣X∈𝒫n−3i−1∩𝒫n−2i−1}.Proof.
(i)𝒫n−1i−1=𝒫n−2i−1=∅, and 𝒫n−3i−1≠∅. By Lemma 2.6(i), n=3k and i=k for some k∈ℕ. Therefore 𝒫ni=𝒫nn/3={{2,5,…,n−4,n−1}}.
(ii)
𝒫n−2i−1=𝒫n−3i−1=∅, and 𝒫n−1i−1≠∅. By Lemma 2.6(ii), we have i=n. So 𝒫ni=𝒫nn={[n]}.(iii)
𝒫n−1i−1=∅,𝒫n−2i−1≠∅ and 𝒫n−3i−1≠∅. By Lemma 2.6(iii), n=3k+2 and i=⌈(3k+2)/3⌉=k+1 for some k∈ℕ. Since X={2,5,…,3k−1}∈𝒫3kk, X∪{3k+2}∈𝒫3k+2k+1. Also, if X∈𝒫3k−1k, then X∪{3k+1}∈𝒫3k+2k+1. Therefore we
have(2.3){{2,5,…,3k−1,3k+2}}∪{X∪{3k+1}∣X∈𝒫3k−1k}⊆𝒫3k+2k+1. Now let Y∈𝒫3k+2k+1. Then 3k+2 or 3k+1 is in Y. If 3k+2∈Y, then by Lemma 3, at least one vertex labeled 3k+1,3k or 3k−1 is in Y. If 3k+1 or 3k is in Y, then Y−{3k+2}∈𝒫3k+1k, a contradiction because 𝒫3k+1k=∅. Hence, 3k−1∈Y,3k∉Y, and 3k+1∉Y. Therefore Y=X∪{3k+2} for some X∈𝒫3kk, that is Y={2,5,…,3k−1,3k+2}. Now suppose that 3k+1∈Y and 3k+2∉Y. By Lemma 2.3, at least one vertex labeled 3k,3k−1, or 3k−2 is in Y. If 3k∈Y, then Y−{3k+1}∈𝒫3kk={{2,5,…,3k−1}}, a contradiction because 3k∉X for all X∈𝒫3kk. Therefore 3k−1 or 3k−2 is in Y, but 3k∉Y. Thus Y=X∪{3k+1} for some X∈𝒫3k−1k. So (2.4)𝒫3k+2k+1⊆{{2,5,…,3k−1,3k+2}}∪{{3k+1}∪X∣X∈𝒫3k−1k}.(iv)
𝒫n−3i−1=∅, 𝒫n−1i−1≠∅, and 𝒫n−2i−1≠∅. By Lemma 2.6(iv), i=n−1. Therefore 𝒫ni=𝒫nn−1={[n]−{x}∣x∈[n]}.(v)
𝒫n−1i−1≠∅,𝒫n−2i−1≠∅, and 𝒫n−3i−1≠∅. Let X1∈𝒫n−1i−1, so at least one vertex
labeled n−1 or n−2 is in X1. If n−1 or n−2∈X1, then X1∪{n}∈𝒫ni.
LetX2∈𝒫n−2i−1, then n−2 or n−3 is in X2. If n−2 or n−3∈X2, then X2∪{n−1}∈𝒫ni.
Now letX3∈𝒫n−3i−1, then n−3 or n−4 is in X3. If n−3∈X3, then X3∪{x}∈𝒫ni, for x∈{n,n−1}. If n−4∈X3, then X3∪{n−1}∈𝒫ni. Therefore we have(2.5){{n}∪X1,{n−1}∪X2∣X1∈𝒫n−1i−1,X2∈𝒫n−2i−1}∪{{n−1}∪X∣X∈𝒫n−3i−1∖𝒫n−2i−1}∪{{n}∪X∣X∈𝒫n−3i−1∩𝒫n−2i−1}⊆𝒫ni. Now, let Y∈𝒫ni, then n∈Y or n−1∈Y. If n∈Y, then by Lemma 2.3, at least one vertex labeled n−1,n−2, or n−3 is in Y. If n−1∈Y or n−2∈Y, then Y=X∪{n} for some X∈𝒫n−1i−1. If n−3∈Y,n−2∉Y, and n−1∉Y, then Y=X∪{n} for some X∈𝒫i−1n−2∩𝒫i−1n−3. Now suppose that n−1∈Y and n∉Y, then by Lemma 3, at least one vertex labeled n−2,n−3 or n−4 is in Y. If n−2∈Y or n−3∈Y, then Y=X∪{n−1} for some X∈𝒫n−2i−1. If n−4∈Y,n−3∉Y and n−2∉Y, then Y=X∪{n−1} for some X∈𝒫n−3i−1∖𝒫n−2i−1. So(2.6)𝒫ni⊆{{n}∪X1,{n−1}∪X2∣X1∈𝒫n−1i−1,X2∈𝒫n−2i−1}∪{{n−1}∪X∣X∈𝒫n−3i−1∖𝒫n−2i−1}∪{{n}∪X∣X∈𝒫n−3i−1∩𝒫n−2i−1}.Example 2.8.
ConsiderP6 with V(P6)=[6]. We use Theorem 2.7
to construct 𝒫6i for 2≤i≤6. Since 𝒫51=𝒫41=∅ and 𝒫31={{2}}, by Theorem 2.7, 𝒫62={{2,5}}.
Since𝒫55={[5]},𝒫45=∅, and 𝒫35=∅, we get 𝒫66={[6]}.
Since𝒫54={{1,2,3,4},{1,2,3,5},{1,3,4,5},{2,3,4,5},{1,2,4,5}}, 𝒫44={[4]}, and 𝒫34=∅, then by Theorem
2.7,(2.7)𝒫65={[6]−{x}∣x∈[6]}={{1,2,3,4,6},{1,2,3,5,6},{1,3,4,5,6},{2,3,4,5,6},{1,2,4,5,6},{1,2,3,4,5}},and, for the construction of 𝒫63, by Theorem 2.7,(2.8)𝒫63={X1∪{6},X2∪{5}∣X1∈𝒫52,X2∈𝒫42}∪{{1,2}∪{5},{1,3}∪{6},{2,3}∪{6}}={{1,3,5},{1,3,6},{2,3,6},{2,3,5},{1,4,6},{1,4,5},{2,5,6},{2,4,6},{2,4,5},{1,2,5}}.Finally, since 𝒫53={{1,3,5},{1,2,4},{2,4,5},{2,3,4},{2,3,5},{1,4,5},{1,3,4},{1,2,5}}, 𝒫43={{1,2,3},{1,2,4},{2,3,4},{1,3,4}}, and 𝒫33={[3]}, then(2.9)𝒫64={X1∪{6},X2∪{5}∣X1∈𝒫53,X2∈𝒫43}∪{X∪{6}∣X∈𝒫33}={{1,2,3,5},{1,2,3,6},{1,2,4,6},{1,3,5,6},{1,3,4,6},{1,3,4,5},{1,2,5,6},{1,2,4,5},{2,3,4,6},{1,4,5,6},{2,3,4,5},{2,4,5,6},{2,3,5,6}}.


## 3. Domination Polynomial of a Path

LetD(Pn,x)=∑i=⌈n/3⌉nd(Pn,i)xi be the domination polynomial
of a path Pn. In this section we study this polynomial.Theorem 3.1.
(i) If𝒫ni is the family of dominating
set with cardinality i of Pn, then(3.1)|𝒫ni|=|𝒫n−1i−1|+|𝒫n−2i−1|+|𝒫n−3i−1|.
(ii) For everyn≥4,(3.2)D(Pn,x)=x[D(Pn−1,x)+D(Pn−2,x)+D(Pn−3,x)],with the initial values D(P1,x)=x,D(P2,x)=x2+2x, and D(P3,x)=x3+3x2+x.Proof.
(i) It follows from Theorem2.7.
(ii) It follows from Part (i) and the
definition of the domination polynomial.Using Theorem3.1, we obtain d(Pn,j) for 1≤n≤15 as shown in
Table 1. There are interesting relationships between numbers in this table. In
the following theorem, we obtain some properties of d(Pn,j).Table 1
﻿d(Pn,j), the number of dominating set of Pn with cardinality j.
j123456789101112131415n112213131404415038516011013617008221971800426402681900122616534911000013701209843101110005611712111405311112000140192356343192641211300001917148366552625576131140000612053410501148771330891411500001654831373205818661090418103151Theorem 3.2.
The following
properties hold for the coefficients ofD(Pn,x):
(i)
d(P3n,n)=1, for every n∈ℕ.(ii)
d(P3n+2,n+1)=n+2, for every n∈ℕ.(iii)
d(P3n+1,n+1)=((n+2)(n+3))/2−2, for every n∈ℕ.(iv)
d(P3n,n+1)=n(n+1)(n+8)/6, for every n∈ℕ.(v)
d(Pn,n)=1, for every n∈ℕ.(vi)
d(Pn,n−1)=n, for every n≥2.(vii)
d(Pn,n−2)=(n2)−2=(n(n−1)/2)−2, for every n≥3.(viii)
d(Pn,n−3)=(n3)−(3n−8)=(n−4)(n−3)(n+4)/6, for every n≥4.(ix)
d(Pn,n−4)=(n−5)(n3−n2−42n+96)/24, for every n≥5.(x)
1=d(Pn,n)<d(Pn+1,n)<d(Pn+2,n)<⋯<d(P2n−1,n)<d(P2n,n)>d(P2n+1,n)>⋯>d(P3n−1,n)>d(P3n,n)=1.(xi)
∑i=j3jd(Pi,j)=3∑i=j−13j−3d(Pi,j−1).(xii)
Ifsn=∑j=⌈n/3⌉nd(Pn,j), then for every n≥4, sn=sn−1+sn−2+sn−3 with initial
values s1=1,s2=3 and s3=5.(xiii)
For everyn∈ℕ, and k=0,1,2,…,2n−1, d(P2n−k,n)=d(P2n+k,n).(xiv)
For everyj≥⌈n/3⌉, d(Pn+1,j+1)−d(Pn,j+1)=d(Pn,j)−d(Pn−3,j).Proof.
(i) Since𝒫3nn={{2,5,…,3n−1}}, we have d(P3n,n)=1.
(ii) Proof by induction onn. Since 𝒫52={{1,4},{2,4},{2,5}}, so d(P5,2)=3. Therefore the result is true for n=1. Now suppose that the result is true for all natural
numbers less than n, and we prove it for n. By part (i), Theorem 3.1, and the induction hypothesis we have d(P3n+2,n+1)=d(P3n+1,n)+d(P3n,n)+d(P3(n−1)+2,n)=n+2.
(iii) Proof by induction onn. The result is true for n=2, because d(P7,3)=8=4+4. Now suppose that the result is true for all natural
numbers less than n, and we prove it for n. By part (i), (ii), Theorem 3.1, and the induction hypothesis we have(3.3)d(P3n+1,n+1)=d(P3n,n)+d(P3n−1,n)+d(P3n−2,n)=1+d(P3(n−1)+2,n)+d(P3(n−1)+1,n)=1+(n+1)+(n+1)(n+2)2−2=(n+2)(n+3)2−2.
(iv) Proof by induction onn. Since d(P3,2)=3, the result is true for n=1. Now suppose that the result is true for all natural
numbers less than n, and we prove it for n. By Theorem 3.1, parts (ii), (iii), and the
induction hypothesis we have(3.4)d(P3n,n+1)=d(P3n−1,n)+d(P3n−2,n)+d(P3n−3,n)=n+1+(n+1)(n+2)2−2+n(n−1)(n+7)6=n(n+1)(n+8)6.
(v) Since𝒫nn={[n]}, we have the result.
(vi) Since𝒫nn−1={[n]−{x}∣x∈[n]}, we have d(Pn,n−1)=n.
(vii) By induction onn. The result is true for n=3, because d(P3,1)=1. Now suppose that the result is true for all numbers
less that n, and we prove it for n. By Theorem 3.1, induction hypothesis, part (v) and part (vi) we
have(3.5)d(Pn,n−2)=d(Pn−1,n−3)+d(Pn−2,n−3)+d(Pn−3,n−3)=(n−1)(n−2)2+n−3=n(n−1)2−2.
(viii) By induction onn. The result is true for n=4, since d(P4,1)=0. Now suppose that the result is true for all natural
numbers less than or equal n and we prove it
for n+1. By Theorem 3.1, induction hypothesis, parts (vii) and (vi) we
have(3.6)d(Pn+1,n−2)=d(Pn,n−3)+d(Pn−1,n−3)+d(Pn−2,n−3)=(n−4)(n−3)(n+4)6+(n−1)(n−2)2−2+n−2=(n−3)(n−2)(n+5)6.
(ix) By induction onn. Since d(P5,1)=0, the result is true for n=5. Now suppose that the result is true for all natural
numbers less than n, and we prove it for n. By Theorem 3.1, induction hypothesis, parts (viii) and (vii), we have(3.7)d(Pn,n−4)=d(Pn−1,n−5)+d(Pn−2,n−5)+d(Pn−3,n−5)=(n−6)((n−1)3−(n−1)2−42n+138)24+(n−6)(n−5)(n+2)6+(n−3)(n−4)2−2=(n−5)(n3−n2−42n+96)24.
(x) We will prove that for
everyn, d(Pi,n)<d(Pi+1,n) for n≤i≤2n−1, and d(Pi,n)>d(Pi+1,n) for 2n≤i≤3n−1. We prove the first inequality by induction on n. The result holds for n=1. Suppose that result is true for all n≤k. Now we prove it for n=k+1, that is d(Pi,k+1)<d(Pi+1,k+1) for k+1≤i≤2k+1. By Theorem 3.1 and the induction hypothesis we
have(3.8)d(Pi,k+1)=d(Pi−1,k)+d(Pi−2,k)+d(Pi−3,k)<d(Pi,k)+d(Pi−1,k)+d(Pi−2,k)=d(Pi+1,k+1).Similarly, we have the other
inequality.
(xi) Proof by induction onj. First, suppose that j=2. Then ∑i=26d(Pi,2)=12=3∑i=13d(Pi,1). Now suppose that the result is true for every j<k, and we prove for j=k:(3.9)∑i=k3kd(Pi,k)=∑i=k3kd(Pi−1,k−1)+∑i=k3kd(Pi−2,k−1)+∑i=k3kd(Pi−3,k−1)=3∑i=k−13(k−1)d(Pi−1,k−2)+3∑i=k−13(k−1)d(Pi−2,k−2)+3∑i=k−13(k−1)d(Pi−3,k−2)=3∑i=k−13k−3d(Pi,k−1).
(xii) By Theorem3.1, we
have(3.10)sn=∑j=⌈n/3⌉nd(Pn,j)=∑j=⌈n/3⌉n(d(Pn−1,j−1)+d(Pn−2,j−1)+d(Pn−3,j−1))=∑j=⌈n/3⌉−1n−1d(Pn−1,j)+∑j=⌈n/3⌉−1n−2d(Pn−2,j)+∑j=⌈n/3⌉−1n−3d(Pn−3,j−1)=sn−1+sn−2+sn−3.
(xiii) Proof by induction onn. Since d(P1,1)=d(P3,1), the theorem is true for n=1. Now, suppose that the theorem is true for all
numbers less than n, and we will prove it for n. By Theorem 3.1 and the induction hypothesis, we can
write (3.11)d(P2n−k,n)=d(P2n−k−1,n−1)+d(P2n−k−2,n−1)+d(P2n−k−3,n−1)=d(P2(n−1)+1−k,n−1)+d(P2(n−1)−k,n−1)+d(P2(n−1)−1−k,n−1)=d(P2(n−1)+k−1,n−1)+d(P2(n−1)+k,n−1)+d(P2(n−1)+1+k,n−1)=d(P2n+k−3,n−1)+d(P2n+k−2,n−1)+d(P2n+k−1,n−1)=d(P2n+k,n).
(xiv) By
Theorem3.1, we have(3.12)d(Pn+1,j+1)−d(Pn,j+1)=(d(Pn,j)+d(Pn−1,j)+d(Pn−2,j))−(d(Pn−1,j)+d(Pn−2,j)+d(Pn−3,j))=d(Pn,j)−d(Pn−3,j).Therefore we have the result.In the following theorem we use the generating
function technique to find|𝒫ni|.Theorem 3.3.
For everyn∈ℕ and ⌈n/3⌉≤i≤n, |𝒫ni| is the coefficient of unvi in the
expansion of the function(3.13)f(u,v)=u3v(1+3v+v2+3uv+uv2+2u2v+u2v2)1−uv−u2v−u3v.Proof.
Setf(u,v)=∑n=3∞∑i=1∞|𝒫ni|unvi. By recursive formula for |𝒫ni| in Theorem 3.1 we can write f(u,v) in the
following form:(3.14)f(u,v)=∑n=3∞∑i=1∞(|𝒫n−1i−1|+|𝒫n−2i−1|+|𝒫n−3i−1|)unvi=uv∑n=3∞∑i=1∞|𝒫n−1i−1|un−1vi−1+u2v∑n=3∞∑i=1∞|𝒫n−2i−1|un−2vi−1+u3v∑n=3∞∑i=1∞|𝒫n−3i−1|un−3vi−1=uv(|𝒫20|u2+|𝒫21|u2v+|𝒫22|u2v2)+uvf(u,v)+u2v(|𝒫10|u+|𝒫11|uv+|𝒫20|u2+|𝒫21|u2v+|𝒫22|u2v2)+u2vf(u,v)+u3v(|𝒫00|+|𝒫10|u+|𝒫11|uv+|𝒫20|u2+|𝒫21|u2v+|𝒫22|u2v2)+u3vf(u,v). By substituting the values from Table 1 (note that |𝒫n0|=0 for all natural numbers n and |𝒫00|=1), we have(3.15)f(u,v)(1−uv−u2v−u3v)=u3v(1+3v+v2+3uv+uv2+2u2v+u2v2).Therefore we have the result.



---

*Source: 542040-2009-05-05.xml*