# Download Combinatorial Mathematics V: Proceedings of the Fifth by Wilfried Imrich (auth.), Charles H. C. Little (eds.) PDF

By Wilfried Imrich (auth.), Charles H. C. Little (eds.)

Read or Download Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference, Held at the Royal Melbourne Institute of Technology, August 24 – 26, 1976 PDF

Best mathematics books

Extra info for Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference, Held at the Royal Melbourne Institute of Technology, August 24 – 26, 1976

Example text

As each cycle of arcs must either all be contained in ~ or else all not be in ~, this gives a total of 2 (~(i)'~(j)) possibilities for the arcs between Yi and yj. If we multiply together all the independent possi- bilities for arcs from point cycles which are specified to he out-points to the remaining point cycles of g, we have in all 2i~ ~h(~(i),~(j)) different configurations of such arcs which are possible for digraphs fixed by g*. In addition one can specify independently the subgraph induced by the points of the cycles Yj for j ~ I, which could he any acyclic digraph fixed by (j~iYj] .

T. ] ] for all j >~0 on the right, the resulting equation is \$~. (15) Z(A),I : - Z ' T v. ,,. ~"" J 3 To allow a more compact representation of this relation, we define a product * for monomials by setting T. v. (i,j) 21'] i ] V T. V. ]] of formal generating functions. Then the double sum can be separated into a product, giving T. Z(A)-I [F'- f~'(-ai/~) i] * (Z N(T ;J )'["r(aj/j)--. T ,0 i ~i ! VjB0 J Vj! - E The first factor can be put in the exponential form 1 - e just Z(A) again. a /i (i- e l~± i ) * Z(A).

This should be compared with the relation (16) satisfied by Z(A). It is clear that in (23) the terms of total weight Sp in ZS,N(A) are the only ones which contribute in the ~ - p r o d u c t to the terms of total weight p+l in ZS,N(A). Thus, starting with 1 for weight 0 one can calculate the terms of successively higher total weights in ZS,N(A). , is k while the total weight is p. The disadvantage of (23) compared to (16) for computing A P is obvious. There will be many more terms of total weight p in ZS,N(A) then in Z(A), due to the distinction made between cycles of out-points and other point cycles.