NONINTERSECTING LATTICE PATHS 7 so that in particular [n]q\ = (q q)n, and ] f ! [n]q'[n-l]q--[n-k + l]q ^ Q k 0 The base q in [a]g, [n]q\, (a #)fc? (a z)oo7 and [^] will in most cases be omitted. Only if the base is different from q it will be explicitely stated. The basic hypergeometric series p +ijp is defined by P+IPP a i , . . . , a p + i £ (a1 q)i(a2 q)i---(ap+1]q)i , z i = 0 (g g)i(&i $)« •••(&* g)t An excellent reference book for basic hypergeometric series is [14]. We will frequently refer to it. 2.2. Tw o involutions and nonintersecting lattice paths. In order to make the arguments in sections 3 to 5 more transparent, it is perhaps appropriate to re- capitulate the usual procedure with nonintersecting lattice paths (cf. [16, 17, 41, section 1]), before going into the major counting theory. Given two lattice points in the integer lattice Z 2 , A = (Ai, A2) and E = (Ei,E2), we denote the set of all paths from A to E by P(A —* E). For the number of those paths we have | P ( ^ £ ) | = ( E l + g : £ - ^ ) . (2.2.1) As usual, for a set S by \S\ we mean the cardinality of S. Let Ai = (A^^A^) and Ei = (E± , E\ ), i = 1,2, . . . , r , be lattice points. Set A := (.4.1,... ,-4.r) and E := ( £ i , . . . , Er). The set of all families ( P i , . . . , Pr) of lattice paths where Pi goes from Ai to Ei, i = 1,.. . ,r, is denoted by P ( A E). A family of lattice paths is called intersecting if there are two paths in the family which have a point in common, if not the family is called nonintersecting. Two paths which have a point in common will also be called intersecting. The set of families ( P i , . . . , P r ) of nonintersecting lattice paths where Pi goes from Ai to Ei is denoted by P ( A E ) + , while the set of families ( P i , . . . ,P r ) of intersecting lattice paths is denoted by P ( A E)~. Now let At, Ei as above and A[1] A{?] •- A[r) a n d A ^ A{22) A(2r) , (2.2.2a) and E[l) E[2) E[r) and E^ E{22) £ r ) . (2.2.2b) To count the number |P(A E ) + | of all families ( P i , . . . , P r ) of nonintersecting lattice paths, P2 : Ai Ei, the following procedure is used. Obviously the relation |P(A - E ) + | = |P(A - E)| - |P(A - E)~ | (2.2.3)
Previous Page Next Page