International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 4, Pages 745-762

Equivalence classes of functions on finite sets

Chong-Yun Chao1 and Caroline I. Deisher2

1Department of Mathematics, University of Pittsburgh, Pittsburgh 15260, PA, USA
2Department of Mathematics, Indiana University of Pennsylvania, Indiana 15705, PA, USA

; Revised 7 June 1982

Copyright © 1982 Chong-Yun Chao and Caroline I. Deisher. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


By using Pólya's theorem of enumeration and de Bruijn's generalization of Pólya's theorem, we obtain the numbers of various weak equivalence classes of functions in RD relative to permutation groups G and H where RD is the set of all functions from a finite set D to a finite set R, G acts on D and H acts on R. We present an algorithm for obtaining the equivalence classes of functions counted in de Bruijn's theorem, i.e., to determine which functions belong to the same equivalence class. We also use our algorithm to construct the family of non-isomorphic fm-graphs relative to a given group.