## Quick Reference

An equivalence class associated with a special kind of relation defined on functions. Let *F* = {*f*| *D* → *A*} be a set of functions mapping elements from some domain *D* into some set *A*, which can be regarded as an alphabet. With each function *f* in *F* is associated a **weight***w*(*f*), defined as the formal multiplication of all the images *f*(*x*) under *f*. In effect *w*(*f*) describes the number of occurrences of the different images in *A*.

*F* = {*f*| *D* → *A*}

An equivalence relation can then be defined between two functions of *F* in such a way that equivalent functions have equivalent weights, though the reverse is not in general true. The patterns of *F* are the equivalence classes that emerge from this equivalence relation.

The weight of a pattern is just the weight of any member of that pattern; the weight of the equivalence class [*f*] containing *f* is just *w*(*f*). The formal sum of the weights *w*(*f*) taken over all the equivalence classes in *F* gives the pattern inventory of the set *F*. An important theorem due mainly to George Pólya indicates the close link between pattern inventory and cycle index polynomial.

These ideas are often applied in combinatorics and switching theory. For example, a pattern inventory can indicate the number of essentially different wiring diagrams or logic circuits needed to realize the different possible logic functions.

**From:**
pattern
in
A Dictionary of Computing »

*Subjects:*
Computing.