Discrete Math

Question

 

How many partial functions  are there from a set with m elements to a set with n elements?

Q. I cannot get the intuition how the solution arrived to be (n+1)^m

Comments

The Function is performed from X→ Y (let)

|X| = m and |Y| = n

Now Each Element in X has (n+1) choices i.e to connect with “n” elements or Not perfroming in the Function

Now,

For each element in X has (n+1) choices

Therefore (n+1).(n+1)…...m terms

we will get (n+1)^m.

Answer 1

m to n

Partial function is map from subset of m to n...

Suppose size of subset is k and k is always 0<=k<=n and there are n^k such mapping are possible...

Now there are mCk possible subsets are  of size k..

So from this we can find total no of partial functions..

= mC0 *n^0 + mC1 * n^1 +....+mCm *n^m

= (1+n)^m

Let's take m=2 and n=3

So =2c0 *3^0 + 2c1*3^1 + 2c2 * 3^2

   =   1+6+9 = 16

That is (n+1)^m = (3+1)^2 = 16

 

​​​​

Comments

*(0<=k<=m)

---

@papesh

partial function are funtions that are not defined for all element in its domain. i.e. it is defined only for some subset(other than the whole set and empty set) of the domain.

as per your answer ,  total no of partial functions..

= mC0 *n^0 + mC1 * n^1 +....+mCm *n^m

But   mCm *n^m  means no of total function 

---

https://gateoverflow.in/266995/rosen

Answer 2

source - Discrete Mathematics and Its Applications [7th Edition] - Kenneth H. Rosen Students Solutions Guide

Answer 3

Partial function: function + each element of domain can choose not to map any element in codomain (i.e at most one element of the second set)