Sergey Kirgizov

Jos É L Ram Írez

POLYOMINOES AND GRAPHS BUILT FROM FIBONACCI WORDS

We introduce the k-bonacci polyominoes, a new family of polyominoes associated with the binary words avoiding k consecutive 1's, also called generalized k-bonacci words. The polyominoes are very entrancing objects, considered in combinatorics and computer science. The study of polyominoes generates a rich source of combinatorial ideas. In this paper we study some properties of k-bonacci polyominoes. Specifically, we determine their recursive structure and, using this structure, we enumerate them according to their area, semiperimeter, and length of the corresponding words. We also introduce the k-bonacci graphs, then we obtain the generating functions for the total number of vertices and edges, the distribution of the degrees, and the total number of k-bonacci graphs that have a Hamiltonian cycle.

The family of binary words avoiding a consecutive pattern is well-known in combinatorics and computer science. Many combinatorial statistics or parameters over these words can be studied with automata and grammars by means of the Chomsky-Schűtzenberger methodology [START_REF] Delest | Algebraic languages: a bridge between combinatorics and computer science[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Castro | Applications in enumerative combinatorics of infinite weighted automata and graphs[END_REF]. For instance, the language of binary words avoiding k consecutive 1's is a well-known example from one of Knuth's books [18, p. 286]. In this paper the words from this language are called generalized k-bonacci words. Vajnovszki [START_REF] Vajnovszki | A loopless generation of bitstrings without p consecutive ones[END_REF] studied these words in the context of exhaustive generation of Gray codes. Recently, Bernini [START_REF] Bernini | Restricted binary strings and generalized Fibonacci numbers[END_REF] considered some combinatorial properties of these languages. Baril et al. [START_REF] Baril | Gray codes for Fibonacci q-decreasing words[END_REF] give a bijection between k-bonacci words and the q-decreasing words (for q = k -1), they also provide an efficient exhaustive generating algorithm for q-decreasing words in lexicographic order.

Another direction in the study of the Fibonacci words is in Graph Theory. The n-length binary words that avoid two consecutive ones are the vertices of the Fibonacci cube [START_REF] Hsu | Fibonacci cubes -new interconnection topology, Parallel and Distributed Systems[END_REF]. Two Fibonacci words of the same length are adjacent in the graph if its Hamming distance is equal to one, that is, they differ in exactly one symbol. The Fibonacci cube is a subgraph of the n-dimensional hypercube. The Fibonacci cube has been extensively studied in recent years. See [START_REF] Klavžar | Structures of Fibonacci cubes: a survey[END_REF] for a survey.

In this paper, we are interested in the study of a new family of polyominoes and graphs associated with the generalized k-bonacci words. Let F n,k denote the set of n-length binary words avoiding k consecutive 1's, and F k = ∪ n≥1 F n,k . The set F k corresponds to the set of generalized k-bonacci words. The elements of F n,2 are called Fibonacci words. For example, F 3,2 = {000, 001, 010, 100, 101} and F 3,3 = {000, 001, 010, 011, 100, 101, 110}.

The set F n,k is enumerated by the generalized Fibonacci numbers F n+2,k . This sequence is defined by F n,k = k i=1 F n-i,k for n ≥ 2, with F 1,k = 1 and F n,k = 0 for all n ≤ 0. Given a word w = w 1 • • • w n ∈ F n,k , its associated polyomino, called k-bonacci polyomino, is a bargraph of n columns, such that the i-th column has w i + 1 unit cells for 1 ≤ i ≤ n. For example, Figure 1 shows the polyominoes associated with the 3-bonacci words of length 3. Let P n,k denote the set of k-bonacci polyominoes with n columns. The elements of P n,2 are called Fibonacci polyominoes.

The polyominoes provide a rich source of combinatorial ideas. For example, polyominoes play an important role in the combinatorics on words because they can be encoded by words, and then the problem of deciding if a given polyomino tiles the plane by a translation reduces to finding a special factorization of the word [START_REF] Beauquier | On translating one polyomino to tile the plane[END_REF]. In particular, polyominoes associated with some special prefixes of the infinite Fibonacci word tile the plane by translations [START_REF] Blondin-Massé | Two infinite families of polyominoes that tile the plane by translation in two distinct ways[END_REF][START_REF] Ramírez | A generalization of the Fibonacci word Fractal and the Fibonacci snowflake[END_REF]. The polyominoes have also been studied in connection with other discrete structures such as permutations, set partitions, compositions, among others (see for example [START_REF] Blecher | Combinatorial parameters in bargraphs[END_REF][START_REF] Callan | Statistics on bargraphs of Catalan words[END_REF][START_REF]Polygons, Polyominoes and Polycubes[END_REF][START_REF] Mansour | Enumerations on bargraphs[END_REF] and references contained therein).

Any k-bonacci polyomino can be regarded as a graph, called k-bonacci graph, considering the cell sides as edges and cell corners as vertices. For example, Figure 2 shows the graphs associated with the 3-bonacci polyominoes with 3 columns. Let G n,k denote the set of k-bonacci graphs associated with the polyominoes of P n,k . Note that in G n,k there are isomorphic graphs, in particular, graphs corresponding to words 00 and 1 are isomorphic. And if w 1 and w 2 are two different k-bonacci words of length n ≥ 2, such that w R 1 = w 2 (where w R denotes the reverse of the word w), then the graphs induced by these words are isomorphic. The k-bonacci graphs are particular examples of chemical graphs, that is, graphs with all vertices of degree at most four. In this paper, we obtain several enumerative results of the k-bonacci polyominoes including the area and semi-perimeter. For the k-bonacci graphs we study the number of vertices and edges, the degree sequence polynomial, the average degree of a vertex, and the number of k-bonacci graphs that have at least one Hamiltonian cycle.

We obtain these results by using the recursive construction of the k-bonacci words and generating functions in several variables. The generating functions have been successfully used to study several statistics over Fibonacci-runs graphs and the restricted Fibonacci words. See for example [START_REF] Egecioglu | Statistics on restricted Fibonacci words[END_REF][START_REF] Egecioglu | Fibonacci-run graphs I: Basic properties[END_REF][START_REF] Egecioglu | Fibonacci-run graphs II: Degree sequences[END_REF]. n-j,k (possibly empty) and C j is a concatenation of j columns of height 2, for 1 ≤ j < k. Figure 3 illustrates the above decomposition. 1.1. Area and Semiperimeter. In this section we study the distribution of the area and semiperimeter in P n,k . Let P be a k-bonacci polyomino. We denote by area(P ) the number of cells of P and by sper(P ) the semiperimeter, that is the half of the perimeter of P (since the perimeter of a k-bonacci polyomino is always an even number). Define the generating function

• • • j • • • j (1) (2) (3) (4) (5)
F k (x, p, q) := n≥1 x n P ∈P n,k
p sper(P ) q area(P ) , k ≥ 2, where x marks the length of the corresponding k-bonacci word, i.e., the number of cells in the bottom row of a polyomino. Analogously, we introduce the generating functions

F k,j (x, p, q) := n≥1 x n P ∈P (j) n,k
p sper(w) q area(P ) , for j = 1, 2.

It is clear that

F k (x, p, q) = F k,1 (x, p, q) + F k,2 (x, p, q). (1.1)
In Theorem 1.1 we give a rational expression for the generating function F k (x, p, q).

Theorem 1.1. The generating function for k-bonacci polyominoes with respect to the length of the corresponding word, semiperimeter and area (marked respectively by x, p and q) is F k (x, p, q) = p 2 ((q + pq 2 )x -(pq 3 -p 2 q 3 )x 2 -p k q 2k x k -p k+1 q 2k+1 x k+1 ) 1 -(pq + pq 2 )x + (p 2 q 3 -p 3 q 3 )x 2 + p k+2 q 2k+1 x k+1 .

Proof. From the decomposition given in Figure 3 we have the functional equations

F k,1 (x, p, q) = p 2 qx (1)
+ pqx(F k,1 (x, p, q) + F k,2 (x, p, q))

(2)+(3)

F k,2 (x, p, q) = k-1 j=1 p i+2 q 2i x j (4)
+   k-1 j=1 p i+1 q 2i x j   F k,1 (x, p, q) (5) = p 2 (pq 2 x -p k q 2k x k ) 1 -pq 2 x + p(pq 2 x -p k q 2k x k ) 1 -pq 2 x F k,1 (x, p, q).
To make understanding easier, cases (1) to (5) in Figure 3 are indicated below their corresponding terms. Solving the above system of equation and from (1.1) we obtain the desired result. □

For example, the series expansion of the generating function F 3 (x, p, q) begins with (p 2 q + p 3 q 2 )x + (p 3 q 2 + 2p 4 q 3 + p 4 q 4 )x 2 + (p 4 q 3 + 3p 5 q 4 + 2p 5 q 5 + p 6 q 5 )x 3

+ (p 5 q 4 + 4p 6 q 5 + 3p 6 q 6 + 3p 7 q 6 + 2p 7 q 7 )x 4 + • • •

Figure 4 shows the weights of the 3-bonacci polyominoes corresponding to the bold coefficient in the above series.

p 4 q 3 p 5 q 4 p 5 q 4 p 5 q 5 p 5 q 4 p 6 q 5 p 5 q 5 Corollary 1.2. The generating functions for the total area and semi-perimeter within all of the members in P n,k are

A k (x) = 3x -2kx k -2(2 -k)x k+1 + x 2k+1 (1 -2x + x k+1 ) 2 and P k (x) = 5x -5x 2 -(2 + k)x k -(1 -k)x k+1 + 4x k+2 -x 2k+2 (1 -2x + x k+1 ) 2 , respectively.
Proof. From the definition of F k (x, p, q) we have the equalities

A k (x) = ∂F k (x, 1, q) ∂q q=1 and P k (x) = ∂F k (x, p, 1) ∂p p=1 .
Therefore, from Theorem 1.1 we obtain the desired results. □

VOLUME, NUMBER

A 2 (x) = x(3 + 2x + x 2 ) (1 -x -x 2 ) 2 , A 3 (x) = x(3 + 6x + 3x 2 + 2x 3 + x 4 ) (1 -x -x 2 -x 3 ) 2 , A 4 (x) = x(3 + 6x + 9x 2 + 4x 3 + 3x 4 + 2x 5 + x 6 ) (1 -x -x 2 -x 3 -x 4 ) 2 , P 2 (x) = x(5 + x -2x 2 -x 3 ) (1 -x -x 2 ) 2 , P 3 (x) = x(5 + 5x -3x 3 -2x 4 -x 5 ) (1 -x -x 2 -x 3 ) 2 , P 4 (x) = x(5 + 5x + 5x 2 -x 3 -4x 4 -3x 5 -2x 6 -x 7 ) (1 -x -x 2 -x 3 -x 4 ) 2 .
We will apply the same technique to obtain other corollaries throughout the article.

1.2. Area and Semiperimeter of the Fibonacci polyominoes. For the Fibonacci polyominoes (k = 2) we can give some additional results. Let t n (p, q) denote the n-th coefficient of F 2 (x, p, q), that is, t n (p, q) :=

P ∈P n,2
p sper(P ) q area(P ) .

Theorem 1.3. For all n ≥ 3 we have

t n (p, q) = pqt n-1 (p, q) + p 3 q 3 t n-2 (p, q),
with the initial values t 1 (p, q) = p 2 q + p 3 q 2 and t 2 (p, q) = p 3 q 2 + 2p 4 q 3 . Moreover, for all n ≥ 1 we have the combinatorial formula

t n (p, q) = ⌊ n+1 2 ⌋ i=0 n + 1 -i i p n+i+1 q n+i . (1.2)
Proof. Let P be a Fibonacci polyomino with n columns (n ≥ 3). If the last column has height 1, then the number of this kind of polyominoes is given by qpt n-1 (p, q). On the other hand, if the last column has height 2, then the previous column has height 1, and these polyominoes are counted by the polynomial p 3 q 3 t n-2 (p, q). Hence the total number of Fibonacci polyominoes is given by pqt n-1 (p, q) + p 3 q 3 t n-2 (p, q). Finally, we can use mathematical induction and the recurrence relation to prove the combinatorial identity. This formula can be also proved by means of Zeilberger's creative telescoping method [21]. Denote the summand on the right side of the equality in (1.2) by F (n, i), that is

F (n, i) := n + 1 -i i p n+i+1 q n+i .
By the Zeilberger algorithm, F (n, i) satisfies the relation

F (n + 2, i) -pqF (n + 1, i) -p 3 q 3 F (n, i) = G(n, i + 1) -G(n, i), (1.3)
with the certificate

R(n, i) = - i(2 -i + n)p 2 q 2 (2 -2i + n)(3 -2i + n) .
That is, R(n, i) = G(n, i)/F (n, i) is a rational function in both variables. If f (n) denotes the right sum in the equality (1.2), then summing both sides of (1.3) with respect to i yields f (n + 2) -pqf (n + 1) -p 3 q 3 f (n) = 0. The sequences f (n) and t n (p, q) satisfy the same recurrence relation and have the same initial values, therefore these sequences coincides for all positive integers n. □ Corollary 1.4. The total area for all Fibonacci polyominoes in P n,2 is

⌊ n+1 2 ⌋ i=0 n + 1 -i i (n + i) = 1 5 (6nF n+2 + (n + 2)F n ),
where F n is the n-th Fibonacci number.

Proof. From Theorem 1.3 the total area of the Fibonacci polyominoes is given by

∂t n (1, q) ∂q q=1 = ⌊ n+1 2 ⌋ i=0 n + 1 -i i (n + i).
For the expression in terms of Fibonacci numbers we use the generating function of the total area

A 2 (x) = x(3 + 2x + x 2 ) (1 -x -x 2 ) 2 = (3x + 2x 2 + x 3 ) n≥0 c(n + 2)x n ,
where c(n) is the convolution of the Fibonacci numbers, that is

c(n) = n i=0 F i F n-i = 1 5 ((n -1)F n + 2nF n-1 ) .
In the last equality we use the identity (32.13) given in [START_REF] Koshy | Fibonacci and Lucas Number with Applications[END_REF]. Therefore,

[x n ]A 2 (x) = 3c(n + 1) + 2c(n) + c(n -1) = 1 5 (6nF n+2 + (n + 2)F n ), n ≥ 1.

□

The number of Fibonacci polyominoes of area n is related to the Narayana's cows sequence [START_REF] Allouche | Narayana's cows and delayed morphisms[END_REF]

n = ⌊(n-1)/3⌋ i=0 n -2i -1 i .
Theorem 1.5. The number of Fibonacci polyominoes of area n is equal to the number of Narayana's cows b n+1 .

Proof. From Theorem 1.1 the generating function of the number of Fibonacci polyominoes of a fixed area is

F 2 (1, 1, q) = q(1 + q + q 2 )
1 -q -q 3 . On the other hand, the generating function of the Narayana sequence is N (x) := i≥0 b i x i = 1/(1 -x -x 3 ). Then N (q) = 1 + q + qF 2 (1, 1, q). By comparing the n-th coefficient of the generating functions N (q) and F 2 (1, 1, q) we obtain the desired result. □

VOLUME, NUMBER

For example, Figure 5 shows the Fibonacci polyominoes of area 5, that is, b 6 = 6 polyominoes.

Figure 5. Fibonacci polyominoes of area 5.

Number of Vertices and Edges

The goal of this section is to enumerate the number of vertices and edges of the k-bonacci graphs. Let G be a k-bonacci graph. We denote by ver(G) and edg(G) the number of vertices and edges of the graph G. Let G

G k (x, p, q) := n≥1 x n G∈G n,k p edg(G) q ver(G) , k ≥ 2.
Similarly, we have the generating functions G k,j (x, p, q) := n≥1

x n G∈G (j) n,k p edg(G) q ver(G) , for j = 1, 2.

In these trivariate generating functions the variable x marks the length of the corresponding k-bonacci word, i.e., the number of vertices in the bottom row of a graph minus one.

Theorem 2.1. The generating function for k-bonacci graphs with respect to the length of the corresponding word, the number of edges and vertices (marked respectively by x, p and q) is G k (x, p, q) = p 2 q 3 ((p 2 q + p 5 q 3 )x -(p 7 q 4 -p 8 q 5 )x 2 -p 5k q 3k x k -p 5k+3 q 3k+2 x k+1 ) 1 -(p 3 q 2 + p 5 q 3 )x + (p 8 q 5 -p 9 q 6 )x 2 + p 5k+4 q 3k+3 x k+1 .

Proof. From the decomposition given in Figure 3 we have the functional equations

G k,1 (x, p, q) = p 4 q 4 x (1)
+ p 3 q 2 x(G k,1 (x, p, q) + G k,2 (x, p, q)) (2)+(3) G k,2 (x, p, q) = k-1 j=1 p 3j+2j+2 q 3(j+1) x j (4) +   k-1 j=1 p 3j+2j+1 q 3j+1 x j   G k,1 (x, p, q) (5)
= p 2 q 3 (p 5 q 3 x -p 5k q 3k x k ) 1 -p 5 q 3 x + pq(p 5 q 3 x -p 5k q 3k x k ) 1 -p 5 q 3 x G k,1 (x, p, q). Solving the above system of equation and from the equality G k (x, p, q) = G k,1 (x, p, q) + G k,2 (x, p, q) we obtain the desired result. □

MONTH YEAR 7 THE FIBONACCI QUARTERLY

For example, the series expansion of the generating function G 3 (x, p, q) begins with x p 7 q 6 + p 4 q 4 + x 2 p 12 q 9 + 2p 10 q 8 + p 7 q 6 + x 3 p 16 q 12 + 2p 15 q 11 + 3p 13 q 10 + p 10 q 8 + x 4 2p 21 q 15 + 3p 19 q 14 + 3p 18 q 13 + 4p 16 q 12 + p 13 q 10 + • • • Figure 6 shows the weights of the 3-bonacci graphs corresponding to the bold coefficient in the above series.

p 10 q 8 p 13 q 10 p 13 q 10 p 15 q 11 p 13 q 10 p 16 q 12 p 15 q 11 Corollary 2.2. The generating functions for the total number of vertices and edges within all of the members in G n,k are

V k (x) = 10x -9x 2 -3(1 + k)x k -(4 -3k)x k+1 + 8x k+2 -2x 2k+2 (1 -2x + x k+1 ) 2 and E k (x) = 11x -5x 2 -(2 + 5k)x k -(9 -5k)x k+1 + 4x k+2 + 2x 2k+1 -x 2k+2 (1 -2x + x k+1 ) 2 ,
respectively.

In particular, for k = 2, 3, and 4 we obtain the following generating functions:

V 2 (x) = 2x(5 + x -2x 2 -x 3 ) (1 -x -x 2 ) 2 , V 3 (x) = x(10 + 11x -6x 3 -4x 4 -2x 5 ) (1 -x -x 2 -x 3 ) 2 , V 4 (x) = x(10 + 11x + 12x 2 -2x 3 -8x 4 -6x 5 -4x 6 -2x 7 ) (1 -x -x 2 -x 3 -x 4 ) 2 , E 2 (x) = x(11 + 5x -x 3 ) (1 -x -x 2 ) 2 , E 3 (x) = x(11 + 17x + 6x 2 + x 3 -x 5 ) (1 -x -x 2 -x 3 ) 2 , E 4 (x) = x(11 + 17x + 23x 2 + 7x 3 + 2x 4 + x 5 -x 7 ) (1 -x -x 2 -x 3 -x 4 ) 2 .
Let v n (p, q) denote the n-th coefficient of G 2 (x, p, q), that is,

v n (p, q) := G∈G n,2
p edg(G) q ver(G) .

VOLUME, NUMBER

Theorem 2.3. For all n ≥ 3 we have v n (p, q) = p 3 q 2 v n-1 (p, q) + p 9 q 6 v n-2 (p, q), with the initial values v 1 (p, q) = p 4 q 4 + p 7 q 6 and v 2 (p, q) = p 7 q 6 + 2p 1 0q 8 . Moreover, for all n ≥ 1 we have the combinatorial formula

v n (p, q) = ⌊ n+1 2 ⌋ i=0 n + 1 -i i p 3n+1+3i q 2n+2+2i .

Degree Sequences

In this section we are interested in the degree sequence of a k-bonacci graph. Degree sequences have been well studied for Fibonacci cubes [START_REF] Klavžar | The degree sequence of Fibonacci and Lucas cubes[END_REF] and Fibonacci-run graphs [START_REF] Egecioglu | Fibonacci-run graphs II: Degree sequences[END_REF]. Recall that the degree of a vertex of a graph is the number of edges that are incident to the vertex. A k-bonacci graph can have only vertices of degree two, three, or four. Let G be a k-bonacci graph. We denote by deg i (G) the number of vertices of degree i in the graph G.

We are interested in the generating function

D k (x, q 2 , q 3 , q 4 ) := n≥1 x n G∈G n,k q deg 2 (G) 2 q deg 3 (G) 3 q deg 4 (G) 4 , k ≥ 2,
where x marks the length of the corresponding k-bonacci word, i.e., the number of vertices in the bottom row of a graph minus one. Analogously, we introduce the generating functions D k,j (x, q 2 , q 3 , q 4 ) :

= n≥1 x n G∈G (j) n,k q deg 2 (G) 2 q deg 3 (G) 3 q deg 4 (G) 4
, j = 1, 2.

Theorem 3.1. For all k ≥ 2, the generating function D k (x, q 2 , q 3 , q 4 ) is given by q 4 2 (q 2 3 q 4 + q 4 )x -(q 2 3 q 2 4 -2q 2 q 2 3 q 2 4 + q 4 3 q 4 )x 2 -q 2k 3 q k 4 x k + (q 2k+2 3 q k 4 -2q 2 q 2k 3 q k+1 4 )x k+1 q 4 (1 -(q 2 3 + q 4 q 2 3 )x + (q 4 q 4 3 -q 2 2 q 2 4 q 2 3 )x 2 + q 2 2 q k+1 4 q 2k 3 x k+1 )

.

Proof. Let G be a Fibonacci graph in G n,k . If n = 1, then G contributes to the generating function the term q 4 2 x. See Figure 7 case (1). If n > 1 and G ∈ G

n,k , then this case contributes to the generating function the terms q 2 3 xD k,1 (x, q 2 , q 3 , q 4 ) and q 2 q 4 xD k,2 (x, q 2 , q 3 , q 4 ), as seen in Figure 7 cases ( 2) and ( 3). Notice that in the case (2) we have only two new vertices of degree 3. In the case (3) we have a new vertex of degree 2 and another of degree 4. The red vertices denote the vertices of degree 2, the blue vertices denote the vertices of degree 3, and the green vertices denote the vertices of degree 4. For n > 1 and G ∈ G

n,k , this case contributes the terms (see Figure 7 cases (4) and ( 5))

q 4 2 k-1 j=1 q 2(j-1)+2 3 q j-1 4 x j (4) +   q 2 k-1 j=1 q 2(j-1)+2 3 q j 4 x j   D k,1 (x, q 2 , q 3 , q 4 ) (5)
.

j • • • j q 4 2 x D k,1 (x, q 2 , q 3 , q 4 ) × q 2 3 x D k,2 (x, q 2 , q 3 , q 4 ) × q 2 q 4 x • • • q 4 2 q
2(j-1)+2 3 q j-1 4 x j D k,1 (x, q 2 , q 3 , q 4 ) × q 2 q 2(j-1)+2 3 Therefore, we have the functional equations D k,1 (x, q 2 , q 3 , q 4 ) = q 4 2 x + q 2 3 xD k,1 (x, q 2 , q 3 , q 4 ) + q 2 q 4 xD k,2 (x, q 2 , q 3 , q 4 ) D k,2 (x, q 2 , q 3 , q 4 ) = q 4 2 (q 2 3 q 4 x -q 2k 3 q k 4 x k ) q 4 (1 -q 2 3 q 4 x)

q j 4 x j
+ q 2 (q 2 3 q 4 x -q 2k 3 q k 4 x k ) 1 -q 2 3 q 4 x D k,1 (x, q 2 , q 3 , q 4 ).
Solving the above system of equation we obtain the desired result. □

For example, the series expansion of the generating function D 3 (x, q 2 , q 3 , q 4 ) begins with q 4 2 q 2 3 + q 4 2 x + 2q 5 2 q 2 3 q 4 + q 4 2 q 2 3 + q 4 2 q 4 3 q 4 x 2 + q 6 2 q 4 3 q 2 4 + q 6 2 q 2 3 q 2 4 + 2q 5 2 q 4 3 q 2 4 + 2q 5 2 q 4 3 q 4 + q 4 3 q 4 2 x 3 + • • • Figure 8 shows the weights of the 3-bonacci graphs corresponding to the bold coefficient in the above series.

q 4 2 q 4 3 q 5 2 q 4 3 q 4 q 6 2 q 2 3 q 2 4 q 5 2 q 4 3 q 2 4 q 5 2 q 4 3 q 4 q 6 2 q 4 3 q 2 4 q 5 2 q 4 3 q 2 4 Figure 8. Weights for the graphs in G 3,3 .

Corollary 3.2. The generating function for the total number of vertices of degree 2 within all of the members in G n,k is

D (2) k (x) := 2(4x -7x 2 -2x k + x k+1 + 7x k+2 -x 2k+1 -2x 2k+2 ) (1 -2x + x k+1 ) 2 .

VOLUME, NUMBER

In particular, for k = 2, 3, and 4 we obtain the following generating functions:

D (2) 2 (x) = 2x(4 -x -5x 2 -2x 3 ) (1 -x -x 2 ) 2 , D (2) 3 (x)
= 2x(4 + x -4x 2 -8x 3 -5x 4 -2x 5 ) (1 -x -x 2 -x 3 ) 2 , D (2) 4 (x)
= 2x(4 -7x -2x 3 + x 4 + 7x 5 -x 8 -2x 9 ) (1 -2x + x 5 ) 2 .
Corollary 3.3. The generating function for the total number of vertices of degree 3 within all of the members in G n,k is

D (3) k (x) := 2(x + x 2 -kx k -(1 -k)x k+1 -2x k+2 + x 2k+2 ) (1 -2x + x k+1 ) 2 .
In particular, for k = 2, 3 and 4 we obtain the following generating functions:

D (3) 2 (x) = 2x(1 + x + 2x 2 + x 3 ) (1 -x -x 2 ) 2 , D (3) 3 (x)
= 2(x + x 2 -3x 3 + 2x 4 -2x 5 + x 8 ) (1 -2x + x 4 ) 2 , D (3) 4 (x)
= 2(x + x 2 -4x 4 + 3x 5 -2x 6 + x 10 ) (1 -2x + x 5 ) 2 .
Corollary 3.4. The generating function for the total number of vertices of degree 4 within all of the members in G n,k is

D (4) k (x) := 3x 2 + (1 -k)x k -(4 -k)x k+1 -2x k+2 + 2x 2k+1 (1 -2x + 2x k+1 ) 2 .
In particular, for k = 2, 3 and 4 we obtain the following generating functions:

D (4) 2 (x) = 2x 2 (1 + x) (1 -x -x 2 ) 2 , D (4) 3
(x) = x 2 (3 + 4x + 4x 2 + 2x 3 ) (1 -x -x 2 -x 3 ) 2 , D (4) 4 (x)
= 3x 2 -3x 4 -2x 6 + 2x 9 (1 -2x + x 5 ) 2 .
3.1. The degree sequence of the Fibonacci graph. Finally, we consider the particular case of Fibonacci graphs

(k = 2). Let d n,2 (q) denote the n-th coefficient of D 2 (x, q, 1, 1), that is, d n,2 (q) := G∈G n,2 q deg 2 (G) .
Similarly, we define the sequences

d n,3 (q) := G∈G n,2 q deg 3 (G) and d n,4 (q) := G∈G n,2
q deg 4 (G) .

Theorem 3.5. For all n ≥ 3 we have

d n,2 (q) = d n-1,2 (q) + q 2 d n-2,2 (q),
with the initial values d 1,2 (q) = 2q 4 and d 2,2 (q) = q 4 + 2q 4 . Moreover, for all n ≥ 1 we have the combinatorial formula

d n,2 (q) = n i=1 n -1 -⌊ i 2 ⌋ ⌊ i-1 2 ⌋ + n -2 -⌊ i-1 2 ⌋ ⌊ i-2 2 ⌋ q i+3 . (3.1)
Proof. Define the generating function D 2 (x, q) := n≥0 d n,2 (q)x n . From the Theorem 3.1 we have the expression

D 2 (x, q) = xq 4 (2 -x + 2xq) 1 -x -q 2 x 2 .
This generating function satisfies

D 2 (x, q) -xD 2 (x, q) -q 2 x 2 D 2 (x, q) = 2q 4 x -q 4 x 2 + 2q 5 x 2 .
By comparing the coefficient of x n , for n ≥ 2, in the above equality, we obtain the recurrence relation for the sequence d n,2 (q). On the other hand, the combinatorial sum (3.1) is equivalent to

i≥0 2 n -i -1 i -1 q 2i+3 + n -i i -1 q 2i+2 + n -i -1 i -2 q 2i+2 . (3.2)
Denote the above summand by F (n, i), that is

F (n, i) :=2 n -i -1 i -1 q 2i+3 + n -i i -1 q 2i+2 + n -i -1 i -2 q 2i+2 = (n -i -1)! (n(2q + 1) -4iq + 2q -1) (i -1)!(n -2i + 1)! q 2i+2 .
By the Zeilberger algorithm, F (n, i) satisfies the relation

F (n + 2, i) -F (n + 1, i) -q 2 F (n, i) = G(n, i + 1) -G(n, i), (3.3)
with the certificate

R(n, i) = (n -i)(i -1) ((4i -6)q -n(2q + 1) + 1) (n + 2 -2i)(n + 3 -2i) (2nq + n -4iq + 2q -1)
.

If f (n) denotes the combinatorial sum in (3.2), then summing both sides of (3.3) with respect to i yields f (n + 2) -f (n + 1) -q 2 f (n) = 0. The sequences f (n) and d n,2 (q) satisfy the same recurrence relation and have the same initial values, therefore these sequences coincides for all positive integers n. □

Notice that the total vertices of degree 2 of all Fibonacci graphs in G n,2 is given by n i=1

(i + 3) n -1 -⌊ i 2 ⌋ ⌊ i-1 2 ⌋ + n -2 -⌊ i-1 2 ⌋ ⌊ i-2 2 ⌋
.

From a similar argument as in Theorem 3.5 we can prove the following two theorems.

Theorem 3.6. For all n ≥ 3 we have

d n,3 (q) = q 2 (d n-1,3 (q) + d n-2,3 (q)),
with the initial values d 1,3 (q) = q 2 + 1 and d 2,3 (q) = 3q 2 . Moreover, for all n ≥ 1 we have the combinatorial formula

d n,3 (q) = n i=0 (1 + q 2 )q 2(n-1-i) n -i -1 i + (2q 2 -q 4 )q 2(n-1-i) n -i -2 i .
Theorem 3.7. For all n ≥ 3 we have d n,4 (q) = d n-1,4 (q) + q 2 d n-2,4 (q), with the initial values d 1,2 (q) = 2q 4 and d 2,2 (q) = q 4 + 2q 4 . Moreover, for all n ≥ 1 we have the combinatorial formula

d n,4 (q) = n+2 i=0 n -1 -⌊ i-2 2 ⌋ ⌊ i-3 2 ⌋ + n -2 -⌊ i-3 2 ⌋ ⌊ i-4 2 ⌋ q i-3 .
Let d n denote the total number of vertices of the Fibonacci polyominoes in G n,2 . In the following theorems we study the proportion between the sequences d n,i := d n,i (1) (i = 2, 3, 4) and d n . Before, we need the following result. Theorem 3.8 (Asymptotics of linear recurrences, [START_REF] Sedgewick | An Introduction to the Analysis of Algorithms 2nd[END_REF]). Assume that a rational generating function f (x)/g(x), with f (x) and g(x) relatively prime and g(0) ̸ = 0, has a unique pole 1/β of smallest modulus. Then, if the multiplicity of 1/β is ν, we have

[x n ] f (x) g(x) ∼ ν (-β) ν f (1/β) g (ν) (1/β) β n n ν-1 .
Theorem 3.9. Among total degree of vertices of all graphs in G n,2 , the proportion of those that are of degree 2 is asymptotically

lim n→∞ d n,2 d n = 7 - √ 5 22
≈ 0.21654236.

Proof. The generating functions of the sequences d n and d n,2 are rational, therefore we can use the asymptotic analysis for linear recurrences. First, note that the unique pole 1/β of the rational generating function

V 2 (x) = n≥0 d n x n = 2x(5 + x -2x 2 -x 3 ) (1 -x -x 2 ) 2 is α = -1+ √ 5 2
, with multiplicity 2. Therefore

d n ∼ 2(3+2 √ 5) 5 1+ √ 5 2 n n. Similarly, we have d n,2 ∼ ( 1+ √ 5
2 ) n+1 n. From these expressions we obtain the desired result. □ Theorem 3.10. Among total degree of vertices of all graphs in G n,2 , the proportion of those that are of degree 3 is asymptotically

lim n→∞ d n,3 d n = 4 + √ 5 11
≈ 0.56691527.

Proof. The unique pole 1/β of the rational generating function

n≥0 d n,3 x n = 2(x -x 2 + x 3 -2x 4 + x 6 ) (1 -2x + x 3 ) 2 is α = -1+ √ 5 2
, with multiplicity 2.

Therefore d n,2 ∼ 2(2+ √ 5) 5

( 1+ √ 5
2 ) n n. Since

d n ∼ 2(3+2 √ 5) 5 ( 1+ √ 5
2 ) n n we obtain the desired result. □ Theorem 3.11. Among total degree of vertices of all graphs in G n,2 , the proportion of those that are of degree 4 is asymptotically

lim n→∞ d n,4 d n = 7 - √ 5 22
≈ 0.216542364.

Number of Hamiltonian k-bonacci graphs

A Hamiltonian cycle is a cycle that visits each vertex exactly once. Let G be a k-bonacci graph. We define Ham(G) = 1 if G has a Hamiltonian cycle, and 0 otherwise. If Ham(G) = 1, we say that G is a Hamiltonian k-bonacci graph. Define the generating function

H k (x, q) := n≥1 x n G∈G n,k q Ham(G) , k ≥ 2,
where x marks the length of the corresponding k-bonacci word, i.e., the number of vertices in the bottom row of a graph minus one. Similarly, we have the generating functions

H k,j (x, q) := n≥1 x n G∈G (j) n,k
q Ham(G) , for j = 1, 2.

Theorem 4.1. For all k ≥ 2 we have

H k (x, q) = x((1 -x)x(1 -x 2⌊(k-1)/2⌋ ) -q(1 + x)(1 -2x + x k+1 )(-2 + x + x 2⌊k/2⌋ )) (1 -2x + x k+1 )(1 -x -2x 2 + x 3 + x 2(1+⌊k/2⌋
) .

Proof. From the decomposition given in Figure 3 we have the functional equation

H k,1 (x, q) = qx (1)
+ x(H k,1 (x, q) + H k,2 (x, q))

(2)+(3)

The polyomino given in the decomposition (4) corresponds to the grid graph P 3 × P i , for 1 < i ≤ k. It is known 1 that the grid graph P n × P m has a hamiltonian cycle if and only if at least one of m or n is even or m = n = 1. Therefore, the graph P 3 × P i has a hamiltonian cycle if and only if i is even. In this case, the generating function is given by

T k (x, q) = q ⌊k/2⌋ j=1 x 2j-1 + ⌊(k-1)/2⌋ j=1 x 2j (4) = x q + x -x 2⌊ k-1 2 ⌋+1 -qx 2⌊ k 2 ⌋ 1 -x 2 .
Therefore, we obtain the functional equation

H k,2 (x, q) = T k (x, q) (4)
+   ⌊k/2⌋ j=1 x 2j-1   H k,1 (x, q) +   ⌊(k-1)/2⌋ j=1 x 2j   H k,1 (x, 1) (5)
= T k (x, q) + x(1 -x 2⌊k/2⌋ ) 1 -x 2 H k,1 (x, q) + x 2 (1 -x 2⌊(k-1)/2⌋ ) 1 -x 2

x(1 -x k ) 1 -2x + x k+1 . Notice that H k,1 (x, 1) is the generating function of the total number of k-bonacci words end in 1. Solving the above system of equation we obtain the desired result. □ 1 See, for example the discussion on "Math Stackexchange": https://math.stackexchange.com/questions/ 1699203/hamilton-paths-cycles-in-grid-graphs

VOLUME, NUMBER

Corollary 4.2. The generating function for the total number of Hamiltonian k-bonacci graphs is

H k (x) := x(1 + x)(2 -x -x 2⌊k/2⌋ ) 1 -x -2x 2 + x 3 + x 2⌊k/2⌋+2 .
In particular, for 2 ≤ k ≤ 7 we obtain the following generating functions:

H 2 (x) = H 3 (x) = x(2 + x) 1 -x -x 2 , H 4 (x) = H 5 (x) = x(2 + x + x 2 + x 3 ) 1 -x -x 2 -x 4 , H 6 (x) = H 7 (x) = x(2 + x + x 2 + x 3 + x 4 + x 5 ) 1 -x -x 2 -x 4 -x 5 .
Note that every Fibonacci graph admits a Hamiltonian cycle, just walk along its border. The grid P 3 × P 3 does not have a Hamiltonian cycle, so Hamiltonian 3-bonacci graphs cannot have grids P 3 × P 3 as induced subgraphs. Thus, they are precisely 2-bonacci. In general, Hamiltonian 2k-bonacci equals Hamiltonian (2k +1)-bonacci graphs, because any Hamiltonian (2k + 1)-bonacci graph cannot contain P 2k+1 × P 3 as induced subgraph, and there are no 1 2k factors in the corresponding binary words.

Figure 1 .

 1 Figure 1. The Fibonacci polyominoes associated with the words in F 3,3 .

Figure 2 .

 2 Figure 2. The 3-bonacci graphs in G 3,3 .

2 VOLUME, NUMBER 1 .

 1 Decomposition of the k-Bonacci PolyominoesLet P denote the sets of k-bonacci polyominoes with n columns, whose last column has height 1 and 2, respectively. It is clear that P n,k = P , then P is a unit square or P = P ′ □, where P ′ ∈ P n-1,k = P k (n > 1). If P ∈ P (2) n,k , then P = P ′ C j , where P ′ ∈ P[START_REF] Allouche | Narayana's cows and delayed morphisms[END_REF]

Figure 3 .

 3 Figure 3. Decomposition of a k-bonacci polyomino.

Figure 4 .

 4 Figure 4. Weights for polyominoes in P 3,3 .

  . The Narayana's cows sequence b n is defined by the recurrence relation b n = b n-1 + b n-3 for n ≥ 3, with the initial values b 0 = 0, b 1 = 1, and b 2 = 1. The Narayana's cows sequence can be calculated with the formula b

  denote the set of k-bonacci graphs associated with the polyominoes in P (1) n,k and P (2) n,k , respectively. Define the generating function

Figure 6 .

 6 Figure 6. Weights for the graphs in G 3,3 .

Figure 7 .

 7 Figure 7. Decomposition of a k-bonacci graph.