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

In summary: However, out of those, 2^8 are reflexive and 2^36 are symmetric. So, the number of relations that are both reflexive and symmetric would be 2^8 * 2^36 = 2^44.In summary, 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). For the second question, the number of relations on a set of 8 elements that are both reflexive and symmetric is 2^44.
  • #1
Texans80mvp
2
0
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.
 
Physics news on Phys.org
  • #2


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
 

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

1. What is discrete math?

Discrete math is a branch of mathematics that deals with objects that can only take on distinct, separate values. It is used to study and solve problems related to counting, logic, and algorithms.

2. How is discrete math used in computer science?

Discrete math is an essential tool in computer science, as it provides the foundation for many important concepts and techniques used in programming and software development. It is used to design and analyze algorithms, create efficient data structures, and solve problems related to logic and computation.

3. What are some real-world applications of discrete math?

Discrete math has a wide range of real-world applications, including cryptography, computer networking, data compression, and operations research. It is also used in fields such as biology, economics, and social sciences to model and analyze complex systems.

4. What are some common topics in discrete math?

Some common topics in discrete math include set theory, logic, combinatorics, graph theory, and number theory. These topics are used to solve problems related to counting, relations, functions, and structures.

5. Is discrete math difficult to learn?

The difficulty level of discrete math varies depending on the individual, but in general, it is considered to be a more challenging branch of mathematics compared to others. However, with practice and a solid understanding of the fundamentals, it can be a fascinating and rewarding subject to learn.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
6
Views
8K
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
956
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
Back
Top