1,632 views
0 votes
0 votes
How many partial functions are there from a set with m elements to a set with n elements, where m and n are positive integers?

My try : Partial functions are the ones which are undefined for some elements of domain. Now we will have to find cases like at least one element of domain is not defined, at least two not defined and so on. from total possible functions from m to n if we do total - (all are mapped) it will be 0. How to approach it?

2 Answers

Best answer
0 votes
0 votes

Basic Point :-

let no.of elements in A = p and no.of elements in B = q, then total functions = qp

 

let reduce your question into m=4 and n=5

How many functions can possible ?

4C0 * 45. ===> why multiplied by 4C0 is , we left 0 elements in A without mapping.

Partial Functions is atleast one element in A is left as without matching.

4C1 means 1 element in A left as without matching. ==> remaining (4-1) elements in A and 5 elements in B ===> 5(4-1) functions

4C2 means 2 element in A left as without matching. ==> remaining (4-2) elements in A and 5 elements in B ===> 5(4-2) functions

4C3 means 3 element in A left as without matching. ==> remaining (4-3) elements in A and 5 elements in B ===> 5(4-3) functions

4C4 means 4 element in A left as without matching. ==> remaining (4-4) elements in A and 5 elements in B ===> 5(4-4) functions

4C1 * 5(4-1) + 4C2 * 5(4-2) + 4C3 * 5(4-3) + 4C4 * 5(4-4)4C1 * 53 + 4C2 * 52 + 4C3 * 51 + 4C4 * 50 ===> are partial functions.

 

on generalization, it is like

No.of partial functions =  mc1 . n(m-1) + mc2 . n(m-2)mc3 . n(m-3) + .......+mci . n(m-i) + ......+mcm . n(m-m)

mc1 . (1)1 . n(m-1) + mc2 . (1)2 . n(m-2)mc3 . (1)3 . n(m-3) + .......+mci . (1)i . n(m-i) + ......+mcm . (1)m . n(m-m)

mc0 . (1)0 . n(m) +   mc1 . (1)1 . n(m-1) + mc2 . (1)2 . n(m-2)mc3 . (1)3 . n(m-3) +....+mcm . (1)m . n(m-m)  - mc0 . (1)0 . n(m)

= (1+n)m - mc0 . (1)0 . n(m)

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

selected by
0 votes
0 votes

Cardinality of A is m and cardinality of B is n.

Now consider elements of B as boxes + 1 extra box.  

Therefore total we have n+1 boxes. Now why that extra 1 box?

As it is partial function, our elements in domain have n+1 options, either we can map it to any of n elements or don't want to map it to any one.

Consider domain as balls and co domain as boxes, take each ball and we have n+1 options for it. Hence the answer is (n+1)m

edited by

No related questions found