Applications of Combinatorial Analysis to the Calculation of the Partition Function of the Ising Model

Citation

Lin, Ming-Shr Matt (2009) Applications of Combinatorial Analysis to the Calculation of the Partition Function of the Ising Model. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/RSXD-6W47. https://resolver.caltech.edu/CaltechETD:etd-05052009-133119

Abstract

The research work discussed in this thesis investigated the application of combinatorics and graph theory in the analysis of the partition function of the Ising Model.

Chapter 1 gives a general introduction to the partition function of the Ising Model and the Feynman Identity in the language of graph theory.

Chapter 2 describes and proves combinatorially the Feynman Identity in the special case when there is only one vertex and multiple loops.

Chapter 3 digresses into the number of cycles in a directed graph, along with its application in the special case to derive the analytical expression of the number of non-periodic cycles with positive and negative signs.

Chapter 4 comes back to the general case of the Feynman Identity. The Feynman Identity is applied to several special cases of the graph and a combinatorial identity is established for each case.

Chapter 5 concludes the thesis by summarizing the main ideas in each chapter.

Item Type:	Thesis (Dissertation (Ph.D.))
Subject Keywords:	Feynman Identity; Graph theory; Ising Model; Partition Function
Degree Grantor:	California Institute of Technology
Division:	Physics, Mathematics and Astronomy
Major Option:	Physics
Minor Option:	Business Economics and Management Electrical Engineering
Thesis Availability:	Public (worldwide access)
Research Advisor(s):	Wilson, Richard M.
Thesis Committee:	Wilson, Richard M. (chair) Wales, David B. Preskill, John P. Cross, Michael Clifford
Defense Date:	21 April 2009
Record Number:	CaltechETD:etd-05052009-133119
Persistent URL:	https://resolver.caltech.edu/CaltechETD:etd-05052009-133119
DOI:	10.7907/RSXD-6W47
Default Usage Policy:	No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:	1641
Collection:	CaltechTHESIS
Deposited By:	Imported from ETD-db
Deposited On:	14 May 2009
Last Modified:	26 Nov 2019 20:23

Thesis Files

Preview

PDF - Final Version
See Usage Policy.
347kB

Repository Staff Only: item control page

Applications of Combinatorial Analysis to the Calculation of the Partition Function of the Ising Model Thesis by Ming-Shr Matt Lin In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2009 (Defended April 21st, 2009) ii c 2009 Ming-Shr Matt Lin All Rights Reserved iii Acknowledgements I would like to express my deep appreciation to Dr. Wilson. For without his support and encouragement, not to mention professional advice on my research, it would be impossible for me to go through the whole process. I learned not only how to do research in a professional manner, but also how he advised me in a patient and encouraging way. I would also like to thank Dr. Cross, Dr. Preskill, and Dr. Wales for serving my examination committee. Their presence and guidance during my defense will certainly increase my intellectual ability and provide me outlook for future opportunities. iv Abstract The research work discussed in this thesis investigated the application of combinatorics and graph theory in the analysis of the partition function of the Ising Model. Chapter 1 gives a general introduction to the partition function of the Ising Model and the Feynman Identity in the language of graph theory. Chapter 2 describes and proves combinatorially the Feynman Identity in the special case when there is only one vertex and multiple loops. Chapter 3 digresses into the number of cycles in a directed graph, along with its application in the special case to derive the analytical expression of the number of non-periodic cycles with positive and negative signs. Chapter 4 comes back to the general case of the Feynman Identity. The Feynman Identity is applied to several special cases of the graph and a combinatorial identity is established for each case. Chapter 5 concludes the thesis by summarizing the main ideas in each chapter. v Contents Acknowledgements iii Abstract iv 1 Introduction 1 1.1 Review of the Ising Model and its partition function . . . . . . . . . . . . . . . . . . 2 1.2 The partition function as a summation over graphs . . . . . . . . . . . . . . . . . . . 4 1.3 The partition function as a product over cycles: The Feynman Identity . . . . . . . . 5 2 A Combinatorial Proof of a Special Case of the Feynman Identity 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Proof of the identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Definition and properties of the sign function . . . . . . . . . . . . . . . . . . . . . . 12 2.4 More on the sign function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 The Number of Non-periodic Reduced Cycles in a Directed Graph 20 3.1 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 The number of non-periodic cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 The number of non-periodic cycles with specified occurrences of edges . . . . . . . . 23 3.4 Non-periodic cycles with positive and negative signs in the special case . . . . . . . . 25 4 Theorems Derived from the Feynman Identity 28 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 An alternative form of the Feynman Identity . . . . . . . . . . . . . . . . . . . . . . 29 vi 4.3 The first identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.4 A combinatorial lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.5 The second identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.6 Two more combinatorial lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.7 The third identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.8 The fourth identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.9 The fifth recursion relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5 Conclusion 5.1 Conclusion 49 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A The Number of Pointed Cycles in the Case of Two Loops 50 51 A.1 Relation with Costa’s equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 A.2 Derivation of the function for the number of pointed cycles f (a, b) . . . . . . . . . . 53 A.3 Comparison of the two functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 A.4 Combinatorial interpretation of fC (a, b) . . . . . . . . . . . . . . . . . . . . . . . . . 56 B Explicit Expression of the Feynman Identity When the Graph Is Connected B.1 A special case of (4.3) when the graph is connected . . . . . . . . . . . . . . . . . . . Bibliography 57 58 59 vii List of Figures 1.1 Ising Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1 Cotree with eight loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Illustrative graph for the change of revolution number . . . . . . . . . . . . . . . . . . 14 2.3 Illustrative graph for calculation of change of angles . . . . . . . . . . . . . . . . . . . 15 2.4 Interlacing graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 Daisy graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1 Chapter 1 Introduction 2 1.1 Review of the Ising Model and its partition function Graph theory has a natural application in the calculation of the partition function of the Ising model. We will review the partition function of the two-dimensional planar Ising model and the key step in the calculation, the Feynman Identity. The two-dimensional planar Ising model is defined on a square lattice Λ. Each site i of Λ contains Figure 1.1: Ising Model a ‘particle’ with two possible states. A generic example of this model is as follows: Consider a solid consisting of N identical atoms arranged in the regular lattice defined above. Each atom has a net ~ and associated magnetic moment µ ~ In the presence of an external applied electronic spin S ~ = gµ0 S. magnetic field Hz along the z direction, the Hamiltonian H representing the interaction of the atoms with this field is then H = −gµ0 N X j=1 S~j · Hz . (1.1) In addition, each atom is assumed to interact with neighboring atoms, but this is not just the magnetic dipole-dipole interaction. This interaction is in general too small to produce ferromagnetism. The dominant interaction is usually the exchange interaction, a consequence of the Pauli exclusion principle. We will focus on the spin-1/2 situation and adapt the standard notation σi , instead of S~i , to specify the spin state at site i. The interaction energy between two particles at the site i and j, each 3 in the state σi and σj respectively, is described by Eij =     −Jσi σj if i, j are nearest neighbors(n.n.)    0 (1.2) otherwise where J is a parameter that describes the strength of the interaction and it tends to fall off rapidly with increasing separation between two particles. Therefore, we consider only nearest neighbor interaction. When J is greater than zero, the state of lower energy will be the one which favors parallel spin orientation, i.e., one tends to produce ferromagnetism. 2 Suppose Λ has N 2 sites, then there are 2N distinct configurations of the spins. Call S = {σ} the set of all configurations of the system. The energy Eσ of each configuration σ ∈ S is given by Eσ = −J X σi σj (1.3) n.n.∈σ and the partition function is Z= X e−βEσ (1.4) σ∈S Since we will formulate everything in the language of graph theory, let’s call the site vertex from here on. We need two definitions before we state the main theorem. Definition 1: An even graph G is a graph whose vertex have even number of degrees. A even subgraph H of a graph K is a subgraph of K and H is an even graph itself. Definition 2: Given a graph G, define the single-variable polynomial related to G as IG (u) = u|E(G)| where |E(G)| is the total number of edges in G. (1.5) 4 1.2 The partition function as a summation over graphs For completeness, we will include the relevant part in [6] to show that the partition function can be written as a summation over even subgraphs. Theorem 1.2.1 Let A be the set of all even subgraphs of Λ which contains N 2 vertex, then 2 Z = 2N (1 − u2 )−N (N −1) X IG (u) (1.6) G∈A where u = tanh(K) and K = Jβ. Proof. Let’s rewrite the partition function (1.4) as Z= X ... σ1 =±1 X Y eKσi σj (1.7) σN =±1 n.n. by substitution of (1.3) into (1.4), where K = Jβ . Since σi σj = ±1, it follows that eKσi σj = e±K = cosh K ± sinh K; (1.8) therefore, Y n.n. = coshB K Y n.n. eKσi σj = Y n.n. cosh K ± sinh K −B (1 ± tanh K) = (1 − u2 ) 2 Y (1 + uσi σj ) n.n. −B where B = 2N (N − 1) is the number of bonds in Λ. The factor (1 − u2 ) 2 comes from 1 − tanh2 K = −B cosh−2 K; therefore, coshB K = (1 − tanh2 K) 2 . To each pair (i, j) of nearest neighbors of Λ, there corresponds a term uσi σj and an edge. Since the number of pairs (i, j) of nearest neighbors coincides with the number of bonds B of Λ, the 5 product on the right-hand side is a polynomial in u of degree B, that is , Y (1 + uσi σj ) = 1 + n.n. B X p=1 up X (σi1 σi2 ) . . . (σi2 p−1 σi2 p ). (1.9) n.n. The second summation, i.e., the summation over n.n., is over all possible products of p pairs of nearest neighbors of Λ where a pair is not to occur twice in the same product. Each pair (σi , σj ) is associated with an edge connecting vertices i and j; so each product of p pairs corresponds to a graph with p edges. We see that the second summation is over all graphs with p edges. The graph may have vertices of degree 0, 1, 2, 3, or 4, in the situation of the planar lattice. The summations over the spins, i.e., σi ’s, eliminates graphs containing any odd-degree vertex, because P P σi = 0 and σi3 = 0. The graphs left are those whose vertices all have even degrees. There is a factor of 2N because each vertex of Λ contributes a factor of 2 from P (even degree) σi 2 = 2, and the summations include all the σi ’s. Notice that in the proof, there is no need of planarity. We will get rid of the constant in front of the summation and call the summation as the partition function for simplicity. The even graph we have here is not the physical diagram of the lattice itself. It is a diagrammatic description of the proof above. For example, a vertex with degree 4 doesn’t mean that its corresponding site has a spin that is parallel to its four neighbors, but that it has appeared four times in the product. 1.3 The partition function as a product over cycles: The Feynman Identity In order to facilitate the calculation of the partition function and therefore predict the thermal properties of the lattice, it is more convenient to write it in a product form. Feynman conjectured 6 the following identity for a general graph embedded in a plane: X G∈A IG (u) = Y (1 + Jc (u)) (1.10) [c]∈P where σ(c) is the sign of the cycle [c], defined in Chapter 2, P is the set of non-periodic reduced cycles, defined in Chapter 3, and Jc (u) = σ(c)Ic (u). There have been a few articles on the Feynman identity [1][7] and its proof. The special case when there is only one vertex first appeared in Sherman[2], but there is no rigorous proof of the identity in that paper. In the special case, one can interpret the loops as generators and the cycles as word, as will be shown in the next chapter. Therefore, we can assign combinatorial meanings to both sides of the Feynman identity, and by double counting, the proof is done in a clear and short way. 7 Chapter 2 A Combinatorial Proof of a Special Case of the Feynman Identity 8 2.1 Introduction The identity stated as Theorem 2.1.1 below was given by S. Sherman [2] as a special case of the Feynman identity. This latter result has an involved geometric/topological proof. Sherman remarks in [2] that “a strictly algebraic and non-geometric proof of [this theorem] would be in order... Such an algebraic proof might shed light on the Ising problem in three dimensions.” Let Fk be the free group on k generators x1 , . . . , xk . A word w = a1 a2 · · · an in Fk , where each symbol ai is one of the generators x1 , . . . , xk or their inverses x1−1 , . . . , x−1 k , is circularly-reduced, or c-reduced, when ai+1 6= a−1 for i = 1, 2, . . . , n − 1 and also a1 6= a−1 n . It will be convenient to exclude i the identity in Fk as a c-reduced word. From here on, all words will be c-reduced, so we may skip the word when appropriate. Let ρ be the permutation of the c-reduced words that takes a1 a2 · · · an to an a1 a2 · · · an−1 . The images of powers of ρ on a word w are the rotations of w. A circular-word [w] is the set of all rotations of a given c-reduced word, i.e. an orbit of the cyclic group hρi generated by ρ on the set of c-reduced words in Fk . We remark that the circular-words are in one-to-one correspondence with the nontrivial conjugacy classes in Fk (every conjugacy class contains c-reduced words; two c-reduced word are conjugates if and only if one is a rotation of the other). As we switch to the formulation of a planar drawing of an oriented cotree in section 2.3, there is a natural correspondence between these two languages: each generator corresponds to a loop in the special case, and each cycle corresponds to a circular word, with two orientations considered as different. Sherman defines a sign σ(w) ∈ {1, −1} for every c-reduced word w. The definition will depend on an orientation of a planar drawing of a cotree (a graph with one vertex) with k loops labeled by the generators xi . The definition of sign is geometric (involving paths and angles) and we must deal with that. For the momment, we note only that the signs of a word and any of its rotations are the same, so that σ is well-defined on circular-words. The period of a word w (or circular-word [w]) is the least positive integer t so that ρt (w) = w. A word w or circular-word [w] of length n is said to be non-periodic when the period of w is n. Given ǫ = ±1, and nonnegative integers n1 , n2 , . . . , nk , let N (n1 , . . . , nk ; ǫ) denote the number 9 of non-periodic c-reduced circular-words [w] of length n = n1 + · · · + nk with σ(w) = ǫ, and which contain a total of ni of the symbols xi and x−1 for each i = 1, 2, . . . , k. i Theorem 2.1.1 In the ring of formal power series in k (commuting) indeterminates Z1 , Z2 , . . . , Zk , we have Y (1 + Z1n1 n1 ,··· ,nk ≥0 = · · · Zknk )N (n1 ,··· ,nk ;+) (1 − Z1n1 · · · Zknk )N (n1 ,··· ,nk ;−) k Y (1 + Zj ) 2 (2.1) j=1 where the product on the left is extended over all k-tuples (n1 , . . . , nk ) of nonnegative integers other than (0, 0, . . . , 0). The proof of Theorem 2.1.1 is given in Section 2.2. In Section 2.3 we derive the algebraic properties of σ we use in our proof, and in Section 2.4 we observe a further property that allows us to compute the sign of a c-reduced word combinatorially from the word and the cotree without any reference to paths and angles as in the original definition. The Witt Identity [3] concerns the numbers M (n1 , . . . , nk ) of non-periodic circular-words in the free semigroup generated by x1 , . . . , xk , with ni occurrence of xi for each i = 1, . . . , k. Following the notation of Theorem 2.1.1, Y n1 ,··· ,nk ≥0 (1 − Z1n1 · · · Zknk )M (n1 ,··· ,nk ) = 1 − Z1 − Z2 − · · · − Zk . (2.2) It is in view of (2.2) that (2.1) is called an Analogue of the Witt Identity in [2]. 2.2 Proof of the identity Properties of σ that we require for the proof are σ(xi ) = σ(x−1 i ) = +1 for every generator xi , (2.3) 10 and σ(ud ) = (−1)d−1 (σ(u))d for every c-reduced word u. (2.4) For ǫ = ±1 and nonegative integers n1 , . . . , nk , let W (n1 , . . . , nk ; ǫ) denote the number of creduced words (not circular-words) that have sign ǫ and a total of ni occurrences of xi or x−1 i , i = 1, 2, . . . , k. We will need to know that given n1 , n2 , . . . , nk , at least two of which are positive, we have W (n1 , n2 , . . . , nk ; +) = W (n1 , n2 , . . . , nk ; −). (2.5) Proofs of (2.3), (2.4), and (2.5) will be given in Section 2.3. Assuming these properties, the proof of Theorem 2.1.1 is purely combinatorial. We first give a relation between the numbers W (n1 , n2 , . . . , nk ; ±) and N (n1 , n2 , . . . , nk ; ±). Lemma 2.2.1 Given n1 , n2 , . . . , nk , not all zero, let g be the greatest common divisor of n1 , n2 , . . . , nk and write n = n1 + · · · + nk . Then W (n1 , n2 , . . . , nk ; +) = X d|g, d odd n1 n2 nk n N ( , , . . . , ; +), d d d d (2.6) and W (n1 , n2 , . . . , nk ; −) = X + Xn d|g, d even d|g d N( n1 n2 nk n N ( , , . . . , ; +) d d d d n1 n2 nk , , . . . , ; −). d d d (2.7) Proof. The period of a c-reduced word with ni occurrences of xi and x−1 will be of the form n/d i where d divides g. Given a divisor d of g, the c-reduced words with ni occurrences of xi and x−1 i , and period n/d, may be obtained as follows: Start with a representative u of a non-periodic c-reduced circular-word [u] of length n/d with ni /d occurrences of xi and x−1 and repeat it d times to get a i c-reduced word w = ud . Associate to [u] the distinct rotations of w, namely the first n/d rotations w, ρ(w), . . . , ρn/d−1 (w). 11 As d ranges over divisors of g, we obtain every c-reduced word w with ni occurrences of xi and x−1 exactly once in this way. By (2.4), the sign σ(w) of w = ud is (−1)d−1 (σ(u))d . If d is even, i σ(w) = −1. If d is odd, σ(w) = σ(u). Therefore, every word [u] in N ( nd1 , nd2 , . . . , ndk ; +) with d odd contribute n/d words in W (n1 , n2 , . . . , nk ; +), and the rest contribute to W (n1 , n2 , . . . , nk ; −). Proof of Theorem 2.1.1. It will suffice to prove that the formal logarithms of both sides of (2.1) are equal. The logarithm of the right-hand side is 2 ∞ k X X (−1)ℓ−1 j=1 ℓ=1 Zjℓ ℓ (2.8) and the logarithm of the left-hand side is X N (n1 , · · · , nk ; +) n1 ,··· ,nk ≥0 − X n1 ,··· ,nk ≥0 ∞ X (−1)ℓ−1 ℓ=1 N (n1 , · · · , nk ; −) (Z1n1 · · · Zknk )ℓ ℓ ∞ X (Z n1 · · · Z nk )ℓ 1 k ℓ ℓ=1 . (2.9) Given m1 , . . . , mk , let g be the greatest common divisor of m1 , . . . , mk and write m = m1 + · · · + mk . Then the coefficient of a monomial Z1m1 Z2m2 · · · Zkmk in (2.9) is X d|g 1 (−1)d−1 N (m1 /d, . . . , mk /d; +) d − X1 d|g d N (m1 /d, . . . , mk /d; −) (2.10) By Lemma 2.2.1, this is equal to 1 W (m1 , m2 , . . . , mk ; +) − W (m1 , m2 , . . . , mk ; −) . m (2.11) By (2.5), this is 0 in the case that at least two of the mi ’s are positive; that is, the coefficient of Z1m1 · · · Zkmk in (2.9) and (2.8) are the same in this case. m Now consider the coefficient of Zj j in (2.9), mj > 0. There are only two c-reduced words with m −mj mj occurences of xj or x−1 (and all other mi = 0), namely xj j and xj j . By (2.3) and (2.4), both of these have sign (−1)mj −1 . Then the quantity in (2.11) is equal to 2(−1)mj −1 /mj , which matches 12 m the coefficient of Zj j in (2.8). 2.3 Definition and properties of the sign function To define the sign function σ as in Sherman [2], we start with any planar drawing of an oriented cotree, a graph with one vertex v and k loops corresponding to the k pairs of generators and their ±1 inverse x±1 1 , . . . , xk . See Figure 2.1 as an example of cotree with eight loops. To each generator xi can be associated the closed path pi that traverses the corresponding loop, starting and terminating at v, following the oriention of the loop; and x−1 can be associated with the reverse path p−1 i i . For a c-reduced word w = xei11 · · · xeiℓℓ , the sign σ(w) is defined as (−1)r−1 where r is the number of revolutions made by the tangent vector to the associated path pei11 · · · peiℓℓ as the path is traversed. Note that different drawings may give different sign functions. For the definition of sign, it is convenient to assume the drawing of the graph is given so that x8 x6 x1 x2 x7 x4 x5 x3 v Figure 2.1: Cotree with eight loops the loops are represented by smooth closed curves with tangent vectors that vary continuously over ‘time’ as the loop is traversed, except perhaps at v, but where there is a limiting value at the beginning and end of each loop. If t1 (a unit vector in the plane) is the value of the tangent vector as the path nears the end of one loop and t2 is the value of the tangent vector as the path begins another loop, we must imagine a short time in which the tangent vector rotates from t1 to t2 either clockwise or counter-clockwise, whichever is the least motion, i.e. whichever motion goes through an angle of less than 180◦ . We may assume that the graph is drawn so that t1 = −t2 never arises 13 (which case would arise, e.g., if the word were not c-reduced). It is clear that the sign of a rotation of a c-reduced word is the same as the sign of the original word. It is also clear that σ(xi ) = σ(x−1 i ) = +1 for any generator xi . If the number of revolutions of the tangent vector made by traversing a path q associated with a c-reduced word u is r, then the number of revolutions of the tangent vector made by traversing q d is dr, and so σ(ud ) = (−1)dr−1 = (−1)d−1 (−1)d(r−1) = (−1)d−1 (σ(u))d . This establishes (2.3) and (2.4). Given a word w, let L(w) be the induced planar drawing of the set of loops corresponding to the symbols in w. A loop in L(w) is extremal in L(w) when it either contains no other loops in L(w), or contains all other loops in L(w). A symbol a, which is one of the generators xi or x−1 i , is extremal in w when it occurs in w and its corresponding loop is extremal in L(w). For example, if the drawing is as described in Figure 2.1 and w = x21 x−3 8 x6 x8 x2 , then the extremal symbols in w are x1 , x2 , x8 , x−1 8 . Lemma 2.3.1 Let a be a symbol in a c-reduced word w, say w = uak v, where k 6= 0 and the symbols on either side of a in the cyclic order are different from a. (That is, u does not terminate with a, and v does not terminate with a when u is empty. Similarly, v does not begin with a and u does not begin with a if v is empty.) If a is an extremal symbol in w, then σ(ua−k v) = −σ(uak v). Proof. First consider the case when k = 1. The diagrams in Figure 2.2, where we have suppressed the vertex v and made the paths continuous, are suggestive. It seems clear the trace of the tangent vector around one of the paths has one more revolution than the other, so that the signs will differ. But we should be careful, for example in the case c = b−1 below. To be more precise, let b be the symbol that appears before a (at the end of u, if u is nonempty) 14 a a−1 u v u v Figure 2.2: Illustrative graph for the change of revolution number and c the symbol that appears just after a (at the beginning of v, if v is nonempty). It is important that the loops corresponding to b and c are both outside or both inside the loop corresponding to a, and this is ensured by our choice of a as extremal in w. We illustrate the case when they are both outside. Label the angles α, β, γ, and δ as shown in Figure 2.3, all taken clockwise as positive. We allow c = b−1 , in which case δ = 0. The difference of the number of revolutions between uav and ua−1 v is {β + γ − (π − α)}/2π − {−α − β − δ + (π − γ − δ)}2π = 1 Figure 2.3 illustrates the case when all angles are smaller than π, but the calculation holds when one of them is greater than π. For example, when δ is greater than π, it would be more intuitive to write the difference as {−(δ − π)}/2π − {−2π − (δ − π)}/2π but since α + β + δ + γ = 2π, the result is the same. So the signs are different when k = 1. It is easy to see that σ(uak v) = (−1)k−1 σ(uav) and σ(ua−k v) = (−1)k−1 σ(ua−1 v), for positive integers k. Thus the theorem holds for any k. Proof of (2.5). Fix n1 , . . . , nk with at least two of the ni ’s positive; let n = n1 + · · · + nk . Let S be the set of c-reduced words w (not circular-words) in the free group generated by x1 , . . . , xk with ni occurrences of xi or x−1 i , i = 1, 2, . . . , k. We will define a (fixed-point-free) involutory mapping 15 b a α δ β c γ Figure 2.3: Illustrative graph for calculation of change of angles φ : S → S, so that σ(φ(w)) = −σ(w) for all w ∈ S. be an extremal symbol in w whose subscript i Given a word c-reduced word w ∈ S, let a = x±1 i is the least so that the corresponding loop in extremal in L(w). Find the first occurrence of a term ak in w and change it to a−k , and also change the exponent of any term aℓ at the end of w in the case that w begins with a, to get φ(w). For example, suppose the loops corresponding to x±1 1 and x±1 2 are the only extremal loops in L(w). Then −7 4 −2 7 φ(x43 x−2 2 x1 x4 ) = x3 x2 x1 x4 −5 −4 −2 7 7 5 and φ(x41 x−2 2 x1 x4 x1 ) = x1 x2 x1 x4 x1 . It is clear that φ2 is the identity and by Lemma 2.3.1, we have σ(φ(w)) = −σ(w). Remark. Even though the sign of a word depends on the particular drawing, both N (n1 , · · · , nk ; +) and N (n1 , · · · , nk ; −) are independent of the drawing. Of course W (n1 , · · · , nk ; ) = W (n1 , · · · , nk ; +)+ W (n1 , · · · , nk ; −) is independent of the drawing, and Lemma 2.3.1 shows that both W (n1 , · · · , nk ; +) and W (n1 , · · · , nk ; −) are independent of the drawing. Then by Lemma 2.2.1 and Möbius inversion, nN (n1 , n2 , . . . , nk ; +) = X d|g, d odd µ(d) W ( nk n1 n2 , , . . . , ; +), d d d (2.12) 16 nN (n1 , n2 , . . . , nk ; −) = X µ(d) W ( d|g, d odd nk n1 n2 , , . . . , ; −) d d d − T, (2.13) where T = 0 when g is odd and T = W ( n21 , n22 , . . . , n2k ; −) when g is even. Here µ(d) is the numbertheoretic Möbius function. Therefore, N (n1 , · · · , nk ; +) and N (n1 , · · · , nk ; −) are independent of the drawing. 2.4 More on the sign function The following lemma provides a combinatorial method for computing the sign of a word, with respect to any drawing of the cotree. Let w1 and w2 be c-reduced words. For i = 1, 2, let outi be a directed line segment starting at v and in the direction of the tangent to the path coresponding to wi as it leaves v. For i = 1, 2, let ini be a directed line segment terminating at v and in the direction of the tangent to the path corresponding to wi as it returns to v. There will be a circular order on the four line segments at v. We say that w1 and w2 interlace when in1 and in2 separate out1 and out2 in this order. Figure 2.4 shows one type of interlacing. Lemma 2.4.1 If w1 and w2 are c-reduced words so that w1 w2 is also c-reduced, then, with the above notation, σ(w1 w2 ) = +σ(w1 )σ(w2 ) if w1 and w2 interlace, and σ(w1 w2 ) = −σ(w1 )σ(w2 ) otherwise. Proof. First suppose that w1 and w2 interlace and let α1 , α2 , β1 , and β2 be the angles as indicated in Figure 2.4, as one of the possible situations. Others are similar and omitted. Let the number of ′ revolutions of wi be ri , and we separate it into two parts: 2πri = 2πri + αi . If r12 is the number of ′ ′ revolutions of w1 w2 , start from out1 , then 2πr12 = 2πr1 +β1 +2πr2 +β2 Since α1 +α2 −β1 −β2 = 2π, we get r12 = r1 + r2 − 1, which will yield the correct sign rule. Had we taken clockwise as positive direction, then all the four angles will change sign, but the final result is not affected at all. 17 In the case when in1 is at the “bottom” and in2 is at the “top”, then the calculation would be the same if α1 is still defined as the angle from in1 to out1 , β1 the angle from in1 to out2 , and similar for α2 and β2 . When w1 and w2 do not interlace, the proof is similar. β2 in1 α2 w1 w2 out2 out1 in2 β1 α1 Figure 2.4: Interlacing graph Here is an example of the computation of σ(x1 x2 x3 x4 x5 x6 x7 x8 ) when the cotree is as in Figure 2.1: σ(x1 x2 x3 x4 x5 x6 x7 x8 ) = (−)σ(x1 x2 x3 x4 x5 x6 x7 )σ(x8 ) = (−)(−)σ(x1 x2 x3 x4 x5 x6 )σ(x7 )σ(x8 ) = · · · = (−)(−)(+)(−)(+)(+)(−) = +. It is easy to see that every c-reduced word, involving at least two generators, can be written as the product of two c-reduced words, so Lemma 2.4.1, used successively, allows the computation of the sign of any word with respect to any drawing. In case that the cotree is the “daisy”, as the example shown in Figure 2.5 below, in the case of five loops, da Costa and Variane[5] have given an explicit rule to compute the sign of a c-reduced word, which we restate here as Theorem 2.4.2. We give a quick proof based on Lemma 2.4.1. 18 D2 D1 D3 D5 D4 Figure 2.5: Daisy graph e e ei Associated with each word w = Di1i1 Di2i2 · · · Dil l a sequence Sl = (i1 , i2 , · · · , il ), where Dij ’s are symbols. Let s be the number of negative exponents eij ’s. The sequence is such that a loop ij appears at least once in S, for all j = 1, 2, · · · , l, and ik 6= ik+1 and il 6= i1 . Decompose S into T subsequences such that, each subsequence is an ordered set of numbers formed in the following way: (a) if p, q are two elements inside the subsequence and q comes after p, then q > p; (b) a new subsequence begins whenever this ordering is broken in the sequence by two adjacent elements not satisfying (a). For instance, a sequence with three loops and l = 14 is decomposed as follows, with T = 7: S14 = (12123213232312) = (12)(123)(2)(13)(23)(23)(12). Theorem 2.4.2 (da Costa and Variane) Let N be the total number of symbols in w, then the sign of w is σ(w) = (−1)N +l+s+T +1 . e Proof. Recall that σ(Di1i1 ) = (−1)ei1 +1 , where Dj′ s are the counterclockwise loops as in Figure 2.5, we calculate the sign as we did in the previous example, and use induction on s and T. When s = 0 and T = 1, all the pairs in the calculation interlace, so e e ei e ei σ(Di1i1 Di2i2 · · · Dil l ) = (+)l−1 σ(Di1i1 ) · · · σ(Dil l ) = (−1)N +l . 19 When s = 0 and there is one increment of T in the word, the sign will gain one extra factor of (−1) from the non-interlacing case of Lemma 2.4.1, which yields the same sign rule as [5]. For each increment of s, which implies one of the loops is traversed in the opposite direction, then the interlacing will change to non-interlacing, or vise versa. 20 Chapter 3 The Number of Non-periodic Reduced Cycles in a Directed Graph 21 3.1 Outline In this chapter, we will switch to cycles in a general directed graphs. By combining with the result in Chapter 2 and adapting the theorem in this chapter to the special case when there is only one vertex, a method for deriving the analytic formula of the number of non-periodic cycles with positive and negative signs is developed. If there are only two loops adjacent to the vertex, the formula first appeared in Costa [4]. We use our method and derive the same expression as well in Appendix B. 3.2 The number of non-periodic cycles Given a directed graph D which may contain multiple edges and loops, let E(D) be the set of all edges of D. The origin of an edge e is the starting vertex and the end of e is the ending vertex. The inverse Inv(e) of e is the set of edges whose origin and end is the end and origin of e, respectively. If e is a loop, then e ∈ Inv(e). The successor E(e) of e is the set of edges whose origin is the end of e. If e is a loop, then Inv(e) ⊂ E(e). The proper successor P (e) of e is E(e)\Inv(e) when e is not a loop. When e is a loop, then P (e) is the same as E(e) . A pointed cycle p is a closed path in D with a specified starting edge, and a cycle [c] is the equivalent class of cyclic permutations of c. A (pointed) cycle is called reduced if there is no immediate reversal as it traverses through an edge that is not a loop. Since we consider the inverse of a loop is the same as itself, it is ok that the reduced cycle traverses through a loop multiple times. Only reduced cycles are considered, so we may omit the word when appropriate. Let ρ be the cyclic permutation of the pointed cycle c = e1 e2 ...ek , i.e. ρ(c) = ek e1 ...ek−1 , then the period of a cycle [c] is the least positive integer t so that ρt (c) = c. A cycle [c] of length M is said to be non-periodic when the period of [c] is M . A ℓ-cycle is a cycle of total length ℓ, i.e., the number of edges is ℓ. Lemma 3.2.1 Let T be a |E(D)| by |E(D)| square matrix whose entry t(ei , ej ) is 1 when ej is in the proper successor P (ei ) and zero otherwise. The diagonal entry t(ei , ei ) is 1 when ei is a loop 22 and 0 otherwise. Let ND (ℓ) be the number of non-periodic reduced ℓ-cycles in D. Then X ℓND (ℓ) = Tr(T M ). (3.1) ℓ|M Proof. To prove the lemma, we count the number of reduced pointed M -cycles in two different ways. First, given a divisor ℓ of M , a reduced pointed M -cycle w with period ℓ may be obtained as follows: Start with a representative c of a non-periodic reduced cycle [c] of length ℓ and repeat it M/ℓ times to get a reduced pointed cycle w = cM/ℓ . Note that the first ℓ cyclic permutations w, ρ(W ), ..., ρM/ℓ−1 (w) are different pointed cycles. By the definition of ND (ℓ), we conclude that the number of pointed M -cycles is P ℓ|M ℓND (ℓ). Here is the other way of counting. Let a and b be the edge of D. The (a, b)th entry of T M is T M (a, b) = X t(a, ei1 )t(ei1 , ei2 )...t(eiM −1 , b), ei1 ,ei2 ,...,eiM −1 which counts the number of M -paths from the origin of edge a to the end of edge b. Taking the trace of T M will ensure that only closed paths are counted and every starting edge is taken into account. Notice that a periodic cycle with period ℓ and total length M is also counted ℓ times in Tr(T M ) since , even though there are M entries, the number of different edges is ℓ. For example, if M = 6 and ℓ = 3, then the 6-cycle, say e1 e2 e3 e1 e2 e3 , is counted once by each of t6 (e1 , e1 ), t6 (e2 , e2 ), and t6 (e3 , e3 ). Lemma 3.2.2 Let µ() be the Mobius function. Then ND (M ) = 1 X M µ( )T r(T ℓ ) M ℓ (3.2) ℓ|M Proof. By the Mobius inversion formula, we can invert (3.1) to get M ND (M ) = X ℓ|M µ( M )T r(T ℓ ) ℓ (3.3) 23 Theorem 3.2.3 Define P as the set of non-periodic reduced cycles in a direct graph D and denote the length of its element [c] ∈ P by |c|. Then Y (1 − u|c| ) = det(I − uT ) (3.4) [c]∈P Proof. It will suffice to prove that the formal logarithms of both sides of (3.4) are equal. The logarithm of the left-hand side is ∞ XX u|c|ℓ [c]∈P ℓ=1 ℓ = ∞ X X 1 M =1 ℓ|M ℓ ND ( M M )u , ℓ where ND ( M ℓ ) has the same definition as above. The above equation comes from collecting terms that have the same power M . The logarithm of the right-hand side is log det(I − uT ) = Tr log(I − uT ) = Tr ∞ X (uT )ℓ ℓ=1 ℓ = ∞ X Tr(T M ) M =1 M uM . Comparing the coefficient of uM , we get the two sides of (3.1). 3.3 The number of non-periodic cycles with specified occurrences of edges Given a directed graph D which may contain multiple edges and loops, let ND (m1 , m2 , ..., m|E(D)| ) denote the number of non-periodic reduced cycles of length M = m1 + m2 + ... + m|E(D)| which contain mi of edge ei for each i = 1, 2, ..., |E(D)|. In order to keep track of the edges, every edge ei is assigned an indeterminate xi . Define S as a square matrix whose entries s(ei , ej ) is √ xi xj when ej is in the proper successor P (ei ) of ei and zero otherwise. For example, if D has only one vertex 24 with two loops, then   S=  x1 √ x1 x2  √ x1 x2  .  x2 mk 1 m2 in T r(S M ), Lemma 3.3.1 Let f (m1 , m2 , . . . , mk ) be the coefficient of a monomial xm 1 x2 ...xk where M = m1 + m2 + · · · + mk , and g is the g.c.d. of m1 , m2 , ..., mk , then XM ℓ|g ℓ ND ( m1 m2 mk , , ..., ) = f (m1 , m2 , . . . , mk ). ℓ ℓ ℓ (3.5) Proof. We count the number of reduced pointed cycles with mi occurrence of edge xi in two ways. First given a divisor ℓ of g, a reduced pointed cycle w with period ℓ and mi occurrence of xi , for all i’s, may be obtained as follows: Start with a representative c of a non-periodic reduced cycle [c] of length M/ℓ and repeat it ℓ times to get a reduced pointed cycle w = cℓ . By the definition of ND ( mℓ1 , mℓ2 , ..., mℓk ), we conclude that the number of pointed M -cycles with mi occurrence of xi is mk m1 m2 M ℓ|g ℓ ND ( ℓ , ℓ , ..., ℓ ). P Here is the other way of counting. In T r(S M ), the coefficient of mk 1 m2 is the number of pointed reduced cycles with mi occurrence of xi , for a monomial xm 1 x2 ...xk similar reasons as in Theorem 3.2.1. Theorem 3.3.2 Let Ic be the product of xi ’s that corresponds to the edges ei traversed by the cycle [c]. Then Y (1 − Ic ) = det(I − S). (3.6) [c]∈P Proof. This theorem is a generalization of Theorem 3.2.3 and the proof will follow a similar argument. The logarithm of the left-hand side is ∞ XX Ipℓ [c]∈P ℓ=1 ℓ = X X1 m1 ,m2 ,...,mk ℓ|g ℓ ND ( m1 m2 mk m 1 m 2 k , , ..., )x1 x2 ...xm k ℓ ℓ ℓ where g is the greatest common divisor of all mi ’s. Multiplying by M = m1 + m2 + ... + mk , we get mk 1 m2 equals the number of pointed M -cycles with mℓi occurrence of xi for the coefficient of xm 1 x2 ...xk i = 1, 2, ..., k. 25 The logarithm of the right-hand side is log det(I − S) = Tr log(I − S) = T r ∞ X SM M =1 M . mk 1 m2 equals the number of pointed M -cycles. After multiplying by M , the coefficient of xm 1 x2 ...xk This is because taking the trace will ensure the path is closed and different starting positions are counted accordingly. 3.4 Non-periodic cycles with positive and negative signs in the special case The analytical expression of the number N (m1 , m2 ; ±) of non-periodic cycles with signs in the special case of two loops is known[4], but there is no general expression when there are k loops, k > 2. Here we derive it as follows. From Lemma 3.3.1, we can reverse (3.5) and get ND (m1 , m2 , ..., mk ) = X µ(d) M d|g f (m1 /d, m2 /d, . . . , mk /d). (3.7) In order to apply this result to the special case as in Chapter 2, the directed graph now is a single vertex with loops embedded on a plane, and the inverse of the loop is always present and considered as different from itself due to the two orientations; therefore, it has to be excluded from the proper successor of itself. For example, the matrix S in the case of two loops, along with their inverse loops, is   x1    0  S=  √  x x  1 2   √ x1 x2 0 √ x1 x2 x1 √ x1 x2 √ x1 x2 x2 √ x1 x2 0 We will use this to calculate f (m1 /d, m2 /d) in Appendix A.  √ x1 x2    √ x1 x2   .   0    x2 (3.8) 26 If we define WD (m1 , m2 , ..., mk ) as the number of pointed reduced M -cycles in D with mi occurrence of ei for i = 1, 2, ..., k and M = m1 + m2 + ...mk , then, by a similar argument as Lemma 2.2.1, we get WD (m1 , m2 , ..., mk ) = XM ℓ|g ℓ ND ( m1 m 2 mk , , ..., ), ℓ ℓ ℓ where ND ( mℓ1 , mℓ2 , ..., mℓk ) is calculated in (3.7). The subscript D is to signify that WD (m1 , m2 , ..., mk ) applies to general directed graph. The function W (m1 , m2 , ..., mk ; ±), as defined in Chapter 2, applies to only the special case. Nonetheless, when we treat the special case as a directed graph and define W (m1 , m2 , ..., mk ) = W (m1 , m2 , ..., mk ; +) + W (m1 , m2 , ..., mk ; −), then W (m1 , m2 , ..., mk ) = WD (m1 , m2 , ..., mk ). Put together, W (m1 , m2 , ..., mk ) = WD (m1 , m2 , ..., mk ) XM = ℓ|g ℓ ND ( m1 m2 mk , , ..., ). ℓ ℓ ℓ Substitute (3.7) into the above expression to get X m1 X M X µ(d) m1 mk mk X ( f( , ..., )) = , ..., ) f( µ(d′ ) ℓ M/ℓ ℓd ℓd p p ′ ′ ℓ|g d|g p|g d |p where g ′ is the greatest common divisor of mi /ℓ. By using the property of the Mobiüs Function: X d|n µ(d) =     1    0 if n = 1 otherwise 27 we derive W (m1 , m2 , ..., mk ) = f (m1 , ..., mk ). (3.9) The reason we introduce the function WD (m1 , m2 , ..., mk ) is to help us connect with the function N (m1 , m2 , . . . , mk ; ±), which is defined in Chapter 2. Because W (m1 , m2 , ..., mk ; +) = W (m1 , m2 , ..., mk ; −), as proved in Chapter 2, we have W (m1 , m2 , ..., mk ; +) = W (m1 , m2 , ..., mk ; −) = W (m1 , m2 , ..., mk )/2. (3.10) If we replace W (m1 , m2 , ..., mk ; ±) in (2.12) and (2.13) by (3.10) and use W (m1 , m2 , ..., mk ) = f (m1 , ..., mk ), we have N (m1 , m2 , . . . , mk ; +) = X d|g, d odd µ(d) f (m1 /d, m2 /d, . . . , mk /d), 2M (3.11) and N (m1 , m2 , . . . , mk ; −) = X d|g, d odd µ(d) f (m1 /d, m2 /d, . . . , mk /d) − 2M T (3.12) where T = 0 when g is odd and T = W ( m21 , m22 , . . . , m2k ; −) when g is even. In principle, the function f (m1 , ..., mk ) can be calculated from its definition; therefore, we can derive expressions for N (m1 , m2 , ..., mk ; +) and N (m1 , m2 , ..., mk ; −). We also show in Appendix A that (3.11) and (3.12) reduce to the expression in Costa [4] in the case of two loops. 28 Chapter 4 Theorems Derived from the Feynman Identity 29 4.1 Introduction We will apply the Feynman Identity to certain graphs to derive combinatorial identities involving binomial numbers. A rigorous proof of each identity is provided separately. The Feynman Identity can be presented as X G∈A G(xi ) = Y (1 + Jc (xi )), (4.1) c∈P where xi is the indeterminate corresponding to the edge ei , A is the set of even simple subgraphs, and G(xi ) = Q mi where mi is the multiplicity of ei in the subgraph G. Since G is a simple graph, i xi mi here equals either one or zero, but in general it is some non-negative number. For simplicity, G is used to denote both the subgraph in A and the corresponding monomial. On the right hand side, c is a class of non-periodic paths and P is the set of equivalent classes up to the “starting point” and orientation. For example, a C4 is a path that has four starting point and after accounting for orientations, there are eight paths and they belong to the same class. Jc (xi ) = σ(c) Q mi where i xi mi is the multiplicity of ei in c and σ(c) is the sign of c as defined in Chapter 2. For future reference, we will call the left hand side of (4.1) the graph side and the right hand side the path side. 4.2 An alternative form of the Feynman Identity The Feynman Identity can be rewritten by taking logarithm on both sides of (4.1) and comparing the coefficient of the monomial mi where i runs over the non-zero mi ’s. After taking logarithms, i xi Q the coefficient on the path side is again 1 (W (m1 , m2 , ..., mk ; +) − W (m1 , m2 , ..., mk ; −)), M as in the special case in Chapter 2. This is because the relation between N (m1 , ..., mk ; ±) and W (m1 , ..., mk , ±) remains the same in the general case and the definition of the sign function is 30 valid as long as the graph is embedded in a two-dimensional orientable manifold. The logarithm on the graph side, after Taylor expansion, is X A\∅ ∞ X 2 1 X 3 B 1 X (−1)B+1 X G(xi ) + G(xi ) − ... = Gj (xi ) G(xi ) − 2 3 B j A\∅ (4.2) B=1 A\∅ where each of the summations on the left is over the set A\∅ of non-empty even simple subgraphs. So the identity can be rephrased as the following: Let [f (x1 , x2 , ..., xk )]xm1 xm2 ...xmk denote the 1 2 k mk 1 m2 in the polynomial f (x1 , x2 , ..., xk ). Then coefficient of the monomial term xm 1 x2 ...xk h X A\∅ = 4.3 i 1 X 2 1 X 3 G(xi ) − G(xi ) + G(xi ) − ... m1 m2 mk 2 3 x1 x2 ...xk A\∅ A\∅ 1 W (m1 , m2 , ..., mk ; +) − W (m1 , m2 , ..., mk ; −) . M (4.3) The first identity The first identity we will derive is in the following theorem. Theorem 4.3.1 Let y1 , y2 , ..., yL be positive intergers and X a positive number such that X − 1 ≥ PL ℓ=1 yℓ . Then max{yi } X X (−1)B+1 X B=1 B j=B (−1)B+j B j j j ... = 0, j y1 y2 yL (4.4) where the inner summation over j goes in a decreasing order. (The reason for the decreasing order will become clear in the proof.) Proof using the Feynman Identity. Define the degree-star deg∗ (vi ) of a vertex vi as the number of edges incident with vi and counting multiple edges as 1. For example, if there are totally three edges incident with vi but two of them are mulple edges, then deg ∗ (vi ) = 2. We will look into the case when deg ∗ (vi ) ≤ 2 for all vi ’s. Given a set of parameters {mi } which specifies the number of occurrence of each edge ei , let G{mi } be the graph with edge ei of multiplicity mi . When G{mi } is connected and all mi ’s are 31 equal to, say, m, then the path side of (4.3) has nonzero coefficient. In this case, both sides equal (−1)(m+1) /m. This is explained in Appendix B. When G{mi } is not connected, let the number of components be L. Since deg ∗ (vi ) ≤ 2 for all vertices, each of the component Cℓ of G{mi } is actually a closed path repeated, say yℓ times, ℓ = 1, 2, ..., L, where yℓ = mi if ei ∈ Cl . Without lose of generality, let y1 ≥ y2 ≥ ... ≥ yL ≥ 1. The coefficient of Q mi in the term i xi P y1 X B A\∅ G(xi ) (−1)B+j j=B is B j j j ... . j y1 y2 yL (4.5) Notice that the summation over j goes in a decreasing order because we use inclusion-exclusion principle, which is explained in the next paragraph. The first term j = B comes from the following. First we choose yℓ out of B factors in the term X A\∅ B G(xi ) to compose the repeated component Cℓ . Because each individual factor contains subgraphs as the direct composition of several Ci ’s, we can choose them “without replacement”. But since the summation over A\∅ does not contain the empty graph, which corresponds to 1, each factor has to contribute at least one component. We may use the inclusion-exclusion principle to get rid of those terms that contribute less than B factors. The range of B for which the coefficient of of all yℓ ’s, to P Q mi is nonzero goes from y1 , i.e., the maximum i xi ℓ yℓ . The lower value y1 comes from the fact that the set A\∅ contains only simple graphs without repeated edges, so we need at least y1 factors to compose C1 repeated y1 times. The upper value comes from the fact that, if each factor contributes exactly one component, which is the most “spread-out” situation, then the total number of factors equals the total number of components, counting multiplicities, which is P ℓ yℓ . 32 The above expression in (4.5) is the coefficient of Q mi from the term i xi P B A\∅ G(xi ) . If we sum over all B’s, then the left hand side of (4.3) becomes y1 X X (−1)B+1 X B B=1 (−1)B+j j=B B j j j ... , j y1 y2 yL (4.6) where X is some finite number such that all nonzero terms are taken into account. When B is larger than P P ℓ yℓ , because each factor of the term we need only P B A\∅ G(xi ) ℓ yℓ , the coefficient from the term P has nonzero contribution and totally B A\∅ G(xi ) has to be zero. Therefore the inner summation over j in (4.6) becomes zero when B is larger than P ℓ yℓ . This is the expression we get from the graph side. We can see easily that the path side of (4.3) is zero. Since G{mi } is not connected, there is no way to traverse it in one stroke. So both W (mi ; +) and W (mi ; −) are zero. Alternative proof. Since for all j < y1 , the expression (4.5) is zero, we rewrite the summation index j as from 1 to B. After interchanging the order of summation, we have B X X 1 X B=1 = B j=1 (−1)j+1 X X X X 1 B j=1 B=j B j B j j j ... j y1 y2 yL (−1)j+1 j j j ... . y1 y2 yL (4.7) By using the identity (1.52) in [8], the inner summation on the right hand side of (4.7) can be written as X X 1 B B=j B j = X X B−1 X X −1 j =j =X . j−1 j j−1 B=j Subsituting back into (4.7), we get X X (−1)j+1 X j=1 =X X−1 X k=0 (−1)k X −1 j−1 X −1 k j j j ... y1 y2 yL k+1 k+1 k+1 ... . y1 y2 yL (4.8) 33 Use the identity (x.16) in [8] n X (−1)k k=0 n a1 + b1 k a2 + b2 k ar + br k ... = 0, k m1 m2 mr (4.9) with the condition 0 ≤ m1 + m2 + ... + mr ≤ n. Substitute with n = X − 1, r = L, mi = yi , and ai = bi = 1 for all iin (4.9) to see that this is exactly the expression in (4.8). The condition on X is also satisfied since X − 1 ≥ P yi , so the expression in (4.4) is zero. This complete the prove of the first theorem. We make some preliminary remarks before we state the second theorem. 4.4 A combinatorial lemma Suppose there are A different objects, A ≥ 2, and R of them are special. We want to partition them into B different baskets with the following rule: (1) None of the basket are empty and (2) the R special objects arein different baskets. Only when B ≤ A can the first rule be satisfied and only when R ≤ B can the second one be satisfied; so the number of partition is nonzero only when R ≤ B ≤ A. A real life example may be, during Easter, we want to put R eggs into different baskets. None of the eggs are the same but we want to have at most one egg in each basket. The rest of the objects are candies and they can go to any basket. All the baskets must be nonempty. We can partition the A objects in the following way. To partition the R special objects, or the eggs in the previous example, choose R baskets out of B, so there are B R R! ways of partition. Take J objects out of the rest of the A − R objects, which are the candies in the previous example, and fill up the rest of the B − R baskets. Since none of them is allowed to be empty, J ≥ B − R. The rest of the A − R − J objects then can go into any of the first R baskets. Let F (N, k) denote the number of distributions of N different objects into k different nonempty basket. Then the number 34 of the partitions of the candies is A−R X J=B−R A−R F (J, B − R)RA−R−J . J Combined together, the total number of distribution, denoted by D(A, R; B), is D(A, R, B) = A−R X A − R B F (J, B − R)RA−R−J . R! J R (4.10) J=B−R Notice that each term in the summation is mutually exclusive due to the total number of candies in the no-egg baskets. If we denote the Stirling numbers of the second kind by S2 (N, k), which is the number of distributions of N different objects into k identical baskets, then F (J, B − R) = (B − R)!S2 (J, B − R). Here is an interesting identify about D(A, R; B). Lemma 4.4.1 Based on the definition of D(A, R; B) and with the condistion that A > R, A X (−1)B+1 B B=R D(A, R; B) = 0. (4.11) Proof. Let the above summation be G(A, R) and substitute the expression for D(A, R; B) in (4.10) into (4.11) to obtain G(A, R) = A X (−1)B+1 B B=R B R R! A−R X J=B−R A−R F (J, B − R)RA−R−J . J Replace F (J, B − R) by (B − R)!S2 (J, B − R) and rearrange the terms to get G(A, R) = R A−R A X A−R X B=R J=B−R A−R (−1)B+1 B! S2 (J, B − R)R−J . B J 35 Interchange the two summations along with the proper summation ranges to get G(A, R) = RA−R A−R X X R+J J=0 B=R A−R (−1)B+1 (B − 1)!S2 (J, B − R) R−J . J Let b = B − R and put those terms related to b together: G(A, R) = RA−R (−1)R+1 A−R X J=0 J X A−R R−J (−1)b (b + R − 1)!S2 (J, b). J b=0 The second summation can be simplified using the generating function of S2 , which we will prove later: J X b=0 (−1)b (b + R − 1)!S2 (J, b) = (−R)J (R − 1)!. (4.12) Therefore, G(A, R) = RA−R (−1)R+1 A−R X J=0 A−R R−J (−R)J (R − 1)!. J Notice that R−J (−R)J = (−1)J , so the part of summation over J becomes A−R X J=0 A−R (−1)J = (1 − 1)A−R = 0. J This completes the proof of (4.11). To finish the story we come back to (4.12) and use the generating function of the Stirling numbers of the second kind: xJ = J X b=0 S2 (J, b)x(x − 1)...(x − b + 1). (4.13) Let x = −R in (4.13) and notice there are b terms following S2 (J, b) on the right-hand side: (−R)J = J X b=0 S2 (J, b)R(R + 1)...(R + b − 1)(−1)b . (4.14) 36 Complete the factorial by multiplying both sides by (R − 1)!. Then (4.14) becomes (4.12): (−R)J (R − 1)! = J X b=0 (−1)b (R + b − 1)!S2 (J, b). 4.5 The second identity Recall that G{mi } is the graph with edge ei of multiplicity mi . A repeated edge is one that has multiplicity greater than one. We can decompose G{mi } into a set of subpaths S = {pj } such that (1) the degrees of the vertices of pj all equal two for all j and (2) the disjoint union of the edge set E(pj ) is E(G{mi } ); here disjoint means that the repeated edges in different edge set is not eliminated as we combine them together. Define A as the number of paths in S, i.e., A = |S|, and notice that A ≥ 2 when there exists at least one vertex vj with deg ∗ (vj ) > 2. Use a decomposition matrix SA×|E(G{mi } )| to denote the decomposition where Si,j = 1 when the sub-path pi resulting from the decomposition S contains edge ej and Si,j = 0 otherwise. Given a graph G{mi } , there may be different ways of decomposition that satisfy the above rule, and we will use a subcript, i.e., Si to denote the set and Si to denote the matrix when necessary. After the decomposition, there are A subpaths, and it is desired to partition them into B parts, which we will call the egg-candy partition procedure (the name is inspired from the Easter example in the previous section): Partition the elements of the set S into B parts and put them into B different baskets such that no two subgraphs in the same basket have common edges. This way, the direct composition of the subpaths in the same basket corresponds to a unique even subgraph in the term P j Gj (xi ). Therefore, each choice of the above procedure contributes 1 to the coefficient of Q mi i xi . In view of the Easter example, those subpaths that have common edges are treated as eggs with common features, and they are not supposed to go to the same basket; eggs that have no features in common then can go to the same basket. Those subpaths without any repeated edges are candies and they can be in any basket. 37 For example, if S = {p1 , p1 , p2 , p2 } where p1 and p2 do not have any common edge, so p1 and p2 are different kinds of eggs, but the two p1 ’s are considered the same kind of eggs. If B = 2, then the only elligible partition is to put p1 and p2 into the same basket, and repeat it again for the second P Q i basket. Therefore the term ( j Gj (xi ))B contribute 1 to the coefficient of i xm when B = 2. i This is because one can always find the unique subgraph, say Gj , which has exactly the same edge set as the disjoint union of E(p1 ) and E(p2 ) and the same subpaths cannot be put together in the same basket since the subgraphs are simple ones. If B = 3, There are 3! different ways to assign {{p1 , p2 }, {p1 }, {p2 }} into three different basket, so the total contribution is 3!. If B = 4, then there are 4!/2!2! different partitions. If p1 and p2 have any edge in common, then the total is 4!/2!2! when B = 4 and zero otherwise. Let D(S; B) be the coefficient of Q mi in the term i xi P B j Gj (xi ) contributed from the decom- position S. For example, take S = {p1 , p1 , p2 , p2 } in the above paragraph where p1 and p2 don’t have any common edge, then D(S; 2) = 1, D(S; 3) = 3, and D(S; 4) = 6. Theorem 4.5.1 Suppose the decomposition S is such that the matrix S has only one column with more than one nonzero entry, i.e., there is only one edge ei with mi = R > 1, and the other mi ’s equal 1. Then A X (−1)B+1 B=R B D(S; B) = 0, (4.15) where A is the number of rows of S. Proof using the Feynman Identity. Based on the discussion of D(S; B), the coefficient of Q mi i xi on the graph side of (4.3) is ∞ X (−1)B+1 B=1 B D(S; B). So the alternative form of the Feynman Identity becomes ∞ X (−1)B+1 B=1 B D(S; B) = 1 W (m1 , m2 , ..., mk ; +) − W (m1 , m2 , ..., mk ; −) . M (4.16) Since the nonzero terms start from B = R to B = A, (4.16) actually has the same expression as 38 (4.15) on the left hand side. We know that if there is any repeated edge, then the path side of the Feynman Identity (4.3) is zero. To be specific, because the paths are not allowed to go backward immediately, we can shrink the repeated edge eR by connecting the vertices of eR as a single vertex, and the situation is equivalent to the special case when there is a single vertex with several loops; therefore, we have a one-to-one mapping between the positive- and negative-sign paths. Alternative proof. In the case when the decomposition S produces |A| subpaths and R of them have a common repeated edge, and there is no other repeated edge, D(S; B) is the same as D(A, R; B) in the previous section. Again, the nonzero term starts from B = R and ends at B = A, as explained in the previous section. So the graph side of the Feynman Identity is same as the left hand side of (4.11) in Lemma 4.4.1. By Lemma 4.4.1, we know that this expression is zero. 4.6 Two more combinatorial lemmas Lemma 4.6.1 Let m be a positive integer and x is a positive number. Then m X k=0 m+x+k m+x (−1)k =0 m+x+k k m−k (4.17) Proof. Consider the first term when k = 0. The left hand side of (4.17) can be written as m X k=1 m+x+k m+x m+x m+x 1 (−1)k . + m+x+k k m−k m+x 0 m So we will prove that m X k=1 −1 m+x+k m+x m+x (−1)k . = m+x+k m+x k m m−k (4.18) 39 Use n n−1 n , = t t−1 t (4.19) to get 1 m+x+k−1 m+x+k 1 = . m+x+k k k k−1 So the summation in (4.18) becomes m X (−1)k m + x + k − 1 m + x k−1 k k=1 m−k . (4.20) We need to deal with (−1)k . Using the definition −z k = 1 (−z)(−z − 1)...(−z − k + 1), k we get the following identity: −z k k = (−1) z+k−1 . k (4.21) So (k−1) (−1) −(m + x + 1) m+x+k+1 (k−1) (m + x + 1) + (k − 1) + 1 = . = (−1) k−1 k−1 k−1 Substitute this expression back into the summation in (4.20), the expression (4.18) becomes m X (−1)k m + x + k − 1) m + x k=1 k k−1 m−k = m X −1 −(m + x − 1) m + x k=1 k−1 k m−k . Using (4.19) again with n = −(m + x) and t = k, we get m X k=1 m X −1 1 −(m + x) m + x −(m + x) m + x = . −(m + x) (m + x) k m−k k m−k k=1 40 If we add and subtract the term k = 0, we get m X −(m + x)) m + x −(m + x) m + x 1 . − (m + x) k m−k 0 m k=0 Using m X a k k=0 b m−k = a+b , m which is true for general a and b, we see that the first summation becomes (4.22) 0 m , which equals zero. So put together, the left hand side of (4.18) becomes −1 −(m + x) m + x m+x 1 0− , = (m + x) m+x 0 m m which is the right hand side of (4.18) Lemma 4.6.2 Let m be a positive integer and x a positive number. Then m X (−1)k k=0 m+x+k−1 m+x = 0. k m−k (4.23) Proof. We will use (4.21) again to get (−1)k m+x+k−1 k = −(m + x) . k So the summation becomes m X (−1)k k=0 X m −(m + x) m + x m+x+k−1 m+x , = k m−k k m−k k=0 which is zero by (4.22). We will use both lemmas in the proof of the following theorem. 41 4.7 The third identity Suppose that after the decomposition, every subpath contains exactly one repeated edge. For example, if p1 , p2 , and p3 have the common edge e1 , and p4 , p5 have the common edge e2 , then the upper left part of the decomposition matrix S looks like the following:   1    1     1     0     0     0    . .. 0 0 0 1 1 0 .. .  ···    ···     ···     ···     ···     ···    ..  . Let the multiplicity of edge ei be Ri , i = 1, 2, ..., n, and let the coefficient in the Bth term P ( j Gj (xi ))B be D(R1 , R2 , ..., Rn ; B). We use D(R1 , R2 , ..., Rn ; B) instead of D(S; B) since we will need the recursion relation on n. Without loss of generality, let R1 ≥ R2 ≥ ... ≥ Rn ≥ 2. Theorem 4.7.1 Let D(R1 , R2 , ..., Rn ; B) be defined as in the last paragraph. Then R1 +RX 2 +...+Rn B=R1 (−1)B+1 D(R1 , R2 , ..., Rn ; B) = 0. B Proof using the Feynman Identity. Since the expression for the coefficient of (4.24) Q mi i xi is D(R1 , R2 , ..., Rn ; B), the left hand side of (4.24) is the same as the graph side of (4.3). Again, the nonzero terms start from B = R1 to B = A. Also we know that the whenever there is repeated edge, the path side of the Feynman Identity yields zero. Therefore, the summation result is zero. Alternative proof. We will prove the identity using induction, and the base case is when n = 2. For simplicity of notation, we will use (4.25), an expression for D(R1 , R2 ; B), to prove (4.24) when n = 3, instead of general n, but the procedure is similar. 42 Here is the expression for D(R1 , R2 ; B): D(R1 , R2 ; B) = B R1 R2 (R2 − (B − R1 ))!. (B − R1 )! R1 ! R2 − (B − R1 ) B − R1 R1 (4.25) This is because to put R1 + R2 objects into B non-empty different baskets, where only for B = R1 , R1 + 1, ..., R1 + R2 is the expression nonzero, such that none of the first kind of R1 objects are in the same basket, and neither are the second kind of R2 objects, we choose R1 out of B baskets and fill them with the first R1 objects. Since the baskets are different, we need the factor of R1 !. Then we choose B − R1 out of R2 second kind of objects and put into the rest of the baskets. For the rest R2 − (B − R1 ) second kind of objects, they need to go into the baskets filled with the first kind of objects. We can prove (4.24) in the case when n = 2 by substituting (4.25) into the summation in (4.24). Let k = B − R1 . Then (4.24) becomes RX 1 +R2 (−1)B+1 D(R1 , R2 ; B) B RX 1 +R2 (−1)B+1 B R2 R1 (R2 − (B − R1 ))! R1 ! (B − R1 )! B R1 B − R1 R2 − (B − R1 ) B=R1 = B=R1 = R2 X (−1)k+R1 +1 R1 + k k=0 R1 + k R1 R1 R2 (R2 − k)!. k! R1 ! R2 − k k (4.26) In view of R2 k!(R2 − k)! = R2 !, k the expression (4.26) becomes R1 +1 (−1) R2 X (−1)k R1 + k R1 R1 !R2 ! . R2 − k R1 + k k (4.27) k=0 Using (4.17) again from Lemma 4.6.1 and substituting with m = R2 and x = R1 − R2 , we see that the expression (4.27) is zero. This complete the proof of the base case. To prove (4.24) for general n, we need the recursion 43 relation B X D(R1 , ..., Rn ; B) = Rn ! i=B−Rn B i D(R1 , ..., Rn−1 ; B). i Rn − (B − i) (4.28) We can easily understand (4.35) from the recursion relation between D(R1 , R2 , R3 ; B) and D(R1 , R2 ; B): D(R1 , R2 , R3 ; B) = R3 ! B X i=B−R3 B i D(R1 , R2 ; i). i R3 − (B − i) (4.29) Choose i out of B baskets to put the first and second kind of objects, which is accounted by D(R1 , R2 ; i), and the remaining B − i baskets have to be filled up with the third kind of objects. Now there are R3 − (B − i) third kind of objects left. Choose R3 − (B − i) out of i baskets which already contain the first and/or the second kinds of objects. Since the baskets and the objects are different, there is a factor of R3 !. Now we will prove R1 +R 2 +R3 X B=R1 (−1)B+1 D(R1 , R2 , R3 ; B) = 0 B (4.30) and the proof for general n is similar. Substitute (4.29) into the left hand side of (4.30) and interchange the two summations: R1 +R 2 +R3 X (−1)B+1 D(R1 , R2 , R3 ; B) B R1 +R 2 +R3 X (−1)B+1 R3 ! B B=R1 = B=R1 = RX 1 −1 i+R X3 i=R1 −R3 B=R1 B+1 (−1) B + B X i=B−R3 RX 1 +R2 i+R X3 i=R1 B=i + B i D(R1 , R2 ; i) i R3 − (B − i) R1 +R 2 +R3 2 +R3 R1 +R X X i=R1 +R2 +1 B=i B i D(R1 , R2 ; i) i R3 − (B − i) Since D(R1 , R2 ; i) = 0 unless i = R1 , R1 + 1, ...R1 + R2 , only the second summation is nonzero. 44 Focus on the inner summation: i+R X3 i (−1)B+1 B B i R3 − (B − i) B=i i+R 1 X3 B−1 i = (−1)B+1 i i−1 R3 − (B − i) B=i Set k = B − i; then we have R3 i (−1)i+1 X k k+i−1 (−1) i i−1 R3 − k k=0 R3 i (−1)i+1 X k k+i−1 . (−1) = i k R3 − k k=0 Using (4.23) in Lemma 4.6.2 with m = R3 and x = i − R3 , we see that the left hand side of (4.30) is zero. 4.8 The fourth identity Theorem 4.8.1 Let L be a positive integer greater than 1. Then k L−1 XX k=1 k L−1 j = (−1)L−1 . (−1) j j=1 j (4.31) Proof using the Feynman Identity. The special situation of the decomposition that will lead to this combinatorial identity is the following. Every subpath has only one repeated edge, except one of them, which we call the bridge. The repeated edges all have multiplicity two, and one of them is contained in the bridge and the other one is in some other subpath. Use the decomposition matrix and put the bridge in the first row, the left upper part of the decomposition matrix S looks like the 45 following:   1 1 1    1 0 0     0 1 0    . . .  ···    ···     ···     ··· Let the number of subpaths, including the bridge, be L, so L is greater than one. In order that the coefficient of Q mi i xi be nonzero, we need to take at least two factors, or two baskets in the egg-candy partition procedure, which means B has to be greater or equal to 2 in the summation of the right hand side of (4.2). The partition in this case is that, the bridge goes into one basket and the remaining (L − 1) subpaths go to the other basket, so total number of ways is 2. In the case of three baskets, the bridge has three choices to begin; after the bridge chooses one basket, and the remaining subpaths have two choices of baskets. In order to make sure every basket is non-empty, we need to subtract the two cases when both of the subpaths choose the same basket. Therefore, the total number is 3(2L−1 − 2). In general for k + 1 basket, k = 1, 2, ..., L − 2, we use the inclusion-exclusion principle to ensure that there is no empty basket, so k k L−1 L−1 L−1 k+1 k 1L−1 (k + 1) k − (k − 1) + (k − 2) + · · · + (−1) 1 k−1 k−2 1 X k L−1 j . (4.32) (−1)k+j =(k + 1) j j=k When there are L baskets, then each basket has to be fulfilled, therefore the number of choices is L!. If we substitute with k = L − 1 in (4.32), then we have L 1 X (−1)L−1+j j=L−1 1 X L − 1 L−1 L − 1 L−1 j . (−1)j j = (−1)L−1 L j j j=L−1 Using the follwing identity which we will prove later: L−1 X j=0 (−1)j L − 1 L−1 j = (−1)L−1 (L − 1)!, j (4.33) 46 we recognize that the expression in (4.32) when k = L − 1 is L!. So the expression (4.32) applies when k = L − 1 too. Summing over the index k for the number of baskets to find the coefficient on the graph side of (4.3): k X (−1)L+1 k L−1 1 (−1)k+2 1 j + ... + (−1)k+j (k + 1) L! − 2 + 3(2L−1 − 2) + · · · + 2 3 k+1 L j j=1 = k L−1 XX (−1)j k=1 j=1 k L−1 j j The path side of (4.3) has the coefficient of Q mi as (−1)L−1 , as explained in the following. Since i xi there is only one possibility to compose a single-stroke path, which is to start from some vertex of the bridge, and visit every other subpath using the repeated edge as a “bridge”, the number of crossings equals L − 1. To finish the story, we come back to (4.33). Use the identity (1.6) in [8]: k X (−1)j j=0 n−1 x k−x x n−1 X j!S2 (n − 1, k), (−1)j j = j k−j j j=0 (4.34) where S2 (n − 1, k) is the Stirling numbers of the second kind. Set k = x = n − 1 = L − 1 in (4.34): k X (−1)j j=0 Noticing that 0 L−1−j L−1 L−1 0 L − 1 L−1 X j!S2 (L − 1, j). (−1)j j = j L−1−j j j=0 = 0 when L − 1 6= j and 0 L−1−j = 1 when L − 1 = j and S2 (L − 1, L − 1) = 1, we get (−1)L−1 (L − 1)! on the right hand side. This complete the proof using the Feynman Identity. Alternative proof. Use the identity (1.6) in [8] again: n−1 k−x x n−1 X j x j!S2 (n − 1, k). (−1) j = (−1) j k−j j j=0 j=0 k X j 47 Set x = k and n = L in the above expression; we get k X j=0 Notice that 0 k−j (−1)j L−1 k 0 k L−1 X j!S2 (L − 1, k). (−1)j j = j k−j j j=0 equals 0 when k 6= j and 1 when k = j. Therefore, the only nonzero term on the right hand side is when j = k. So k X (−1)j j=1 k L−1 j = (−1)k k!S2 (L − 1, k) j Putting this expression into the inner summation on the left hand side of (4.31) , we get L−1 X k=1 (−1)k k!S2 (L − 1, k) = (−1)L−1 This identity can be proved using the generating function of the Stirling numbers of the second kind: xn = n X k=1 S2 (n, k)x(x − 1)(x − 2)...(x − k + 1) Set x = −1, n = L − 1, and the proof is complete. 4.9 The fifth recursion relation When the decomposition S = {pj |j = 1, 2, ..., A} of G{mi } contains a subpath pk , called the special path, whose edges are not repeated, i.e., for all ei ∈ E(pk ), mi = 1. We say S is a special decomposition if it contains a special subpath. Theorem 4.9.1 Let S be a special decomposition of G{mi } , and pk is the special subpath of S. Then D(S; B) = B D(S\{pk }; B) + D(S\{pk }; B − 1) , where S\{pk } = {pj |j = 1, ..., A and j 6= k}. (4.35) 48 Proof. The above is true because we can put the last object pk in any of the B baskets once we have done the allocation of the A − 1 objects into B baskets, none of them are empty. We may as well allocation the A − 1 objects into B − 1 non-empty baskets, and put the last object pk into the last basket. Since the baskets are distinct, again we have B choices. 49 Chapter 5 Conclusion 50 5.1 Conclusion In Chapter 2, the special case of the Feynman Identity was proved combinatorially. By taking logarithms and interpreting both sides of the Feynman Identity in a combinatorial way, we saw that the identity arises by counting the difference of the numbers of c-reduced words that have positive and negative signs. The definition of the sign function is explained by the planar drawing of an oriented cotree, but its properties (2.3) and (2.4), as well as Lemma 2.3.1 and 2.4.1 are independent of the particular drawings. Based on the latter Lemma, we were able to give a quick prove of Theorem 2.4.2. Chapter 3 digresses into the number of non-periodic reduced cycles in a directed graph. We apply the result to the special case of a single vertex and develope a method of calculating N (m1 , m2 , ..., mk ; +) and N (m1 , m2 , ..., mk ; −). When the number k of loops is 2, these numbers were calculated by Costa[4]. In Appendix A, we applied the methods of Chapter 3 to derive the same expressions for these numbers. Chapter 4 presents the Feynman Identity (4.1) and its alternative form (4.3) after taking logarithms. Four theorems involving combinatorial identities are derived from the alternative form as we look into several special conditions on the graph. We introduced the function D(A, R; B) to denote the number of distributions of A objects into B non-empty different baskets, with the condition that, among the A objects, R of them have to be in different baskets. This facilitates our discussion of the alternative form of the Feynman Identity and we are able to endow the graph side with a combinatorial interpretation. 51 Appendix A The Number of Pointed Cycles in the Case of Two Loops 52 A.1 Relation with Costa’s equation In Costa[4], an explicit expression for N (m1 , m2 ; +) is presented in eq (3.36). To simplify, let m1 = a, m2 = b, and a + b = M . If we rewrite that expression in terms of the notation here, we have N (a, b; +) = X d|g, d odd min[a,b]/d µ(d) d X ℓ=1 22ℓ−1 a/d − 1 b/d − 1 . ℓ ℓ−1 ℓ−1 (A.1) If we reduce (3.11) to the case of two loops and compare with the corresponding equation (A.1), we find the expression for the function fC (a/d, b/d): min[a,b]/d fC (a/d, b/d) = X ℓ=1 2M 22ℓ a/d − 1 b/d − 1 . d 2ℓ ℓ−1 ℓ−1 (A.2) Or, min[a,b] fC (a, b) = X ℓ=1 22ℓ a − 1 b − 1 . (a + b) ℓ ℓ−1 ℓ−1 (A.3) The subscript C is to signify that this function is the one from Costa. We will derive (A.3) by applying the result from Chapter 3. Notice that in the notation of Chapter 3, we distinguish a path from its reverse-direction one, but in Costa[4], page 1016, they are considered as in the same class. So the final result here should be twice as in Costa. Therefore, we will prove that f (a, b) = 2fC (a, b) in the following section. 53 A.2 Derivation of the function for the number of pointed cycles f (a, b) We will derive this formula from the matrix S in (3.8). Replace x1 in S by x and y1 by y for simplicity. Diagonalize S to get   x 0    0 y  ′ S =   0 0    0 0 Define A = 12 (x + y + p 1 2 (x + y + p 0 0 0 0 x2 + 14xy + y 2 ) 0 1 2 (x + y − 0 x2 + 14xy + y 2 ) and B = 21 (x + y − p p x2 + 14xy + y 2 )             x2 + 14xy + y 2 ). According to Lemma 3.3.1 when a > 0 and b > 0, f (a, b) = [T r(S ′a+b )]xa yb = [xa+b + y a+b + Aa+b + B a+b ]xa yb . So only Aa+b + B a+b is relevant. Use At + B t = (A + B)(At−1 + B t−1 ) − AB(At−2 + B t−2 ), A + B = x + y, and AB = −3xy, we get the recursion relation f (a, b) = f (a − 1, b) + f (a, b − 1) + 3f (a − 1, b − 1) (A.4) for a ≥ 1 and b ≥ 1.The initial conditions are f (1, 0) = f (0, 1) = 2, f (0, 0) = 4. The last one comes from the fact that the trace of a 4 × 4 identity matrix is 4. Define f (x, y) = ∞ ∞ X X f (a, b)xa y b , a=0 b=0 then from the recursion relation and the initial conditions, f (x, y) = 2 2 − (x + y) . 1 − (x + y + 3xy) 54 Let h(a, b) = [(1 − (x + y + 3xy))−1 ]xa yb , i.e., the coefficient of xa y b in h(x, y) = (1 − (x + y + 3xy))−1 , then min[a,b] h(a, b) = X ℓ=0 (a + b − ℓ)! 3ℓ , (a − ℓ)!(b − ℓ)!ℓ! and f (a, b) = 2(2h(a, b) − h(a − 1, b) − h(a, b − 1)). Put together, we get min[a,b] f (a, b) = 2(a + b) X ℓ=0 (a + b − ℓ − 1)! ℓ 3. (a − ℓ)!(b − ℓ)!ℓ! (A.5) This completes the derivation of the function f (a, b) from Chapter 3. A.3 Comparison of the two functions In order to show that f (a, b) and 2fC (a, b) are equal, we need the following lemma. Lemma A.3.1 min[a,b] X ℓ=0 (a + b − ℓ − 1)!Z ℓ = (a − ℓ)!(b − ℓ)!ℓ! min[a,b] X ℓ=1 (Z + 1)ℓ a − 1 b − 1 ℓ ℓ−1 ℓ−1 (A.6) for any Z > 0. The expressions we have for f (a, b) and fC (a, b) apply when Z = 3. Proof. Let m = min[a, b] and the coefficient of Z k be [Z k ]. Treat both sides as polynomials in the variable Z, then on the left-hand side [Z k ] is equal to a a+b−k 1 (a + b − k − 1)! , = (a − k)!(b − k)!k! a+b−k k a and on the right-hand side [Z k ] is equal to m X 1 a−1 b−1 ℓ ℓ=k ℓ ℓ−1 ℓ−1 k = m X 1 a a−k b−1 ℓ=k a k ℓ−k ℓ−1 . 55 For the last step, we use ℓ a a−1 = a ℓ ℓ−1 and a ℓ a a−k = . ℓ k k ℓ−k After eliminating a k , we get the equivalent statement X m a−k b−1 a+b−k a . = ℓ−k ℓ−1 a+b−k a ℓ=k Or, by using a a+b−k a+b−k−1 = a+b−k a a−1 and rewriting the dummy variable ℓ = ℓ′ + k, we get m−k X a − k b − 1 a+b−k−1 = . a−1 ℓ′ ℓ′ + k − 1 ′ ℓ =0 To prove (A.7), the right-hand side can be written as m−k X ℓ′ =0 a−k ℓ′ b−1 , (b − k) − ℓ′ and when a ≥ b, we use Vandermonde Convolution [8]: n X x y x+y = k n−k n k=0 where x = a − k, y = b − 1, and n = b − k in this case. When a < b, we use [8] n X n x+y−n k=0 k x−k = x+y x (A.7) 56 where x = b − k, y = a − 1, and n = a − k in this case. So the two expressions are the same. This complete the verification that our general method for deriving N (m1 , m2 , ..., mk ; +) is combatible with Costa’s analytical expression when k = 2. A.4 Combinatorial interpretation of fC (a, b) We provide a combinatorial meaning of Costa’s formula (A.3) as follows. The number of pointed cycles with a total of a occurrences of the first loop and b occurrences of the second loop can be counted by forming a word that has ℓ “blocks”. Each Block contains at least one first loop and at least one second loop. The possible number of blocks goes from 1 to min[a, b]. Now we need to divide a loops into ℓ blocks. We know that a−1 ℓ−1 is the number of positive solutions of the equation x1 + x2 + ... + xℓ = a. Divide a identical objects into ℓ blocks and the same for another b identical objects. Since each block, consisted of a and b, can be reversed, so there are 22ℓ possibilities. This accounts for the part 22ℓ a−1 ℓ−1 b−1 . ℓ−1 For a pair of the solutions, say {(x∗1 , ..., x∗ℓ ), (y1∗ , ..., yℓ∗ )} of the two equations x1 +x2 +· · ·+xℓ = a and ∗ )}, ..., {(x∗ℓ , ..., x∗1 ), (yℓ∗ , ..., y1∗ )} y1 +y2 +· · ·+yℓ = b, respectively, its ℓ−1 rotations: {(x∗2 , ..., x∗ℓ−1 ), (y2∗ , ..., yℓ−1 lead to the same pointed cycles. So after dividing it by ℓ, we can get the total number. Since we are looking for pointed cycles, there are a + b possible starting points. Therefore, there is a correction factor of a+b ℓ . 57 Appendix B Explicit Expression of the Feynman Identity When the Graph Is Connected 58 B.1 A special case of (4.3) when the graph is connected We will discuss the special case of (4.3) when G{mi } is a connected graph, where mi is the power of the indeterminate xi corresponding to the edge ei , and for every vertex vi , deg ∗ (vi ) ≤ 2. Notice that each of the summations on the graph side of (4.3) is over even simple subgraphs. So only when mi ’s are equal, say m, that the coefficient of mi on the graph side of (4.3) can i xi Q m+1 possibly be nonzero. Under this situation, the only nonzero term is (−1)m the coefficient is (−1)m+1 /m. P ( j Gj (xi ))m ; therefore, The expression from the path side reduces to (−1)m+1 /m under this situation too. Again only when all the mi ’s are equal can the expression possibly be non-zero . This is because the path is not allowed to go backward immediately; if the vertex vi has two distinct edges ej and ek , i.e., deg ∗ (vi ) = 2, each with multiplicity mj and mk respectively, then since every path that goes through ej has to continue to ek , mj = mk . When all the mi ’s are equal, say m, the graph is actually a non-self-crossing path, say p, repeated m times. The path pm has sign equals (−1)m+1 . Because W (mi ; ±) are the numbers of pointed paths, when m is odd, W (mi ; +) = |E(p)| and W (mi ; −) = 0; when m is even, W (mi ; +) = 0 and W (mi ; −) = |E(p)|. Therefore, the expression on the path side equals (−1)m+1 |E(p)|/M = (−1)m+1 /m. 59 Bibliography [1] S. Sherman, Combinatorial Aspects of the Ising Model for Ferromagnetism I, J. Math. Phys. 1 (1960), 202. [2] S. Sherman, Combinatorial Aspects of the Ising Model for Ferromagnetism II, Bull. Am. Math. Soc. 68 (1962), 225. [3] H. M. Hall, The Theory of Groups, New York (1959), 169. [4] G. A. T. F. da Costa, Feynman Identity: a special case. I, J. Math. Phys. 38(2) (1997), 1014. [5] G. A. T. F. da Costa and J. Variane Jr., Feynman Identity: a special case. II, arXiv:mathph/0305042 v1 (2003) [6] G. A. T. F. da Costa and A. L. Maciel, Combinatorial Formulation of Ising Model Revisited, arXiv:math-ph/0304033 v1 (2003) [7] P. N. Burgoyne, Remarks on the Combinatorial Approach to the Ising Model, J. Math. Phys. 4(10) (1963), 1320. [8] H. W. Gould, Combinatorial Identities, Morgantown Printing and Binding Co. (1972), 22.