Pólya's Counting Theorem and a Class of Tensor Identities

In an extensive class of combinatorial problems concerned with the enumeration of labelled structures (graphs, trees, regular polyhedra with labelled edges, vertices, faces, etc.), one is concerned with the action of a finite group G on a set R of functions (domain D = {1, 2, ..., d), range R = {1, ..., r}) [1, 2]. For example, if D = {1, ...,6} is regarded as the six faces of a cube and R — {1, 2} is a set of two colours (1 standing for " red " and 2 standing for " green " say), then each function in R represents a colouring of the cube. Cleaily two different functions can give the same painted cube (/(I) = l,/(i) = 2i # 1 and g(2) = 1, g(i) = 2, i # 2 for example). Each painted cube, however, corresponds to an orbit of G acting on R where G is the rotational substitution group of the cube (as a permutation group of order 24 on the faces of the cube) [1, 2]. For geGJe R, gf(x) = f(g~ (xj). Each of the 10 possible painted cubes thus corresponds to an orbit of G acting on R. As another example, let D = {1, ...,6} be the six places in a shift register and let R = {1, 2}. In this case the basic structure under consideration is a state of the shift register fa sequence of six binary digits either 1 or 2). The group G acting on D is the cyclic group (with generator (12 3 4 5 6)) of order six. In this example what is naturally observed are representatives of the orbits of G acting on R (e.g. 2 2 1 1 2 2, 2 1 1 2 2 2 , 1 1 2 2 2 2 all represent the same state but at most one is observed as the contents of the register at any given time). A fundamental tool for dealing with such problems is P61ya's enumeration theorem [1, 2]. P61ya's theorem or identity has the basic feature that it allows one to obtain combinatorial information about the orbits of G: R through routine computations which do not involve an explicit construction of these orbits (to make such an explicit construction may be quite difficult even on a digital computer). Certain classes of tensor algebraic identities used primarily in the study of matrix inequalities, matrix identities, and combinatorial matrix functions also have this basic feature [4, 5,11]. In this paper we explore the relationship between Polya's theorem and these identities, obtaining a generalization of P61ya's theorem which relates to pattern inventories where the " weights " and " labels " [1, 2] may vary within an orbit of G : R (i.e., non-homogeneous weights and labels).