Overview

pattern


Show Summary Details

Quick Reference

An equivalence class associated with a special kind of relation defined on functions. Let F = {f| DA} 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 weightw(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| DA}

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.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.