Number of cyclically irreducible words in the alphabet of a free group of finite rank
- PDF / 123,092 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 101 Downloads / 200 Views
NUMBER OF CYCLICALLY IRREDUCIBLE WORDS IN THE ALPHABET OF A FREE GROUP OF FINITE RANK
UDC 519.1
L. M. Koganov
To the memory of William T. Tutte (05.14.1917—05.02.2002)
It is shown that a formula that was independently obtained earlier for the number of cyclically irreducible words of length n in a symmetric alphabet of a finitely generated free group of rank k and the Whitney formula for a chromatic polynomial of a simple nonself-intersecting cycle of length n with a variable l are mutually deducible from one another when l = 2k . The necessary bijections differ for even and odd values of n. Keywords: cyclically irreducible word, proper word, chromatic polynomial of a graph, Whitney formula for the chromatic polynomial of a simple cycle. PRELIMINARY INFORMATION 1. The problem consists of the establishment of a closed formula for the number of words of a special form for a fixed parameter n, i.e., the length of a word and a rank k in the case of a symmetric group alphabet A = {a1 , a1- 1 , K , a k , a k- 1 }, where a1 , a 2 , K , a k are all the generators of a free group. We put ì a - 1 if x = a , i -1 ï i x =í -1 ïî a j if x = ( a j ) and call x and x - 1 mutually inverse symbols. We consider that a word is irreducible (we denote by i.w. an irreducible word) if it does not contain a subword of the form xx - 1 , i.e., two mutually inverse adjacent symbols. Moreover, we assume that an irreducible word is cyclically irreducible (c.i.w.) if its single-letter beginning (prefix) and ending (suffix) are not mutually inverse. We will also use the concept of a proper word (p.w.) in a finite alphabet. A word is assumed to be proper if it does not contain any two identical adjacent symbols of the alphabet (nontrivial series are absent). This definition is a specialization of a proper coloring of a graph in the case of a simple nonself-intersecting chain with a punctuated or labeled beginning. We particularly note the possibility of occurrence of mutually inverse adjacent symbols in proper words.
Scientific Center of Nonlinear Wave Mechanics and Technology, Russian Academy of Science, Moscow, Russia, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 39–48, July–August 2007. Original article submitted January 25, 2006. 1060-0396/07/4304-0499
©
2007 Springer Science+Business Media, Inc.
499
FORMULATION OF THE RESULT 2. The result presented below is established in [1, 2] (see also [3]), was independently deposited earlier in an electronic archive [4; Theorem 1.1], but was published only in [5; p. 114, Fact 3]. Let n n be the number of c.i.ws. of length n in the symmetric group alphabet A. THEOREM. The following formula is true: ì ( 2k - 1) if n is even , n n = ( 2k - 1) n + í if n is odd. î1
(1)
Proof. Let us compare relationship (1) with the well-known H. Whitney formula [6; p. 691, formula (3.1)] (with the reference made to [7; Sec. 6, pp. 576–579]) for the chromatic polynomial c (C n , l ) of a simple nonself-intersecting cycle C n whose variable is l. The Whitney formula is of the form
Data Loading...
