# On Distance(r,k)-Fibonacci Numbers and Their Combinatorial and Graph Interpretations

Authors: Dorota Bród
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We introduce three new two-parameter generalizations of Fibonacci numbers. These generalizations are closely related tok-distance Fibonacci numbers introduced recently. We give combinatorial and graph interpretations of distance (r,k)-Fibonacci numbers. We also study some properties of these numbers.


---

## Body

## 1. Introduction

In general we use the standard terminology of the combinatorics and graph theory; see [1]. The well-known Fibonacci sequence {Fn} is defined by the recurrence Fn=Fn-1+Fn-2 for n≥2 with F0=F1=1. The Fibonacci numbers have been generalized in many ways, some by preserving the initial conditions and others by preserving the recurrence relation. For example, in [2] k-Fibonacci numbers were introduced and defined recurrently for any integer k≥1 by F(k,n)=kF(k,n-1)+F(k,n-2) for n≥2 with F(k,0)=0, F(k,1)=1. In [3] the following generalization of the Fibonacci numbers was defined: xn=2rxn-1+xn-2 for an integer r≥0 such that 4r-1+1≠0 and n≥2 with x0=0 and x1=1. Other interesting generalizations of Fibonacci numbers are presented in [4, 5]. In the literature there are different kinds of distance generalizations of Fn. They have many graph interpretations closely related to the concept of k-independent sets. We recall some of such generalizations:(1)
Reference [6]. Consider F(k,n)=F(k,n-1)+F(k,n-k) for n≥k+1 with F(k,n)=n+1 for n≤k.(2)
References [4, 7, 8]. Consider Fibonacci p-numbers Fp(n)=Fp(n-1)+Fp(n-p-1) for any given p(p=1,2,3,…) and n>p+1 with Fp(0)=0 and Fp(n)=1 for 1≤n≤p+1.(3)
Reference [9]. Consider Fd(1)(k,n)=Fd(1)(k,n-k+1)+Fd(1)(k,n-k) for n≥k with Fd(1)(k,n)=1 for n≤k-1.(4)
Reference [9]. Consider Fd(2)(k,n)=Fd(2)(k,n-k+1)+Fd(2)(k,n-k) for n≥k with Fd(2)(k,n)=0 for n=0,…,k-2, Fd(2)(k,k-1)=1, Fd(2)(1,1)=1, Fd(2)(2,2)=2, for k≥3Fd(2)(k,k)=1.(5)
Reference [9]. Consider Fd(3)(k,n)=Fd(3)(k,n-k+1)+Fd(3)(k,n-k) for n≥2k-1 with Fd(3)(k,n)=1 for n=0,…,k-1, Fd(3)(2,2)=2, for k≥3Fd(3)(k,k)=Fd(3)(k,2k-2)=3, for k+1≤n≤2k-1Fd(3)(k,n)=4.(6)
Reference [10]. Consider F2(1)(k,n)=F2(1)(k,n-2)+F2(1)(k,n-k) for n≥k+1 with (1)F21k,n=1ifn≤k-1orn=k=1,2ifn=k≥2.(7)
Reference [11]. Consider F2(2)(k,n)=F2(2)(k,n-2)+F2(2)(k,n-k) for n≥k+1 with(2)F22k,n=0ifnis  odd  andn≤k-1,1ifnis  even  andn≤k-1,F22k,k=0ifk=1,1ifkis  odd  andk≥3,2ifkis  even.(8)
Reference [11]. Consider F2(3)(k,n)=F2(3)(k,n-2)+F2(3)(k,n-k) for n≥k+1 with(3)F23k,n=1ifnis  even  andn≤k-1,2ifnis  odd  andn≤k-1,F23k,k=3ifkis  odd  andk≥3,2ifkis  even  ork=1.In this paper we introduce three new two-parameter generalizations of distance Fibonacci numbers. They are closely related with the numbersF2(j)(k,n), j=1,2,3, presented in [10, 11]. We show their combinatorial and graph interpretations and we present some identities for them.


## 2. Distance(r,k)-Fibonacci Numbers

Letk≥1, n≥0, and r≥1 be integers. We define distance (r,k)-Fibonacci numbers of the first kind Fr(I)(k,n) by the recurrence relation (4)FrIk,n=rFrIk,n-2+rk-1FrIk,n-kforn≥k+1with the following initial conditions:(5)FrIk,0=FrIk,1=1,FrIk,n=rn/2forn=2,3,…,k-2,FrIk,k-1=rk-1/2fork≥3,FrIk,k=rk-1+rk/2fork≥2.For r=1 we get F1(I)(k,n)=F2(1)(k,n). These numbers were introduced in [10].Ifr=1 and k=1, then F1(I)(1,n) gives the Fibonacci numbers Fn. For r=1 and k=3 the numbers F1(I)(3,n) are the well-known Padovan numbers.Table1 includes the values of Fr(I)(k,n) for special values of k and n.Table 1
Distance(r,k)-Fibonacci numbers Fr(I)(k,n) of the first kind.
k
∖
n
0
1
2
3
4
5
6
7
8
1
1
1
r
+
1
2
r
+
1
r
2
+
3
r
+
1
r
2
+
5
r
+
2
r
3
+
4
r
2
+
6
r
+
2
2
r
3
+
9
r
2
+
8
r
+
2
r
4
+
6
r
3
+
15
r
2
+
10
r
+
2
2
1
1
2
r
2
r
4
r
2
4
r
2
8
r
3
8
r
3
16
r
4
3
1
1
r
r
2
+
r
2
r
2
2
r
3
+
r
2
r
4
+
3
r
3
4
r
4
+
r
3
3
r
5
+
4
r
4
4
1
1
r
r
r
3
+
r
2
r
3
+
r
2
2
r
4
+
r
3
2
r
4
+
r
3
r
6
+
3
r
5
+
r
4
5
1
1
r
r
r
2
r
4
+
r
2
r
4
+
r
3
2
r
5
+
r
3
2
r
5
+
r
4
6
1
1
r
r
r
2
r
2
r
5
+
r
3
r
5
+
r
3
2
r
6
+
r
4
7
1
1
r
r
r
2
r
2
r
3
r
6
+
r
3
r
6
+
r
4Letk≥1, n≥0, and r≥1 be integers. We define the distance (r,k)-Fibonacci numbers of the second kind Fr(II)(k,n) by the following recurrence relation: (6)FrIIk,n=rFrIIk,n-2+rk-1FrIIk,n-kforn≥k+1 with initial conditions(7)FrIIk,n=rn/2for  evenn,0for  oddn,forn=0,1,…,k-1FrIIk,k=0fork=1,rk-1for  oddk,k≥3,rk-1+rk/2for  evenk. For r=1 we have then F1(II)(k,n)=F2(2)(k,n); see [10]. Moreover, for r=1 and k=1, n≥2F1(II)(k,n)=Fn-2.In Table2 a few first words of the distance (r,k)-Fibonacci numbers of the second kind Fr(II)(k,n) for special values of k and n are presented.Table 2
Distance(r,k)-Fibonacci numbers Fr(II)(k,n) of the second kind.
k
∖
n
0
1
2
3
4
5
6
7
8
1
1
0
r
r
r
2
+
r
2
r
2
+
r
r
3
+
3
r
2
+
r
3
r
3
+
4
r
2
+
r
r
4
+
6
r
3
+
5
r
2
+
r
2
1
0
2
r
0
4
r
2
0
8
r
3
0
16
r
4
3
1
0
r
r
2
r
2
2
r
3
r
4
+
r
3
3
r
4
3
r
5
+
r
4
4
1
0
r
0
r
3
+
r
2
0
2
r
4
+
r
3
0
r
6
+
3
r
5
+
r
4
5
1
0
r
0
r
2
r
4
r
3
2
r
5
r
4
6
1
0
r
0
r
2
0
r
5
+
r
3
0
2
r
6
+
r
4
7
1
0
r
0
r
2
0
r
3
r
6
r
4Letk≥1, n≥0, and r≥1 be integers. We define distance (r,k)-Fibonacci numbers of the third kind Fr(III)(k,n) by the following recurrence relation: (8)FrIIIk,n=rFrIIIk,n-2+rk-1FrIIIk,n-kforn≥k+1 with initial conditions (9)FrIII1,1=2,FrIIIk,n=rn/2for  evenn,2rn/2for  oddn,forn=0,1,…,k-1FrIIIk,k=rk-1+rk/2for  evenk,rk-1+2rk/2for  oddk≥3.For r=1 we get F1(III)(k,n)=F2(3)(k,n). These numbers were introduced in [11]. For r=1, k=1, and n≥0 we have F1(III)(1,n)=Fn+1. Moreover, for r=1, k=4, and n≥1F1(III)(4,2n)=Fn.Table3 includes a few initial words of distance Fr(III)(k,n) for special values of k and n.Table 3
Distance(r,k)-Fibonacci numbers Fr(III)(k,n) of the third kind.
k
∖
n
0
1
2
3
4
5
6
7
8
1
1
2
r
+
2
3
r
+
2
r
2
+
5
r
+
2
4
r
2
+
7
r
+
2
r
3
+
9
r
2
+
9
r
+
2
5
r
3
+
9
r
2
+
16
r
+
4
r
4
+
14
r
3
+
18
r
2
+
18
r
+
4
2
1
2
2
r
4
r
4
r
2
8
r
2
8
r
3
16
r
3
16
r
4
3
1
2
r
r
2
+
2
r
3
r
2
2
r
3
+
2
r
2
r
4
+
5
r
3
5
r
4
+
2
r
3
3
r
5
+
7
r
4
4
1
2
r
2
r
r
3
+
r
2
2
r
3
+
2
r
2
2
r
4
+
r
3
4
r
4
+
2
r
3
r
6
+
3
r
5
+
r
4
5
1
2
r
2
r
r
2
r
4
+
2
r
2
2
r
4
+
r
3
2
r
5
+
2
r
3
4
r
5
+
r
4
6
1
2
r
2
r
r
2
2
r
2
r
5
+
r
3
2
r
5
+
2
r
3
2
r
6
+
r
4
7
1
2
r
2
r
r
2
2
r
2
r
3
r
6
+
2
r
3
2
r
6
+
2
r
4By the definition of distance(r,k)-Fibonacci numbers of three kinds we get for k≥1 and n≥0 the following relations:(10)FrIIIk,n=2FrIk,nfor  evenkand  oddn,FrIk,n=FrIIk,n=FrIIIk,nfor  evenkand  evenn,FrIIk,n=0for  evenkand  oddn.


## 3. Combinatorial and Graph Interpretations of Distance(r,k)-Fibonacci Numbers

In this section we present some combinatorial and graph interpretations of distance(r,k)-Fibonacci numbers. The classical Fibonacci numbers have many combinatorial interpretations. One of them is the interpretation related to set decomposition. We recall it. Let X={1,2,…,n}, n≥1, and Y⋆={Yt⋆:t∈T} be a family of disjoint subsets of X such that(1)
Yt⋆∈{1,2},(2)
ifYt⋆=2 then Yt⋆ contains two consecutive integers,(3)
X∖⋃t∈TYt⋆=∅.It is well known that the number of all families Y⋆ is equal to the classical Fibonacci numbers Fn. We introduce analogous interpretation of distance (r,k)-Fibonacci numbers.Letr≥1 and X={1,2,…,n}, n≥2, be the set of n integers. Let k≥3. Assume that Rn is a multifamily of two-element subsets of X such that (11)Rn=1,2,1,2,…,1,2︸r-times,2,3,…,2,3︸r-times,…,n-1,n,…,n-1,n︸r-times.For fixed t, 1≤t≤n-k by R(k,t) we denote a subfamily of Rn such that R(k,t)={{t+j,t+j+1}:j=0,1,…,k-2,t=1,2,…,n-k+1}. Analogously for fixed t′ we define R(k,t′)={{t,t+1}:t=1,2,…,n-1}.LetRt,t′(j), j=1,2,3, be a subfamily of Rn such that Rt,t′(j)=R(k,t)∪R(k,t′) and(a)
for eachR(k,t1′),R(k,t2′)∈R(k,t′), t1′≠t2′ holds t1′-t2′≥2, for each R(k,t1),R(k,t2)∈R(k,t), t1≠t2, holds t1-t2≥k,(b)
for eachRt∈Rt,t′(j) holds Rt∈{2,k} for t∈Tand exactly one of the following conditions for Rt∈Rt,t′(j) and j=I,II,III, respectively, is satisfied:(c1)
X∖⋃t∈TRt=∅ or X∖⋃t∈TRt=n,(c2)
X∖⋃t∈TRt=∅,(c3)
X∖⋃t∈TRt∈{0,1} and if p∈X∖⋃t∈TRt then either p=1 or p=n.Assume that the condition (c1) is satisfied. Then the subfamily Rt,t′(1) we will call a decomposition with repetitions of the set X with the rest at the end.Assume that the condition (c2) is satisfied. Then the subfamilyRt,t′(2) we will call a perfect decomposition with repetitions of the set X.Assume that the condition (c3) is satisfied. Then the subfamilyRt,t′(3) we will call a decomposition with repetitions of the set X with the rest at the end or at the beginning.Theorem 1.
Letk≥3, n≥2, and r≥1 be integers. Then the number of all decompositions with repetitions of the set X with the rest at the end is equal to the number Fr(I)(k,n).Proof (induction onn).
Letk≥3, n≥2, and r≥1 be integers. Let X={1,2,…,n}. Denote by d(n) the number of all decompositions with repetitions of X with the rest at the end. Let n=2. Then it is easily seen that there are exactly r decompositions of X. Thus we get d(2)=r=Fr(I)(k,2). Let n≥3. Assume that equality d(n)=Fr(I)(k,n) holds for an arbitrary n. We will show that d(n+1)=Fr(I)(k,n+1).
Letd2(n+1) and dk(n+1) denote the number of all decompositions R with repetitions of the set X={1,2,…,n+1} with the rest at the end such that {1,2}∈R and {1,2,…,k}∈R, respectively. It is easily seen that (12)dn+1=d2n+1+dkn+1. Moreover, we get(13)d2n+1=dkn-1,dkn+1=dkn+1-k.By the induction hypothesis and by recurrence (4) we obtain(14)dn+1=dn-1+dn+1-k=FrIk,n-1+FrIk,n+1-k=FrIk,n+1,which ends the proof.Analogously as Theorem1 we can prove the following.Theorem 2.
Letk≥3, n≥2, and r≥1 be integers. Then the number of all perfect decompositions with repetitions of the set X is equal to the number Fr(II)(k,n).Theorem 3.
Letk≥3, n≥2, and r≥1 be integers. Then the number of all decompositions with repetitions of the set X with the rest at the end or at the beginning is equal to the number Fr(III)(k,n).Distance(r,k)-Fibonacci numbers of three kinds have a graph interpretation, too. It is connected with k-distance H-matchings in graphs. We recall the definition of a k-distance H-matching. Let G and H be any two graphs, let k≥1 be an integer, and a k-distance H-matching M of G is a subgraph of G such that all connected components of M are isomorphic to H and for each two components H1 and H2 from M for each x∈V(H1) and y∈V(H2) holds dG(x,y)≥k. In case of k=1 and H=K2 we obtain the definition of matching in classical sense. If M covers the set V(G) (i.e., V(M)=V(G)), then we say that M is a perfect matching of G. For k=2 and H=K1 the definition of k-distance H-matchings reduces to the definition of an independent set of a graph G. In the literature the generalization of H-matching of a graph G is considered, too. For a given collection H=H1,H2,…,Hn of graphs a H-matching M of G is a family of subgraphs of G such that each connected component of M is isomorphic to some Hi, 1≤i≤n. Moreover, the empty set is a H-matching of G, too. If Hi=H for all i=1,2,…,n, then we obtain the definition of H-matching.AmongH-matchings we consider such H-matchings, where Hi, i=1,2,…,n, belong to the same class of graphs, namely, 2-vertex or k-vertex paths (P2 and Pk, resp.), k≥3.Consider a multipathPnr, where n≥2, r≥1, V(Pnr)={x1,x2,…,xn}, and(15)EPnr=x1,x2,…,x1,x2︸r-times,x2,x3,…,x2,x3︸r-times,…,xn-1,xn,…,xn-1,xn︸r-times.Letn≥2, k≥3, and r≥1 be integers. In the graph terminology the number Fr(I)(k,n) is equal to the number of special {P2,Pk}-matchings M of the multipath Pnr such that at most one vertex, namely, xn, does not belong to a {P2,Pk}-matching of the graph Pnr. We will call such matchings M a quasi-perfect matching of Pnr. The number Fr(II)(k,n) is equal to the number of such {P2,Pk}-matchings of Pnr that both vertex x1 and vertex xn belong to some {P2,Pk}-matchings M and M′, respectively, of the graph Pnr. In other words the number Fr(II)(k,n) is equal to all perfect {P2,Pk}-matchings M of the graph Pnr.The numberFr(III)(k,n) is equal to the number of special {Pk,P2}-matchings of the multipath Pnr such that at most one vertex either vertex x1 or xn does not belong to a {P2,Pk}-matching of the graph Pnr.Letσ(Pnr) be the number of all perfect {P2,Pk}-matchings M of the graph Pnr.Theorem 4.
Letr≥1, k≥3, and n≥2 be integers. Then σ(Pnr)=Fr(II)(k,n).Proof.
Consider a multipathPnr where vertices from V(Pnr)={x1,x2,…,xn} are numbered in the natural fashion. Let σk(n) and σ2(n) be the number of perfect {P2,Pk}-matchings M of Pnr such that xn,xn-1∈V(M) and xn,xn-1,…,xn-k∈V(M), respectively. It is easily seen that σk(n)+σ2(n)=σ(Pnr).
LetM be an arbitrary perfect {P2,Pk}-matching of Pnr, k≥3. Consider two cases:(1)
{xn-1,xn}∈E(Pk), where Pk∈M.
Then we can choose the edge{xn-1,xn} on r ways. Moreover, M=M′∪{Pk}, where M′ is an arbitrary {P2,Pk}-matching of the graph Pnr∖{xn,xn-1,…,xn-k+1} which is isomorphic to the multipath Pn-kr. Hence σk(n)=rk-1σ(Pn-kr).(2)
{xn-1,xn}∈E(P2), where P2∈M.
Proving analogously as in case (1) we obtain σ2(n)=rσ(Pn-2r).
Consequently(16)σPnr=σkn+σ2n=rk-1σPn-kr+rσPn-2r.Claim (17)σPnr=rk-1FrIIk,n-k+rFrIIk,n-2.
Proof. Assume now that the set X={1,2,…,n} corresponds to V(Pnr) with the numbering in the natural fashion. Let R(t,t′)={Rt:t∈T}∪{Rt′:t′∈T} be a multifamily of X which gives a perfect decomposition of the set X. Then every Rt and Rt′ correspond to subgraph P|Rt| and P|Rt′| for t,t′∈T, respectively, of Pnr. By Theorem 2 we get (18)σPnr=σkn+σ2n=rk-1FrIIk,n-k+rFrIIk,n-2. Moreover, by (6) we obtain σ(Pnr)=Fr(II)(k,n), which ends the proof.Analogously we can prove combinatorial interpretations of numbersFr(I)(k,n) and Fr(III)(k,n).


## 4. Identities for Distance(r,k)-Fibonacci Numbers

In this section we give some identities and some relations between distance(r,k)-Fibonacci numbers of three types.Theorem 5.
Fork≥1, n≥2k-2, and j=I,II,III, (19)Frjk,n=rFrjk,n-2+rk-2Frjk,n-k+2-r2k-3Frjk,n-2k+2.Proof.
We give the proof for distance(r,k)-Fibonacci numbers of the first kind. By the definition of numbers Fr(I)(k,n), we have(20)rFrIk,n-2+rk-2FrIk,n-k+2-r2k-3FrIk,n-2k+2=rFrIk,n-2+rk-2rFrIk,n-k+rk-1FrIk,n-2k+2-r2k-3FrIk,n-2k+2=rFrIk,n-2+rk-1F2Ik,n-k=FrIk,n,which ends the proof.Corollary 6.
Forn≥2Fn=1/2(Fn-2+Fn+1).Proof.
Forr=1, j=I, and k=1 by (19) we obtain (21)F1I1,n=Fn=Fn-2+Fn+1-Fn.Hence (22)Fn=12Fn-2+Fn+1.Theorem 7.
Forr≥1, k≥2, and n≥1, (23)FrIk,n=FrIIk,n+FrIIk,n-1.Proof (induction onn).
Forn=1 we have (24)FrIk,1=1=FrIIk,1+FrIIk,0. Assume that equality (23) is true for an arbitrary n. We will prove it for n+1. By the recurrence (6) and by induction hypothesis we get (25)FrIk,n+1=rFrIk,n-1+rk-1FrIk,n+1-k=rFrIIk,n-1+FrIIk,n-2+rk-1FrIIk,n+1-k+FrIIk,n-k=rFrIIk,n-1+rk-1FrIIk,n+1-k+rFrIIk,n-2+rk-1F2IIk,n-k=FrIIk,n+1+FrIIk,n, which ends the proof.Analogously we can prove the following.Theorem 8.
Forr≥1, k≥3, and n≥0, (26)2FrIk,n=FrIIk,n+FrIIIk,n.Theorem 9.
Forr≥1, k≥2, n≥2k, and j=I,II,III, (27)Frjk,n=r2Frjk,n-4+2rkFrjk,n-k-2+r2k-2Frjk,n-2k.



---

*Source: 879510-2015-09-14.xml*