Find the number of possible functions from one set to another

In summary, the conversation discusses the number of functions with various restrictions and requirements. The total number of functions without any restrictions is ##n^m##, and the number of functions such that ##f(x)## is never ##1## is ##(n-1)^m##. The number of functions such that ##f(x)=1## for at least one ##x\in S_m## is ##n^m-(n-1)^m##. Similarly, the number of functions such that ##f(x) \notin \{1,2\}## is ##(n-2)^m##, and the number of functions that satisfy this requirement is ##n^m-(n-2)^m##. The
  • #1
HaRgIlIN
2
0
Homework Statement
Consider ##S_m = \{1, 2, 3, . . . , m\}## and ##S_n = \{1, 2, 3, . . . , n\}## with ##m, n \geq 3##.

(a) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m##?

(b) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) \in \{1, 2\}## for at least one ##x \in S_m##?

(c) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m## and ##f(y) \neq 2## for any ##y \in S_m##?

(d) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m## and ##f(y) = 2## for at least one ##y \in S_m##?
Relevant Equations
N/A
I have tried to solve them. I would like to know if my answers are correct.

(a)
The total number of functions without any restrictions
##=n^m##

The number of functions such that ##f(x)## is never ##1##
##=(n-1)^m##

The number of functions such that ##f(x)=1## for at least one ##x\in S_m##
##=n^m-(n-1)^m##

(b)
The number of functions such that ##f(x) \notin \{1,2\}##
##=(n-2)^m##

The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##
##=n^m-(n-2)^m##

(c)
Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##
##=(n-1)^m##

Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##
##=(n-2)^m##

Number of functions that satisfy the requirements in this part
##=(n-1)^m-(n-2)^m##

(d)
Since the answer from part (b) includes:

-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)\neq 2## for any ##y\in S_m##; (which is just part(c))

-The number of functions such that ##f(x)=2## for at least one ##x\in S_m## and ##f(y)\neq 1## for any ##y\in S_m##; (the number is equivalent to part(c)) and

-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)=2## for at least one ##y\in S_m##

Answer for part (d) is just ##[##part(b)##-2\times##part(c)##]##
Hence,
the number of functions
##=n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]##
##=n^m-2(n-1)^m+(n-2)^m##
 
Physics news on Phys.org
  • #3
haruspex said:
All looks good.

Thank you for your help.
 

Related to Find the number of possible functions from one set to another

What is the definition of a function?

A function is a mathematical rule that assigns a unique output value to each input value. In other words, for every input, there is only one possible output.

What is the difference between a one-to-one function and an onto function?

A one-to-one function is a function where each input has a unique output, and each output has a unique input. An onto function, on the other hand, is a function where every element in the output set has at least one corresponding input element.

How do you find the number of possible functions from one set to another?

The number of possible functions from one set to another can be found by using the formula n^m, where n is the number of elements in the input set and m is the number of elements in the output set. This formula assumes that each element in the input set can be mapped to any element in the output set.

Can there be an infinite number of possible functions from one set to another?

Yes, there can be an infinite number of possible functions from one set to another. This is because the input and output sets can have an infinite number of elements, and each element in the input set can be mapped to any element in the output set.

What is the significance of finding the number of possible functions from one set to another?

Finding the number of possible functions from one set to another can help in understanding the complexity of a problem and in making predictions about the behavior of a system. It is also used in various areas of mathematics, such as combinatorics and graph theory.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
671
  • Calculus and Beyond Homework Help
Replies
8
Views
305
  • Calculus and Beyond Homework Help
Replies
3
Views
673
  • Calculus and Beyond Homework Help
Replies
19
Views
393
  • Calculus and Beyond Homework Help
Replies
3
Views
570
  • Calculus and Beyond Homework Help
Replies
6
Views
352
  • Calculus and Beyond Homework Help
Replies
3
Views
914
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
458
  • Calculus and Beyond Homework Help
Replies
3
Views
695
Back
Top