ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 18 (2020) 381-391 https://doi.org/10.26493/1855-3974.2239.7f1 (Also available at http://amc-journal.eu) The expansion of a chord diagram and the Genocchi numbers Tomoki Nakamigawa * Department of Information Science, Shonan Institute of Technology, Fujisawa, Kanagawa, Japan 4= Received 3 February 2020, accepted 21 April 2020, published online 24 October 2020 Abstract A chord diagram E is a set of chords of a circle such that no pair of chords has a common endvertex. Let vi, v2,..., v2n be a sequence of vertices arranged in clockwise order along a circumference. A chord diagram {v1vn+1, v2vn+2,..., vnv2n} is called an «.-crossing and a chord diagram {v1v2, v3v4,..., v2n-1v2n} is called an n-necklace. For a chord diagram E having a 2-crossing S = {x1x3, x2x4}, the expansion of E with respect to S is to replace E with E1 = (E \ S) U {x2x3, x4x1} or E2 = (E \ S) U {x1x2, x3x4}. Beginning from a given chord diagram E as the root, by iterating chord expansions in both ways, we have a binary tree whose all leaves are nonintersecting chord diagrams. Let NCD(E) be the multiset of the leaves. In this paper, the multiplicity of an n-necklace in NCD(E) is studied. Among other results, it is shown that the multiplicity of an n-necklace generated from an n-crossing equals the Genocchi number when n is odd and the median Genocchi number when n is even. Keywords: Chord diagram, chord expansion, Genocchi number, Seidel triangle. Math. Subj. Class. (2020): 05A15, 05A10 1 Introduction A set of chords of a circle is called a chord diagram, if they have no common endvertex. If a chord diagram consists of a set of n mutually crossing chords, it is called an n-crossing. A 2-crossing is simply called a crossing as well. If a chord diagram contains no crossing, it is called nonintersecting. Let V be a set of 2n vertices on a circle, and let E be a chord diagram of order n, where each chord has endvertices of V. In this situation, V is called a support of »This work was supported by JSPS KAKENHI Grant Number 19K03607. E-mail address: nakami@info.shonan-it.ac.jp (Tomoki Nakamigawa) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 382 Ars Math. Contemp. 18 (2020) 187-210 E. We denote the family of all chord diagrams having V as a support by CD(V). Let xi,x2,x3,x4 G V be placed on a circle in clockwise order. Let E G CD(V). For a crossing S = jxix3,x2x4} c E, let Si = jx2x3,x4xi}, and S2 = {xix2,x3x4}. The expansion of E with respect to S is defined as a replacement of E with Ei = (E \ S) U Si or E2 = (E \ S) U S2 (see Figure 1). xl x2 Figure 1: The expansion of a chord diagram with respect to a 2-crossing S. Other chords except those in S are not shown. Let E G CD( V) be a chord diagram. Form a binary tree as follows. Begin with E as the root, arbitrarily choose a crossing of E, and expand E in both ways, adding the results as children of E. Choose crossings in each child if any exists, expand them each in both ways, and repeat the procedure until all leaves are nonintersecting. This procedure terminates and the multiset of leaves is independent of the choices made at each step ([14]). Let us denote the multiset of nonintersecting chord diagrams generated from E by NCD(E). For a chord diagram E G CD(V), let us define the chord expansion number f (E) as the cardinality of NCD(E) as a multiset. For a chord diagram E, the circle graph, also called the interlace graph GE of E, is a graph such that a vertex of GE corresponds to a chord of E and two vertices of GE are joined by an edge if their corresponding chords of E are mutually crossing. We say that two chord diagrams Ei and E2 with a common support are isomorphic if GEl and GE2 are isomorphic as graphs. It is proved that f (E) equals t(GE; 2, -1), where t(G; x, y) is the Tutte polynomial of a graph G ([15]). In the case E is an n-crossing Cn, its associated circle graph is a complete graph Kn with n vertices. In [ ], Merino proved that t(Kn; 2, -1) — Euln+i for n > 1, where (Eul)„>i — (1,1, 2, 5,16,61, 272,...) is the Euler number. Hence, we have f (Cn) — Euln+i for n > 1. See also [12] for the evaluation of t(G; 2, -1) for a graph G. For two nonnegative integers k and n with k < n, we define A(n, k) as a chord diagram of order n + 1, in which there is an n-crossing E0 with an extra chord e such that e crosses exactly k chords of E0. (See Figure 2.) Note that A(n - 1, n - 1) is simply an n-crossing, and that A(n, 0) is a union of an n-crossing and an isolated chord. Let us denote {1, 2,..., n} by [n]. A permutation a on [n] is called an alternating permutation if (a(i) - a(i - 1))(a(i +1) - a(i)) < 0 for 2 < i < n - 1. An alternating permutation a is called an up-down permutation (resp. down-up permutation) if a(1) < a(2) (resp. a(1) > a(2)). For 0 < k < n, the Entringer number Entn,k is defined as the number of down-up permutations on [n + 1] with the first term k +1 ([11]). For n > 1, T. Nakamigawa: The expansion of a chord diagram and the Genocchi numbers 383 A(n, k) n - k Nn / \ V ) ^..... Figure 2: A(n, k) with n = 7 and k = 4 (left), and Nn with n = 8 (right). Entn+i,i equals Euln, the number of all down-up permutations on [n]. In [14], it is proved that f (A(n,k)) = Ent n+2,k+i. For a chord diagram E and for a nonintersecting chord diagram F with a common support, let us denote the multiplicity of F in NCD(E) by m(E, F). For a nonintersecting chord diagram E, a chord e G E is called an ear, if there is no other chord of E on at least one side of e. In [15], it is shown that for an n-crossing Cn and a nonintersecting chord diagram F with a common support, m(Cn, F) = 1 if and only if F has at most 3 ears. A nonintersecting chord diagram E with n chords is called an n-necklace, denoted by Nn, if all chords of E are ears. (See Figure 2.) The main purpose of the paper is to show that m(Cn,Nn) equals the Genocchi number when n is odd and the median Genocchi number when n is even. The Genocchi numbers and the median Genocchi numbers will be introduced in the following section. Recently, Bigeni showed a relation between a weight system of sl2 of chord diagrams and the median Genocchi numbers ([2]). In Definition 1 of [2], followed from [3], a weight system of sl2 is defined inductively by applying an operation for chord diagrams. The operation and the chord expansion are closely related to each other, although our main results in the paper do not seem directly followed from the results in [2]. The rest of this paper is organized as follows. In Section 2, the Genocchi numbers and the median Genocchi numbers are introduced. In Section 3, the main results of the paper are proved. In Section 4, another combinatorial interpretation for the multiplicity of n-necklaces is exhibited. Finally, in Section 5, some open problems are discussed. 2 The Genocchi numbers and the median Genocchi numbers According to [10], but with slightly different indices, let us recursively define the entry S(n, k) in row n > 1 and column k > 0 of the Seidel triangle ([17]): S(1,1) = 1, S(n, k) = 0 for k = 0 or n < 2(k - 1), S(2n,k) = E S(2n - 1,i) for 1 < k < n, (2.1) i>k S(2n +1,k) = E S(2n,i) for 1 < k < n + 1. (2.2) ii = (1,1, 3,17,155,...) and (H(2n + 1))n>0 = (1, 2, 8, 56, 608,...). Combinatorial properties of the Genocchi numbers have been extensively studied ([1, 4, 5,6, 7, 8,9,10,16,19]). It is known that the Genocchi number G(2n) counts the number of permutations a on [2n - 1] such that a(i) < a(i + 1) if a(i) is odd, and a(i) > a(i + 1) if a(i) is even ([6]). It is also known that the median Genocchi number H(2n + 1) counts the number of permutations a on [2n + 1] such that a(i) > i if i is odd and i = 2n + 1, and a(i) < i if i is even ([6]). In the on-line encyclopedia of integer sequences [18], we can find more information for the sequences A001469 (Genocchi numbers), A005439 (median Genocchi numbers), A099960 (An interleaving of the Genocchi numbers of the first and second kind) and A014781 (Seidel triangle). 3 Main results Our aim is to show a new combinatorial interpretation for the values of the Seidel triangle by using chord expansions. Let v0, v1,..., v2n+1 be a sequence of vertices in clockwise order along a circumference. Let V = [vi : 0 < i < 2n + 1}. As one of chord diagrams E G CD(V) isomorphic to A(n, k), introduced in the previous section, we have E = [v0vk+1} U [vivn+i+1 : 1 < i < k} U [vivn+i : k + 2 < i < n +1}. (See Figure 2.) Now let us define (n + 1)-necklaces and N-+1k g CD(V) such that N++ 1 k contains an ear vk v^+1 and N—+1 k contains an ear vk+1vk+2. The values of m(A(n, k), N++1 k) for n and k small are shown in Table 2. T. Nakamigawa: The expansion of a chord diagram and the Genocchi numbers 385 Table 2: m(A(n, k), N+ k) for 0 < k < n < 8 n \ k 0 1 2 3 4 5 6 7 8 0 1 1 1 1 2 1 1 1 3 1 1 2 2 4 2 2 3 3 3 5 3 3 6 6 8 8 6 8 8 14 14 17 17 17 7 17 17 34 34 48 48 56 56 8 56 56 104 104 138 138 155 155 155 Let us define 6+k = m(A(n k), N++i,k) and b-,k = m(A(n k) N„+i,k)- We also n+1,k n,k n+1,kz simply denote b+ k by bn,k. The main result of the paper is the following theorem. Theorem 3.1. Let n > 1. Then we have and b2n—1,k = S(2n, n — [k/2j) for 0 < k < 2n - 1, b2n,k = S(2n +1, [k/2j + 1) for 0 < k < 2n. (3.1) (3.2) A(n, K) >> vo n+k+1 A(n, k-1) A(n-1, n-k) v, n+k+1 Figure 3: A chord expansion of A(n, k) with respect to {v0vk+1, vkvn+k+1} with n = 7 and k = 3. Firstly, we show a relation between b- k and b+ k. Lemma 3.2. b b+,k-1for 1 < k < n. n,k n,k-1 v 386 Ars Math. Contemp. 18 (2020) 187-210 Proof. Let E be a chord diagram isomorphic to A(n, k), as shown in Figure 3. By the chord expansion of E with respect to {v0vk+1, vkvn+k+1}, we have two successors Ei and E2, which are isomorphic to A(n, k -1) and A(n -1, n - k), respectively. Since E2 contains a chord vk vk+1, it does not generate N—+1 k. Furthermore, since N—+1 k is a necklace having a chord vk-ivk, we have b_,k = m(A(n, k), N-+1,k) = m(A(n, k - 1),N++1,k_1) = b+k-1, as required. □ In order to prove Theorem 3.1, let us show arecurrence relation for bn,k. Lemma 3.3. We have b0j0 = 1 and for n > 1, we have bn,0 = bn,1 = bn_ 1,n_ 1, Jbnjk_2 + bn_1n_k for 2 < k < n and n is odd, bnk = N ' ' |bn , k_2 + bn_1, n_k_1 for 2 < k < n - 1 and n is even, bn , n = bn , n_2 for n is even. Proof. When k = 0,1 or n, equations bn ,0 = bn , 1 = bn_1 ,n_1 can be proved easily. Let us consider the case 2 < k < n. As in the proof of Lemma 3.2, we use the expansion of A(n, k) with respect to {voVk+1, VkVn+k+1}. If n is odd, we have b+,k = b_,k_1 + b+_1,n_k = bn,k_2 + bn_1,n_k . If n is even and k < n, we have b+,k = b_,k_1 + b__1,n_k = b+ + b+ = bn,k_2 + bn_1,n_k_1. Finally, if n is even and k = n, since b__10 = 0, we have bn,n = bn,n_1 + bn_1,0 = b+ = bn,n_2, as needed. □ Proof of Theorem 3.1. We proceed by induction on n and k. For (3.1) with n = 1, we have b1j0 = 1 and b1,1 = 1. On the other hand, we have S(2,1) = 1. For (3.2) with n = 1, we have b2 0 = 1, b21 = 1 and b2 2 = 1. On the other hand, we have S(3,1) = S(3, 2) = 1. Let n > 2. For k = 0, we have b2n_1,0 = b2n_2,2n_2 = S(2n - 1, n) = S(2n, n), T. Nakamigawa: The expansion of a chord diagram and the Genocchi numbers 387 and &2n,0 = &2n-1,2n-1 = S(2n, 1) = S(2n + 1,1). For k = 1, we have &2n-1,1 = &2n-1,0 = S(2n,n), and &2n,1 = b2n,0 = S(2n + 1,1). For (3.1) with 2 < k < 2n — 1, we have &2n-1,k = &2n-1,k-2 + &2n-2,2n-1-k = S(2n, n — L(k — 2)/2_|) + S(2n — 1, |(2n — 1 — k)/2j + 1) = S(2n, n +1 — |_k/2j) + S(2n — 1, n — |k/2j) = S(2n,n — |k/2j), and for (3.2) with 2 < k < 2n — 1, we have b2n,k = b2n,k-2 + b2n-1,2n-1-k = S(2n +1, |_(k — 2)/2j + 1) + S(2n,n — |(2n — 1 — k)/2j) = S(2n + 1, |_k/2j) + S(2n, 1 + |k/2j) = S (2n +1,1+ |k/2j), and for (3.2) with k = 2n, we have &2n,2n = &2n,2n-2 = S(2n + 1,n) = S(2n + 1, n +1). □ By Theorem 3.1, we have the following corollary. Corollary 3.4. m(C2n, N2n) = H(2n — 1) and m(C2n-1, Nin-1) = G(2n) for n > 1. Proof. By Theorem 3.1, we have m(C2n, N2n) = b2n-1,2n-1 = S(2n, 1) = H(2n — 1), and m(C2n-1, N2n-1) = &2n-2,2n-2 = S(2n — 1, n) = G(2n). □ 4 Multiplicity of an N-necklace and the number of perfect matchings of an associated graph In this section, we will exhibit a combinatorial interpretation of m(E, Nn) for a given chord diagram E. For a set V of vertices on the circumference, C (V) denotes the set of all 388 Ars Math. Contemp. 18 (2020) 187-210 chords whose endvertices are in V. A Ptolemy weight w on C (V) is defined as a function that satisfies w(xix3)w(x2x4) = w(x2x3)w(xix4) + w(xix2 )w(x3x4) (4.1) for all vertices xi, x2, x3, x4 G V placed along the circle. If w(e) is the Euclidean length of a chord e, then (4.1) holds by the Ptolemy's theorem in Euclidean geometry. Let w be a Ptolemy weight on C(V). If a chord diagram E G CD(V) has a 2-crossing S, by the chord expansion of E with respect to S, we have two successors Ei and E2. Then by (4.1), we have A w(e) = ^ w(e)+ n w(e). (4.2) e£E e£Ei e£E2 We denote the left-hand side of (4.2) by w(E). By iterating chord expansions with (4.2), we have w(E) = Y w(F). (4.3) F eNCV(E) Let V = {vi, v2,..., v2n}, where vi, v2,..., v2n are placed along the circumference in this order. A Ptolemy weight w on C(V) is called rectilinear if w(vjvj) = J2i 1 is maximal. Then the two variables xk and x^ do not appear together in the weight of any chord of F, otherwise such a chord would either intersect v2fc-iv2£ or contradict i — k being maximal. It follows that the product xkx^ never appears in w(F). This contradicts to that w(F) contains a monomial xix2... xn. □ For a chord diagram E having n chords ei, e2,..., en with the rectilinear Ptolemy weight w as defined in the above, let us define a balanced bipartite graph G(E, X) with partite sets A = {ai, a2,..., a„} and B = {bi, b2,..., bn} as follows. For 1 < i < n and 1 < j < n, a and bj are adjacent if and only if a polynomial w(e4) contains amonomial xj. Theorem 4.2. For a chord diagram E with n chords and its associated balanced bipartite graph G(E, X) as defined in the above, m(E, Nn) equals the number of perfect matchings of G(E, X). T. Nakamigawa: The expansion of a chord diagram and the Genocchi numbers 389 Proof. We have w(E) = f]e£E w(e), and for all chords e, w(e) =0 or w(e) = xj + xi+i + • • • + xj for some 1 < i < j < n. Hence, the coefficient of xix2... xn of w(E), which is m(E, Nn) by Lemma 4.1, is the number of possible combinations to choose a variable x g X from each w(e) without repetition. This is the number of perfect matchings of G(E,X ). □ graph G(E, X) (right). Example 4.3. Let n = 4. Let V = jvj : 1 < i < 2n}, where vi, v2,..., v2n are placed on the circumference in this order. Let us consider a rectilinear Ptolemy weight w on C( V) such that w(v2i-iv2i) = xj for 1 < i < n and w(v2iv2i+i) = 0 for 1 < i < n — 1. Let E = {ei : 1 < i < 4} be a chord diagram, where e1 = v1v6, e2 = v2v5, e3 = v3v7, e4 = v4v8. (See Figure 4.) Since w(E) = w(ej) = (xi + X2 + x3)x2(x2 + x3)(x3 + X4), 1