ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.561316 J. Algebra Comb. Discrete Appl. 6(2) • 63–74 Received: 23 March 2018 Accepted: 12 March 2019 0 Journal of Algebra Combinatorics Discrete Structures and Applications Fibonacci numbers and resolutions of domino ideals Research Article Rachelle R. Bouchat, Tricia Muldoon Brown Abstract: This paper considers a class of monomial ideals, called domino ideals, whose generating sets correspond to the sets of domino tilings of a 2 × n tableau. The multi-graded Betti numbers are shown to be in one-to-one correspondence with equivalence classes of sets of tilings. It is well-known that the number of domino tilings of a 2 × n tableau is given by a Fibonacci number. Using the bijection, this relationship is further expanded to show the relationship between the Fibonacci numbers and the graded Betti numbers of the corresponding domino ideal. 2010 MSC: 05E40, 13A15 Keywords: Fibonacci numbers, Monomial ideals, Domino tilings 1. Introduction Monomial ideals have been studied using mechanisms from several different areas of mathematics, including combinatorics, graph theory, algebra, and topology. Given a simplicial complex, there are two common monomial ideals that are studied, the Stanley Reisner ideal of the complex as well as the facet ideal of the complex (see Miller and Sturmfels [14] for a comprehensive overview of these results). Of particular interest are monomial ideals representing well-known combinatorial objects. For example, Conca and De Negri [8] introduced the study of edge ideals. These edge ideals are squarefree monomial ideals generated from the edges of a graph. Edge ideal results have been extended to the study of path ideals by Bouchat, Há, and O’Keefe [4] and further generalized to facet ideals of simplicial complexes by Faridi [10] and to path ideals of hypergraphs by Há and Van Tuyl [12]. Furthermore, many other natural combinatorial objects can be used to generate squarefree monomial ideals. In this paper, we consider a class of monomial ideals arising from the set of domino tilings of a 2 ×n tableau. A domino tiling of a 2×n rectangular tableau is a disjoint arrangement of 2×1 tiles placed horizontally or vertically to completely cover the area of the rectangle. Domino tilings have been well-studied from Rachelle R. Bouchat; Department of Mathematics, Indiana University of Pennsylvania, USA (email: rbouchat@iup.edu). Tricia Muldoon Brown (Corresponding Author); Department of Mathematical Sciences, Georgia Southern Uni- versity, USA (email: tmbrown@georgiasouthern.edu). 63 https://orcid.org/0000-0003-2286-0805 https://orcid.org/0000-0003-3835-1175 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 a combinatorial viewpoint, and they have many interesting properties. For example, using DeMoivre’s initial conditions on Fibonacci numbers, a classic exercise can show the number of 2 ×n domino tilings is given by the nth Fibonacci number. Further, a survey paper by Ardilla and Stanley [2] gives many results for domino and more generalized tilings of the plane. In this paper, we will show the Fibonacci numbers also occur naturally when enumerating graded Betti numbers related to domino tilings. Tilings have been studied in terms of their enumeration, their intersection, and their connection to graph theory. See Fisher and Temperley [16] and Kasteleyn [13] for the first enumerative results; Butler, Horn, and Tressler [7] for intersection results; or Benedetto and Loehr [3] for graph theoretical results. These results, among others, suggest that interpretation as monomial ideals will also be of interest. Here, we extend previous work by the authors [6] to enumerative results concerning the multi-graded and graded Betti numbers of the ideal corresponding to the set of all 2 ×n domino tilings. For a field k, to each domino position in the 2 × n tableau, we associate a variable in the ring R = k[x1, . . . ,x2(n−1),y1, . . . ,yn]. The xi for 1 ≤ i ≤ n− 1 are associated with the horizontally placed dominoes covering entries (1, i) and (1, i+ 1), the xi for n ≤ i ≤ 2(n−1) are associated with the dominoes covering entries (2, i− (n− 1)) and (2, i− (n− 1) + 1), and the yi for 1 ≤ i ≤ n are associated with the vertically oriented dominoes covering entries (1, i) and (2, i). Definition 1.1. Consider a 2 ×n tableau being tiled with 2 × 1 tiles, and denote the set of tilings of the tableau by Tn = {τ : τ is a tiling of the 2 ×n tableau}. Let zi ∈{x1, . . . ,x2(n−1),y1, . . . ,yn}. 1. The tiling monomial xτ associated to the tiling τ is the monomial xτ = ∏ z δzi (τ) i where δzi (τ) = { 1 , if zi ∈ τ 0 , else 2. Associated to a collection of domino tilings {τ1, . . . ,τm} is the domino monomial xτ1,...τm = ∏ z δzi ({τ1,...,τm}) i where δzi ({τ1, . . . ,τm}) = { 1 , if zi ∈ τj for some 1 ≤ j ≤ m, 0 , else. Example 1.2. The tiling monomial associated to the following tiling of the 2 × 7 tableau  x1 x3 x5 y7x7 x9 x11   is x1x3x5x7x9x11y7, and the domino monomial associated to the collection of tilings  x1 x3 x5 y7x7 x9 x11 , y1 y2 y3 x4 x6 x10 x12   is x1x3x4x5x6x7x9x10x11x12y1y2y3y7. Definition 1.3. The domino ideal corresponding to an 2 ×n tableau is the ideal I := (xτ : xτ is a tiling monomial). We note, the generating set of the domino ideals associated to the set of all 2×n domino tilings can also be viewed as paths of a graph. However, the ideals are not path ideals, as their generating sets do not correspond to all paths of a specified length within a graph, but rather just a subset, as illustrated in Example 1.4. 64 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 Example 1.4. Consider a 2×3 tableau, then the domino ideal I is generated by the domino monomials corresponding to the tilings in the set:  x1 y3x3 , y1 x2 x4 , y1 y2 y3   Then I = (x1x3y3,x2x4y1,y1y2y3) ⊂ k[x1,x2,x3,x4,y1,y2,y3]. Notice that I is generated by a subcollec- tion of the paths of length two in the graph: x3 x1 y3 y2 y1 x2 x4 Before stating our results, we give the necessary background from topology and commutative algebra. 2. Background In this paper, we will focus on properties of domino ideals relating to the corresponding minimal free resolutions. Since a domino ideal, I, can be viewed as a finitely generated graded R-module. Associated to I is a minimal free resolution, which is of the form 0 → ⊕ a R(−a) βp,a(I) δp−→ ⊕ a R(−a) βp−1,a(I) δp−1−→ ··· δ1−→ ⊕ a R(−a) β0,a(I) → I → 0 where the maps δi are exact and where R(−a) denotes the translation of R obtained by shifting the degree of elements of R by a ∈ Nn. The numbers βi,a(I) are called the multi-graded Betti numbers of I, and they correspond to the number of minimal generators of degree a occurring in the ith-syzygy module of I. The graded Betti numbers for a finitely generated ideal I, can be computed using the software system Macaulay2 (see [11]) and are displayed in a Betti table where: 0 1 · · · i · · · total: – – – 0: 1: ... j : βi,i+j(I) ... Example 2.1. Consider the domino ideal I = (x1x3y3,x2x4y1,y1y2y3) ⊂ k[x1,x2,x3,x4,y1,y2,y3] cor- responding to a 2 × 3 tableau. Then the Betti table from Macaulay2 corresponding to the minimal free resolution of I is: 0 1 2 total : 3 3 1 3 : 3 . . 4 : . 2 . 5 : . 1 1 From this Betti table, it is easy to form the graded minimal free resolution of I: 0 −→ R(−7) −→ R2(−5) ⊕ R(−6) −→ R3(−3) −→ I −→ 0. 65 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 Throughout this paper, we will be using a result adapted from Theorem 2.8 of Alilooee and Faridi [1] to calculate the multi-graded Betti numbers for path ideals of rooted trees. Before we provide this result, we need the following definitions from simplicial topology. Definition 2.2. 1. An abstract simplicial complex, ∆, on a vertex set X = {x1, . . . ,xn} is a collection of subsets of X satisfying: (a) {xi}∈ ∆ for all i, and (b) F ∈ ∆, G ⊂ F =⇒ G ∈ ∆. The elements of ∆ are called faces, and the maximal faces (under inclusion) are called facets. The simplicial complex ∆ with facets F1, . . . ,Fs will be denoted by 〈F1, . . . ,Fs〉. 2. For any Y ⊆ X, an induced subcollection of ∆ on Y, denoted by ∆Y, is the simplicial complex whose vertex set is a subset of Y and whose facet set is given by {F | F ⊆Y and F is a facet of ∆}. 3. If F is a face of ∆ = 〈F1, . . . ,Fs〉, the complement of F in ∆ is given by FcX = X \ F, and the complementary complex is then ∆cX = 〈(F1) c X , . . . , (Fs) c X〉. Note, in the setting of domino monomials, we let xτ represent either a monomial in the ring R = k[x1, . . . ,x2(n−1),y1, . . . ,yn] or a simplex whose vertices are given by the variables. Thus given x = xτ1,τ2,...,τm, the complex Γx is the simplicial complex 〈xτ1,xτ2, . . . ,xτm〉 and its complementary complex Γcx is given by Γcx = 〈(xτ1 ) c x, (xτ2 ) c x, . . . , (xτm ) c x〉. The following example illustrates this complex. Example 2.3. Consider the domino monomial x = x1x2x4x5x6x8y1y2y3 originating from a 2×5 tableau, which is generated from the set of tilings {x1x4x5x8y3,x2x4x6x8y1,x4x8y1y2y3}. We have Γcx = 〈x2x6y1y2,x1x5y2y3,x1x2x5x6〉. We often apply a deformation retraction to associate variables that always appear together in the com- plement, such as xi with xn−1+i, and in doing so we obtain the following complex that is topologically equivalent to Γcx: Γcx '〈x2y1y2,x1y2y3,x1x2〉' S 1 Complementary complexes are important in determining the Betti numbers as we see in the following corollary. Corollary 2.4 (Corollary 2.11 in [5]). Let S = k[x1, . . . ,xn] be a polynomial ring over a field k, and let I be a pure, squarefree monomial ideal in S. Then the multi-graded Betti numbers of I are given by βi,a(I) = dimk H̃i−1 ( ΓcVert(Γ) ) where Γ is an induced subcollection of ∆(I) with Vert(Γ) = {xi | ai = 1} where a = (a1, . . . ,an). Concluding the background results, we observe the following: Corollary 2.5. Let I be a domino ideal. Then βi,a(I) ∈{0, 1}. As we can find a path ideal containing each domino ideal and because path ideals have this property (see Erey and Faridi [9]), the result follows immediately. 66 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 3. Statistics In order to associate the domino monomials with the appropriate multi-graded Betti numbers, we first introduce three statistics on the set of domino monomials. Definition 3.1. Given a domino monomial x corresponding to the 2 ×n tableau: 1. Set d(x) = d1d2 · · ·dn ∈ {1, 2, 3}n where di = #{z ∈ {xi−1,xi,yi} : z|x} for all 1 ≤ i ≤ n− 1 and dn = #{z ∈{xn−1,yn} : z|x}. We say d(x) is the depth sequence of x. 2. Set v(x) = #{yiyi+1 : yiyi+1|x,xixn−1+i - x, and di = di+1 = 2} to be the number of pairs of vertical dominos in x with a 2 in the depth sequence at these positions such that the corresponding pair of horizontal dominos is not in x. The depth sequence is so named because if all dominos of the monomial x were minimally stacked in their respective positions on the 2 ×n tableau, the height at position i would correspond to the value of the depth sequence di. Both of these statistics will be utilized to classify sets of domino monomials by their the multi-graded Betti numbers βi,a(In). To simplify notation we let 1k represent the depth sequence given by the string of k ones 11 · · ·1, and similarly let 2k = 22 · · ·2 and 3k = 33 · · ·3 describe the depth sequences of strings of k twos and threes, respectively. Thus, for example, the depth sequence 2221233211 can be written as 231232212. Before defining the third statistic, we need to introduce two operations on depth sequences. Definition 3.2. Let d(x) = d1d2 · · ·dn ∈{1, 2, 3}n be a given depth sequence. O1. We may double the sequence by taking any subsequence of 1k , for 1 ≤ k ≤ n, and replacing it with 2k. O2. We may triple the sequence by taking any single subsequence of 23 and replacing the middle two with a three. To illustrate the above definitions for the two operations, we provide the following examples. Example 3.3. Consider the depth sequence d(x) = 1111222211. Then we can double d(x) to obtain the sequence 2221222211 or 1111222222, among others. We could also triple d(x) to obtain 1111232211 or 1111223211. We can now introduce the next statistic on domino monomials. Definition 3.4. The starting column of a domino monomial x is given by the minimum number of operations, doubles or triples, needed to obtain the depth sequence d(x) from the depth sequence 1n. We write sc(x) to represent this quantity. When considering the formation of a domino monomial from the underlying optimal stacking of domino tilings, it becomes clear that the starting column statistic is well-defined. For instance, replacing a subsequence of 1k with 2k could correspond to taking a domino tiling with horizontal tiles at particular entries and combining it with another domino tiling having vertical tiles on those same entries, among other options. Similarly, replacing a subsequence of 23 with 232 could correspond to having both pairs of horizontal tiles as well as the two end vertical tiles and then adding in a third tiling which includes the central vertical tile. Example 3.5. Consider the domino monomial x = x1x3x4x5x6x7x9x10x11x12y1y2y3y7 presented in Example 1.2. The depth sequence of x is d(x) = 27, and as 27 is minimally created from 17 by one operation of changing a sequence of seven ones into seven twos, the starting column is sc(x) = 1. 67 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 We intend to use the starting column statistic, sc(x) to identify the minimum label i such that βi,a(In) = 1 where a is the (3n − 2)-tuple such that ai = δzi ({τ1, . . . ,τm}) for x{τ1,...,τm}. We note, monomials with the same depth sequence may appear in different columns of the Betti table. Thus, the starting column is needed to determine the column i for a given monomial x{τ1,...,τm}. Proposition 3.6. Let Γcx be the complementary complex of a domino monomial x such that xixn−1+i | x, yi - x, and yi+1 - x for some 1 < i < n− 1. Further, let x′ be the domino monomial x′ = x yiyi+1 xixn−1+i . If Γcx is homotopic to the sphere S j, then Γcx′ is homotopic to the sphere S j+1. Proof. By Corollary 2.5, if Γcx is not contractible we may assume it is homotopic to a sphere S j for some j ≥ 0. Now, when transitioning from the domino monomial x to x′ by replacing the variables xixn−1+i with yiyi+1, the vertex set of Γx also changes to the vertex set of Γx′ in the same way. Thus every facet in the complementary complex Γcx can be mapped to a facet of Γ c x′ through this replacement. That is, a tiling in Γx containing xixn−1+i is mapped to a tiling in Γx′ containing yiyi+1, and the complements of these tilings within their respective complementary complexes are the same. Further, a tiling in Γx which does not contain xixn−1+i is mapped to itself in Γx′, and thus the complement of that tiling in Γcx which contains xixn−1+i is mapped to the facet of Γcx′ containing yiyi+1 using the replacement. First, we note by our hypothesis the image of Γcx in Γ c x′ is homotopic to S j. Second, these facets may be grouped into two disjoint sets; that is, into the set of facets which contain the vertices yiyi+1 and the set of facets which contain xi−1xi+1. Now, the remaining facets of Γcx′ must be complements of tilings that contained yi or yi+1, but not both. Therefore, these facets can also be put into two disjoint sets, namely the set of complementary facets which contain the vertices xi+1yi or the set of complementary facets which contain the vertices xi−1yi+1. Thus, in the complex Γcx′, we have disjoint sets of facets containing xi−1xi+1 or yiyi+1, forming a sphere; and moreover, both of these sets are connected to those facets containing xi−1yi+1, creating a pyramid over the sphere Sj. On the other hand these disjoint sets of facets which form the sphere are also connected to xi+1yi, creating another pyramid over this sphere. As there is no connection between the apex of either of these two pyramids, we see the complex is actually a bipyramid over a sphere, Sj, which is homotopic to the sphere Sj+1, and we have proven the claim. Note, although the action in Proposition 3.6 of replacing two interior stacked horizontal tiles with their respective pair of vertical tiles affects the dimension of the complementary complex it does not change the depth sequence, that is d(x) = d(x′). Recall, in the case that the depth sequence of a domino monomial is a string of ones, we know the domino monomial corresponds to a single tiling, and as a generator of the ideal we have β0,a(In) = 1. Thus, if i = 0, the multi-graded Betti number, β0,a(In) = 1 if and only if x = xτ. The next proposition describes the multi-graded Betti numbers for i ≥ 1. Proposition 3.7. Given a domino monomial x = x{τ1,...,τm}, let a = (a1,a2, . . . ,a3n−2) where ai = δzi ({τ1, . . . ,τm}). Then for i ≥ 1, the multi-graded Betti number βi,a(In) = 1 if and only if i = sc(x) + v(x). Proof. Let x be a domino monomial. We first consider the domino monomials where v(x) = 0; that is, the monomials whose corresponding multi-graded Betti numbers are non-zero when i = sc(x). Since there is always a deformation retraction that takes xixn−1+i to xi, we will use the variable xi for 1 ≤ i ≤ n−1 to represent the monomial xixn−1+i. Case: d(x) ∈ {1, 2}n \ 1n. Assume the depth sequence consists of m strings of consecutive twos separated by strings of ones. For example: 222211122221112211 m = 3 122122122221122122 m = 5 For each string of twos in columns ci,ci + 1, . . . ,ci + ki where 1 ≤ ci ≤ n − 1 indexes the first col- umn of the ith string of twos for 1 ≤ i ≤ m and ki ≥ 1, consider a partial domino monomial xcixci+1 · · ·xci+kiyciyci+ki which corresponds to the pair of tilings 68 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 Si = { {xcixci+2 · · ·xci+ki−1,xci+1xci+3 · · ·xci+ki−2yciyci+ki} if n is even {xcixci+2 · · ·xci+ki−2yci+ki,xci+1xci+3 · · ·xci+ki−1yci} if n is odd (Note, a sequence of only one 2 is impossible so ki > 0.) The maximal set of tilings in the equivalence class of x, Sx, consists of the concatenation of one element from the pair of tilings in Si for all 1 ≤ i ≤ m, along with fixed choices for the variables representing the strings of ones. In the complementary complex, every variable corresponding to a one in the depth sequence appears in each generator, and thus does not appear in any facets of the complementary complex. Furthermore, note that the two sub-tilings in Si are complementary to each other, so we may represent Si as {ti, t̄i}. With this notation: Γcx = 〈t1t2 · · ·tm, t̄1t2 · · ·tm, t1t̄2 · · ·tm, . . . , t1t2 · · · ¯tm, t̄1t̄2 · · ·tm, . . . , t̄1t2 · · · ¯tm, . . . , t1t̄2 · · · ¯tm, . . . , t̄1t̄2 · · · ¯tm〉 is homotopic to the complex with m vertices and m complementary vertices, such that in each of the 2m m-dimensional facets no element is in the same facet as its complement, but is in every other facet that does not contain its complement. As this complex is the cross-product of m zero-dimensional spheres, it is homotopic to a sphere of dimension m− 1. Thus we have βm,a(In) = dimKH̃m−1(Sm−1) = 1 and i = sc(x) + v(x) = m. Case: d(x) ∈ {1, 2, 3}n \{1, 2}n. First assume that x can be written x = x̂ ·yc for some column c for 1 < c < n− 1 and some x̂ where d(x̂) ∈ {1, 2}n \ 1n, and thus the depth sequence of x has exactly one three. We compare the complementary complex Γcx with the complementary complex Γx̂. From the case above, we know Γcx̂ is homotopic to a sphere in dimension m− 1. Further every tiling in Γx̂ is also a tiling in Γx, and thus every facet in Γcx̂ appears as a part of a facet of Γ c x by the simplicial join with yc. Therefore, the image of Γcx̂ ∗yc in Γ c x is a cone over an (m− 1)-dimensional sphere. The rest of Γcx is generated by the complements of tilings which contained the vertical tile yc. Recall, that the sphere Γcx̂ can be described as strings of barred and unbarred vertices where, without loss of generality, the unbarred vertex corresponds to the tiling with odd indexed x variables and the barred vertex corresponds to the tiling with even indexed x variables. Any tiling containing horizontal tiles and yc must contain both odd and even indexed x variables, and hence the complementary facet also contains odd and even indexed x vertices while also avoiding yc. Therefore these complements contain tiles in ti and t̄i and so fill the void in the sphere described by Γcx̂. Thus Γ c x is the cone by yc over the boundary of an m-dimensional ball and thus is homotopic to a sphere Sm. For depth sequences with more than one three, this process can be iterated so the result follows from the previous case. Finally, we need to consider domino monomials with a given depth sequence d(x) where v(x) > 0. Consider the set of pairs {yiyi+1 : yiyi+1|x,xixn−1+i - x, and di = di+1 = 2} Note, if we replace any subset of non-overlapping pairs of yiyi+1 in the monomial x with the corresponding xixn−1+i, the depth sequence remains unchanged. Applying Proposition 3.6, we see each of these replacements of yiyi+1 with xixn−1+i decreased the dimension of the sphere by one, as well as decreased the statistic v(x) by one. By reversing this process we have proven the claim. Example 3.8. Consider the domino monomial x = x1x3x4x5x6x7x9x10x11x12y1y2y3y7 from Example 1.2, and observe that x contains two adjacent pairs of vertical dominos. However, for only one of these pairs, y2y3, is the corresponding pair of horizontal dominos absent, so we have i = sc(x) + v(x) = 2 + 1 = 3. Thus, the equivalence class of tilings x corresponds to the multi-graded Betti number β3,a(I7) = 1 where a = (a1 . . . ,a3n−2) is such that am = 1 if and only if m|x and am = 0 otherwise. We may now state our main result. 69 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 Theorem 3.9. Let Tn be the set of domino tilings of a 2 ×n tableau, and let In be the monomial ideal generated by the tilings τi ∈ Tn. Then, the set of non-zero multi-graded Betti numbers βi,a(In) for i ≥ 0 are in bijection with the set of domino monomials generated from Tn. Proof. Given a domino monomial, Proposition 3.7 shows the appropriate multi-graded Betti number is non-zero as the complementary complex corresponds to a sphere. By definition, non-zero multi-graded Betti numbers can be described by a set of domino tilings, so the result follows. 4. Enumeration As the correspondence between domino monomials and non-zero multi-graded Betti numbers of the domino ideal is well understood, we now wish to utilize this result to enumerate graded Betti numbers of the domino ideal. We will see that the nature of the tilings as counted by Fibonacci numbers is carried through to the sets of tilings. As stated, the number of 2 ×n domino tilings is given by the nth Fibonacci number Fn where the Fibonacci number are defined by the recursion with DeMoivre’s initial conditions, Fn+2 = Fn+1 + Fn; F0 = 1,F1 = 1. The Fibonacci numbers are one of the most ubiquitous sequences in combinatorics. One can see the entry A000045 in OEIS[15] to find numerous references to sets of combinatorial objects enumerated by the Fibonacci numbers. We will use products of Fibonacci numbers and binomial coefficient expansions of Fibonacci numbers to count sets of tilings and consequently to determine the graded Betti numbers. In Section 3, we defined a depth sequence for a monomials associated with sets of domino tilings. Now, we begin by considering specific subsequences which we will call fundamental. Using the fundamental sequences, we then build all possible depth sequences corresponding to tiling monomials. The fundamental subsequences are: 1k, 2k, 12k3, 32k1, 32k3, and 3k The first class of fundamental tilings is already well-understood, and thus the number of domino tilings of depth 1k is given by Fk for 0 ≤ k ≤ n. Further, a subsequence of k ones in the depth sequence of a domino monomial implies that every 2 ×n tiling in the set of tilings which comprise the monomial x must contain the same set of k tiles chosen in Fk ways. Because there can be no overlap between tiles chosen for this subsequence and those in other positions of the depth sequence, when counting we may choose this set of dominos independent of the number of ways to choose sets of dominoes to fill in the rest of the 2 × n rectangle. Thus the tilings with a given depth sequence may be enumerated by the product of appropriate Fibonacci numbers for each string of one’s multiplied by the number of ways to choose dominos for the sequences of two’s and three’s. So next, consider the fundamental depth sequences of only two’s or three’s. For a given depth sequence d(x) and a given column in the Betti table i ≥ 1, we wish to understand how many distinct domino monomials x have this depth sequence and correspond to a multi-graded Betti number in column i. Proposition 4.1. Given a domino monomial x = x{τ1,...,τm}, let a = (a1,a2, . . . ,a3k−2) where ai = δzi ({τ1, . . . ,τm}). For k ≥ 2, the number of domino monomials x with non-zero multi-graded Betti number βi,a(In) = 1 and depth sequence 2k is ( k−i−1 i−1 ) . Proof. If the depth of a domino monomial corresponding to a set of 2 ×k tilings is 2k, the first and last columns must contain the vertical dominos y1, yk and the horizontal dominos x1xk and xk−1x2(k−1). Therefore there are k − 2 remaining columns in which a choice of dominos can be made. Each of these 70 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 columns must be covered with one pair of horizontal dominos and either another pair of horizontal dominos or a vertical domino. We see if d(x) = 2k then sc(x) = 1 and so Proposition 3.7 gives if i = 1, then v(x) = 0 which corresponds to the one domino monomial x = x1x2 · · ·x2k−2y1yk containing all the horizontal dominos. Thus we satisfy the claim with ( k 0 ) = 1. For i > 1, choose i−1 pairs of non-intersecting horizontal dominos of the form xjxk−1+j to be replaced in the monomial by the pair yj,yj+1. These selections must be non-intersecting because removing both xjxk−1+j and xj+1xk+j leaves a depth of only 1 in column j + 1. Further, Proposition 3.6 notes that each of these replacements increases the dimension of the complementary complex by one and as there are ( k−2−(i−1) i−1 ) ways to choose i− 1 non-consecutive integers from the set [k − 2], we have the ( k−i−1 i−1 ) ways to choose the non-intersecting pairs of horizontal domino tiles enumerates the domino monomials corresponding to a non-zero ith multi-graded Betti number. In the proof of Proposition 4.1, we assumed 2k was a depth sequence corresponding to a domino monomial of a 2 × k rectangle. However, by adjusting indices the domino monomials can easily be modified to describe a factor of a 2 ×n domino monomial whose depth sequence contains a subsequence of k consecutive twos adjacent to a subsequence or subsequences of ones. Now consider fundamental subsequences of length k + 1 and k + 2 containing two’s or three’s and contained inside a larger length n depth sequence. First, a subsequence of threes, 3k, in columns j,j + 1, . . . ,j + k implies that all dominos, both horizontal and vertical, in those columns must be included in the monomial. Thus there is only one way to chose factors for the monomial in those positions. We know that subsequence of threes must be followed and preceded by a string of twos, so we need to understand how these threes affect the choice for an adjacent subsequence of twos. Proposition 4.2. Given a domino monomial x = x{τ1,...,τm}, let a = (a1,a2, . . . ,a3n−2) where ai = δzi ({τ1, . . . ,τm}). For k ≥ 2, suppose the partial depth sequence djdj+1 · · ·dj+k+1 is 32k1 or 12k3, respectively. Then, the number of factors f of x containing dominos from the set {xj, . . .xj+k,xj+n−1, . . . ,xj+k+n−1,yj, . . . ,yj+k} or {xj+1, . . .xj+k+1,xj+n, . . . ,xj+k+n,yj+1, . . . ,yj+k+1}, respectively, such that v(f) = i is ( k−i i−1 ) . Similarly, suppose the partial depth sequence djdj+1 · · ·dj+k+1 is 32k3. Then, the number of factors f of x containing dominos from the set {xj, . . .xj+k,xj+n, . . . ,xj+k+n,yj, . . . ,yj+k+1} such that v(f) = i is ( k−i+1 i−1 ) . Proof. Similar to the proof of Proposition 4.1, we observe that in the case the subsequence of twos is preceded or followed by a three we are allowed one more position in which xjxj+n−1 may be replaced with yjyj+1. Thus we have k−1 or k positions to choose i−1 non-intersection pairs of horizontal dominos to be replaced by pairs of vertical dominos and the result follows. These results now allow us to determine graded Betti numbers by listing all depth sequence created from a string of n ones using operations O1 and O2, separating these sequences into their fundamental subsequences, enumerating each subsequence using the results above, and finally multiplying. Example 4.3 illustrates this process. Example 4.3. Letting n = 7, suppose we wish to calculate βi,13. We write all possible combinations of 1’s, 2’s, and 3’s whose sum is 13 and were created from the sequence 17 using the operations O1 and O2 as 71 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 d(x) Multiplicity Count sc(x) i = 1 i = 2 i = 3 2222221 2 [( 4 0 ) + ( 3 1 ) + ( 2 2 )] · F1 1 2 6 2 2222122 2 [( 2 0 ) + ( 1 1 )] · F1 · ( 0 0 ) 2 2 2 2221222 1 ( 1 0 ) · F1 · ( 1 0 ) 2 1 2322211 2 ( 0 0 ) · [( 2 0 ) + ( 1 1 )] · F2 2 4 4 1232221 2 F1 · ( 0 0 ) · [( 2 0 ) + ( 1 1 )] · F1 2 2 2 1123222 2 F2 · ( 0 0 ) · [( 2 0 ) + ( 1 1 )] 2 4 4 2232211 2 ( 1 0 ) · ( 1 0 ) · F2 2 4 1223221 1 F1 · ( 1 0 ) · ( 1 0 ) · F1 2 1 233211 2 ( 0 0 ) · ( 0 0 ) · F3 3 6 1233211 2 F1 · ( 0 0 ) · ( 0 0 ) · F2 3 4 2321221 2 ( 0 0 ) · ( 0 0 ) · F1 · ( 0 0 ) · F1 3 2 2321122 2 ( 0 0 ) · ( 0 0 ) · F2 · ( 0 0 ) 3 4 1232122 2 F1 · ( 0 0 ) · ( 0 0 ) · F1 · ( 0 0 ) 3 2 2 24 32 We have β1,13(I7) = 2, β2,13(I7) = 24, and β3,13(I7) = 32. Figure 1. Possible depth sequences whose entries sum to 13 used to compute βi,13(I7) shown in the first column of the table in Figure 1. Keeping track of the starting column, we enumerate the subsequences by Propositions 4.1 and 4.2 and multiply. Note, the multiplicity column counts whether or not the reverse of the sequence is distinct from the original sequence. Thus β1,13(I7) = 2, β2,13(I7) = 24, and β3,13(I7) = 32. If we wish to disregard the column in the Betti table, we may use Fibonacci numbers to enumerate all domino monomials with a given depth sequence. Corollary 4.4. The number of domino monomials x with the depth sequence d(x) is given by the product of Counts for its fundamental subsequences as given in the table below. 72 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 Sequence Count 1k Fk 2k Fk−2 12k3 or 32k1 Fk−1 32k3 Fk 3k 1 The above corollary is a result of summing over all 0 ≤ i ≤b(k − 2)/2c and the identity Fk = bk/2c∑ j=0 ( k − j j ) , found in sequence A000045 of OEIS [15]. Example 4.5. Given the depth sequence d(x) = 2222333321112211232, in order to find the number of domino monomials x with this depth sequence we separate the monomial into its seven fundamental subsequences as follows: d(x) = 22223|33|32|111|22|11|232 Thus #{x|d(x) = 24342132212232} = F3 · 1 ·F0 ·F3 ·F0 ·F2 ·F0 ·F0 = 18. We make a final observation on the second column of the Betti table associated to the domino ideal. While the i = 0 column of the Betti table is given by Fibonacci numbers, the i = 1 column also has a nice description in terms of Fibonacci numbers. All domino monomials counted by multi-graded Betti numbers where i = 1 must come from one action of O1, that is, switching a consecutive sequence of ones into twos. Thus, sc(x) = 1 and consequently v(x) = 0 for any such monomial so there is only one choice of all the horizontal dominos for the tilings in the columns whose depth sequence is labeled with twos. Because we now only need to count the number of ways to tile the remaining region(s) labeled with ones, we have the following corollary. Corollary 4.6. In the minimal free resolution of the domino ideal In, the graded Betti numbers β1,j(In) are given by a convolution on the Fibonacci numbers, that is, β1,j(In) = 2n−j∑ k=0 FkF2n−j−k. References [1] A. Alilooee, S. Faridi, On the resolution of path ideals of cycles, Comm. Algebra 43(12) (2015) 5413–5433. [2] F. Ardila, R. P. Stanley, Tilings, Math. Intelligencer 32(4) (2010) 32–43. [3] P. K. Benedetto, A. N. Loehr, Domino tiling graphs, Ars Combin. 109 (2013), 3–29. [4] R. R. Bouchat, H. T. Hà, A. O’Keefe, Path ideals of rooted trees and their graded Betti numbers, J. Combin. Theory Ser. A 118(8) (2011) 2411–2425. [5] R. R. Bouchat, T. M. Brown, Multi-graded Betti numbers of path ideals of trees, J. Algebra Appl. 16(1) (2017) 1750018. [6] R. R. Bouchat, T. M. Brown, Minimal free resolutions of 2 × n domino tilings, J. Algebra Appl. online ready. 73 https://doi.org/10.1080/00927872.2013.837170 https://doi.org/10.1080/00927872.2013.837170 https://doi.org/10.1007/s00283-010-9160-9 https://mathscinet.ams.org/mathscinet-getitem?mr=3087200 https://doi.org/10.1016/j.jcta.2011.06.007 https://doi.org/10.1016/j.jcta.2011.06.007 https://doi.org/10.1142/S0219498817500189 https://doi.org/10.1142/S0219498817500189 https://doi.org/10.1142/S0219498819501184 https://doi.org/10.1142/S0219498819501184 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 6(2) (2019) 63–74 [7] S. Butler, P. Horn, E. Tressler, Intersection domino tilings, Fibonacci Quart. 48(2) (2010) 114–120. [8] A. Conca, E. De Negri, M-sequences, graph ideals, and ladder ideals of linear type, J. Algebra 211(2) (1999) 599–624. [9] N. Erey, S. Faridi, Multigraded Betti numbers of simplicial forests J. Pure Appl. Algebra 218(10) (2014) 1800–1805. [10] S. Faridi, The facet ideal of a simplicial complex, Manuscripta Math. 109(2) (2002) 159–174. [11] D. Grayson, M. Stillman, Macaulay2, a software system for research in algebraic geometry. Available at https://faculty.math.illinois.edu/Macaulay2/. [12] H. T. Hà, A. Van Tuyl, Monomial ideals, edge ideals of hyper graphs, and their graded Betti numbers, J. Algebr. Comb. 27(2) (2008) 215–245. [13] P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica 27(12) (1961) 1209–1225. [14] E. Miller, B. Sturmfels, Combinatorial Commutative Algebra, Springer-Verlag, New York, 2005. [15] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, (2018). [16] H. N. V. Temperley, M. E. Fisher, Dimer problem in statistical mechanics-an exact result, Philo- sophical Magazine, 6(68) (1961) 1061–1063. 74 https://www.fq.math.ca/Papers1/48-2/Butler_Horn_Tressler.pdf https://doi.org/10.1006/jabr.1998.7740 https://doi.org/10.1006/jabr.1998.7740 https://doi.org/10.1016/j.jpaa.2014.02.006 https://doi.org/10.1016/j.jpaa.2014.02.006 https://doi.org/10.1007/s00229-002-0293-9 https://faculty.math.illinois.edu/Macaulay2/ https://doi.org/10.1007/s10801-007-0079-y https://doi.org/10.1007/s10801-007-0079-y https://doi.org/10.1016/0031-8914(61)90063-5 https://doi.org/10.1016/0031-8914(61)90063-5 https://mathscinet.ams.org/mathscinet-getitem?mr=2110098 https://oeis.org https://doi.org/10.1080/14786436108243366 https://doi.org/10.1080/14786436108243366 Introduction Background Statistics Enumeration References