Transformation (combinatorics)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In combinatorial mathematics, the notion of transformation is used with several slightly different meanings.[which?] Informally, a transformation of a set of N values is an arrangement of those values into a particular order, where values may be repeated, but the ordered list is N elements in length. Thus, there are transformations of the set {1,2,3}, namely [1,1,1], [1,1,2], [1,1,3], [1,2,1], [1,2,2], [1,2,3], [1,3,1],[1,3,2], [1,3,3], [2,1,1], [2,1,2],[2,1,3],[2,2,1], [2,2,2], [2,2,3], [2,3,1], [2,3,2], [2,3,3], [3,1,1], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3], [3,3,1], [3,3,2], and [3,3,3]. In general there are NN transformations for a set of N elements.

Analogous to a permutation group having elements that are permutations, a transformation semigroup has elements that are transformations. For N > 1, the set of permutations on N values is a proper subset of the set of transformations on N values.


  • J. Denes, Some combinatorial properties of transformations and their connections with the theory of graphs, Journal of Combinatorial Theory Volume 9, Issue 2, September 1970, Pages 108–116