Counting D-classes and R-Classes

MA 502 Project 1

By: Stephanie Getz 10/4/99

is the set of selfmaps of the finite set A with | A |= n .

Definition: is a D-class of . If f, g , then | f(A) | = | g(A) | = r .

In other words f and g are -valued selfmaps of A .

Definition: is the number of functions in . is the number of -valued selfmaps : ->{1,2,.., r }.

Definition: is an R-Class of . ( is as previously defined.) Given any , in R , f( A )=g( A ). (i.e., and share the same range.)

Definition: is the number of elements of any R-class in . Given a paricular r -valued range, say {1,...,r}, is the number of r-valued selfmaps of {1,...,n} to {1,...,r}.

Example: Let A ={1,2,3,4}, and is the set of three-valued selfmaps of A . The following Maple work lists and counts all the functions in this D-class.

> restart;

> D43:=NULL:
s:=0:
for i from 1 to 4 do
for j from 1 to 4 do
for k from 1 to 4 do
for l from 1 to 4 do
if (i=j and i<>k and i<>l and k<>l)
or(i=k and i<>j and i<>l and j<>l)
or(i=l and i<>j and i<>k and j<>k)
or(j=k and j<>i and j<>l and i<>l)
or(j=l and j<>i and j<>k and k<>i)
or(k=l and k<>i and k<>j and i<>j) then
D43:=D43,[i,j,k,l];
s:=s+1;
fi
od od od od:
D43:=[D43];
d43:=s;

>

Example: consider which was listed above. One R-class in is the set of functions whose range is {1,2,3}. The following Maple work lists and counts this R-class.

> restart;

> D43:=NULL:
s:=0:
for i from 1 to 4 do
for j from 1 to 4 do
for k from 1 to 4 do
for l from 1 to 4 do
if (i<>4 and j<>4 and k<>4 and l<>4)
and ((i=j and i<>k and i<>l and k<>l)
or(i=k and i<>j and i<>l and j<>l)
or(i=l and i<>j and i<>k and j<>k)
or(j=k and j<>i and j<>l and i<>l)
or(j=l and j<>i and j<>k and k<>i)
or(k=l and k<>i and k<>j and i<>j))then
D43:=D43,[i,j,k,l];
s:=s+1;
fi
od od od od:
D43:=[D43];
r43:=s;

Theorem I: The intersection of any two R-classes is empty.

Proof:

Let and be two different R-classes of . Assume is contained in both and . This means that for any

in , and have the same range; and similarly for any in , and have the same range. By transitivity of equality of sets, and have the same range. This implies that and are the same R-class, which is a contradiction because and are different R-classes. Thus, there cannot be a function in two different R-classes, which implies the intersection of any two R-classes is empty.

Theorem II: A D-class is the union of R-classes .

Proof:

Let be a union of R-classes. = {R-classes of selfmaps with = i } where is contained in ={subsets of domain, , with elements}.

Show .

i.) is in . Show is in .

Since is in , | | = . This implies is in , which implies that is in an R-class for some . And, this implies that is in .

ii. ) is in . Show is in

Since f is in U , f(A)=i for some i in I . This implies | f(A) |= r , which by definition means f is in .

By i) and ii) = U . Therefore a D-class is a union of R-classes.

Theorem III: Any two R-classes in a D-class have the same number of elements

Proof: Let R1 and R2 be R-classes of . = {selfmaps f :{1,.., n }-> ={ , , ,.., }, and ={selfmaps

g :{1,2,.., n }-> ={ , , ,..., }}. Since and are both r -valued and have cardinality r , one-to-one relationships can be made from the set {1,2,...,r}to both and . Let h be the one-to-one function h :{1,2,.., r }-> } and j be the one-to-one function :{1,2,.., r }-> .

Let M(A) ={selfmaps M:A ={1,..., n }->{1,2,.., r }} by identity property of sets.

Let h(M(A)) ={selfmaps h(M) , where h is the one-to-one function h :{1,2,..,r}-> }

| M(A) | = | h(M(A)) | because h is a one-to-one function that transforms the range {1,2,..,r} to .

Let j(M(A)) ={selfmaps j(M) , where j is the one-to-one function j :{1,2,.., r }-> }

| M(A) | = | j(M(A)) | because j is a one-to-one function that transforms the range {1,2,.., r } to .

Therefore, | h(M(A)) |=| j(M(A)) |

h(M(A)) ={selfmaps h(M) :{1,.., n }-> ={ , , ,.. }}= R1 by definition

j(M(A)) ={selfmaps j(M): {1,2,.., n }-> ={ , , ,..., }}= by definition

This implies | |=| |=| j(M(A)) |=| R2 |

Therefore, any two R-classes in a D-class have the same number of elements.

Theorem IV: The number of R-classes in a D-class is nCr.

By definition, an R-class is a set of selfmaps of A ={1,2,.., n } with the same r -valued range. The number of R-classes is the number of different r -valued ranges for these selfmaps. The number of r -valued ranges of selfmaps is the same as the number of r -element subsets of A , whose cardinality is n . The number of r -element subsets from an n -element set is nCr (by definition of nCr). Thus, the number of R-classes in a D-class is nCr.

Theorem V: =(nCr)*

Proof:

By the Theorems 1, 2, and 3, the intersection of any two R-classes is empty; and the D-class equals the union of the R-classes in the D-class, and any two R-classes in a D-class have the same number of elements.

This implies =(the number of functions in ) = (#R-classes in )*(# functions per R-Class in )

= (nCr)*

Theorem VI: = - sum( , i=1..r-1) for , and = 1.

Proof:

i)

By definition is the number of functions in an R-classes of . is the D-class of selfmaps with a one-valued range. In other words, is the D-class of constant selfmaps. Since the domain of the selfmaps, A = {1,2,.., n }, has n elements, there are n constant selfmaps of A . Thus . By Theorem V, = (nCr)* .

This implies . Thus = = =1.

ii.) = - sum( *rCi, i=1..r-1)

By definition, is the number of selfmaps in an R-class of . is the D-class of selfmaps with an r -valued range. From Theorem III, any two R-classes in a D-class have the same number of elements. So, we will consider the R-class with range {1,2,..,r}. is the number of r -valued maps : A ={1,2,..., n }->{1,..,r}.

Let F be the set of maps (any valued) f : A ={1,2,..., n }->{1,.., r }. | F | is because for each element in the domain, A , of the functions in F , there are r possible values in the range that the functions can take. This total number takes into account all of the constant functions, two-valued functions, three-valued functions, ..., (r-1) valued functions, and r-valued functions.

To obtain the number of r-valued selfmaps, the number of constant maps, two-valued maps, ..., (r-1) valued maps must be subtracted from the total number of selfmaps possible in the given range.

Let ={ : is a constant selfmap of A and :{1,2,.., n }->{1,2,.., r }},

={ : is a two-valued selfmap of A and :{1,2,.., n }->{1,2,..., r }},

={ : is a three-valued selfmap of A and :{1,2,.., n }->{1,2,..., r }},

.

.

.

={ : is an (r-1) -valued selfmap of A and :{1,2,.., n }->{1,2,..., r }},

and ={ : is an r -valued selfmap of A and :{1,2,.., n }->{1,2,..., r }}

| | = *(rC1) because gives the number of functions for one specific one-valued range, yet the range can be any of the r elements of {1,2,.., r }.

| |= *rC2 because gives the number of functions for one specifice two-valued range, yet the two-valued range can be any two-element subset of {1,2,.., r }, and the number of such subsets is rC2.

In general, | |= *rCi because gives the number of functions for one specific i -valued range, yet the i -valued range can be any i -element subset of {1,2,.., r }, and the number of such subsets is rCi.

Therefore, | | = *rCr = = - sum(| |, i =1.. r-1 ) = -sum( *rCi, i =1.. r-1 )

= -sum( *rCi, i =1.. r-1 )

***I am at a loss as to how to get Maple to execute this recursive function, but I will test by hand .

From the brute force example at the beginning of the project, we know =36. I will verify the formula with this.

= -( *3C1 + *3C2)

=81-(3*1 + 3*( - *2C1))

=81-(3+3(16-2))

=81-45 = 36

Excellent. You are excused from the exam. You may participate however.
here is the maple procedure which implements your formula. I called the function cr for
cardinality of an rclass.

> cr := proc(n,r)
options remember;
local i;
if r = 1 then 1
else r^n - add(cr(n,i)*binomial(r,i),i=1..r-1) fi end;

> cr(4,3);

If you use the small semigroup vocabulary to produce a table of values for cr(n,r) for n=1..6 you get this table . checking the bottom row against cr, we get

> seq(cr(5,i),i=1..5);

Same answers. Yahoo!