Find the number of possible functions from one set to another

  • Thread starter HaRgIlIN
  • Start date
  • #1
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##
 

Answers and Replies

  • #3
2
0
All looks good.

Thank you for your help.
 

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

Replies
1
Views
3K
Replies
7
Views
10K
  • Last Post
Replies
10
Views
4K
Replies
17
Views
649
Replies
2
Views
3K
Replies
4
Views
1K
Replies
3
Views
4K
Replies
6
Views
2K
  • Last Post
Replies
8
Views
4K
Top