How Many Onto Functions and Symmetric Relations Exist in Given Sets?

[Texans80mvp]

For the first question it deals with onto functions I was able to do a-e which deals with actal numbers. Then questions E stumped me. I have no idea what to do or even how to start. It reads:

Let C (n,m) be the number of onto functions from a set of m elements to a set of n elements, where m > n > 1 (All of those are greater than or equal to signs). Find a formula relating C (n,m) to C (m-1,n) and C (m-1,n-1).

The second question deals with relations on a Cartesian product of A. A is a set with 8 elements. I was able to figure out that there are 2^64 relations total and 2^8 are reflexive while 2^36 are symmetric. However how many are both reflexive and symmetric? The question reads:

A is a set with eight elements.
How many relations on A are both reflexive and symmetric?

Any help would be greatly appreciated, even a point in the right direction would help. But like I said I am stuck and have almost no clue on what to do for either problem.

 

[mighty2000]

Hello,

For the first question, we can use the inclusion-exclusion principle to find a formula relating C(n,m) to C(m-1,n) and C(m-1,n-1). The inclusion-exclusion principle states that for three sets A, B, and C:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

In this case, we can think of the sets A, B, and C as the sets of onto functions from a set of m elements to a set of n elements, the set of onto functions from a set of (m-1) elements to a set of n elements, and the set of onto functions from a set of (m-1) elements to a set of (n-1) elements, respectively.

So, using the inclusion-exclusion principle, we can write:

C(n,m) = C(m-1,n) + C(m-1,n-1) - C(m-1,n-1)

This formula relates C(n,m) to C(m-1,n) and C(m-1,n-1), as requested.

For the second question, we can approach it by considering the definitions of reflexive and symmetric relations. A relation on a set A is reflexive if every element in A is related to itself. A relation is symmetric if whenever (a,b) is in the relation, (b,a) is also in the relation.

Since we are dealing with a set of 8 elements, let's label them as a, b, c, d, e, f, g, and h. Now, for a relation to be reflexive, we need to have (a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (g,g), and (h,h) in the relation. That's a total of 8 elements. Similarly, for a relation to be symmetric, we need to have (a,b), (b,a), (c,d), (d,c), (e,f), (f,e), (g,h), and (h,g) in the relation. That's also a total of 8 elements.

Now, let's consider the number of possible relations on the set A. As you correctly