Green's Relation on the set of selfmaps of a set

Definitions: Let X be a set. A subset of X x X is called a relation on X. Let R be a relation on X. The statement [x,y] R can also be written x R y. R is symmetric if x R y implies y R x. The relation R is transitive if x R y and y R z implies x R z. The relation R is reflexive if x R x for all x X. If R is symmetric, transitive, and reflexive then R is called an equivalence relation on R. Let R be an equivalence relation on X. The set = {y | x R y} is called the R-class of x. A collection P of nonempty subsets of X is a partition of X if every point of X lies in exactly one member of the collection P.

Problem. Show that the collection of R-classes of an equivalence relation R on X is a partition of X.

Problem. Let P be a partition of X and define a relation R on X by x R y if and only if x and y lie in the same member of the partition. Show that R is an equivalence relation on X.

Definition of Green's R and D relations . Let X be the set of selfmaps of the set A = {1,2, ... n}. Green's R-relation is the relation R on X defined by f R g if and only if f(A) = g(A), that is, f and g have the same set of values. Green's D-relation is the relation D on X defined by f D g if and only if , that is, f and g have the same number of values.

Problem. Show that both of Green's relations are equivalence relations.

Problem. Show that each D-class is a union of R-classes.

Example. If we take A = {1,2}, there are 2 D-classes, = {[1,2], [2,1]} and = {[1,1],[2,2]}. The first D-class is also an R-class, but the second is the union of 2 R-classes, = {[1,1]} and = {[2,2]}.

Problem. Let A = {1,2,3}. List each D-class in and count its members. Do the same for the R-classes in .

Problem. Let A = {1,2,3,4}. List each D-class in and count its members. Do the same for the R-classes in .

Hint: Use Maple.

Problem. Let A = {1,2,3,4,5}. List each D-class in and count its members. Do the same for the R-classes in .

Hint: Now you really could use Maple.

Definition. For each pair of positive integers [n,r] with r between n and 1, define to be the D-class of and to be the number of functions in .

Problem. Fill in the triangle. I will get you started: 1st row: , 2nd row: .

Problem. Show that two R-classes in the same D-class have the same number of elements.

Definition. is defined to be the number of elements in any R-class in .

Problem. Fill in the triangle. I will get you started. 1st row: , 2nd row: , .