2

so I have following question

$A$ and $B$ are finite sets

How many Partial Functions exist between them ?

$f:A\to B$

Can someone give me a solution/hint/website where they may explain me a solution. Since unfortunately I can't think of a good solution for this one.

Empty
  • 13,012
Sai
  • 73
  • Possible duplicate: http://math.stackexchange.com/questions/292431/number-of-partial-functions-between-two-sets – J126 Feb 05 '15 at 01:49
  • Thank you very much for your answer, could you just explain me the formular a little more since I don't fully unterstand it – Sai Feb 05 '15 at 01:57

4 Answers4

3

Another solution is to identify a partial function $f$ from $A$ to $B$ with a total function from $A$ to the disjoint union $B \sqcup \{\ast\}$ (send every element not in the domain of $f$ to $\ast$). The number of such total functions is $(|B| +1)^{|A|}$, just as in Bernard's solution.

user43208
  • 8,289
1

A partial function from $A$ to $B$ is a map from a subset $X$ of $A$ to $B$. If this subset has $k$ elements $(0\le k\le \lvert B\,\lvert)$, there are $\lvert B\,\lvert^{k}$ such maps. In addition, there are $\dbinom{\lvert A\,\lvert}k$ such subsets.

It remains to sum over all possible values for $kk$: $$\sum_{k=0}^{\lvert A\,\lvert}\dbinom{\lvert A\,\lvert}k \lvert B\,\lvert^{k}=\bigl(1+\lvert B\,\lvert\bigr)^{\lvert A\,\lvert}.$$

Bernard
  • 175,478
1

Hope this interpretation is correct and makes it more simple, straight and intuitive:

In partial function, every element in $A$ need not have image in codomain $B$. Thus each element in $A$ will have $(|B|+1)$ ($+1$ for not mapping to any of the elements in $B$) choices. So total number of partial functions from $A$ to $B$

$ = \underbrace{(|B|+1) (|B|+1)… (|B|+1)}_{\text{|A| times}} = (|B|+1)^{|A|}$

Community
  • 1
Mahesha999
  • 2,053
1

Answer: (|B|+1)^|A|

You can come to the answer (|B|+1)^|A| pretty quickly by just imagining that B had an extra element as bottom, and then just calculate the number of functions from A to {B + bottom} and you will find this will be equivalent to the number of partial functions. This is because we just imagine that mapping to bottom equates to being not mapped by the partial function.

Ameen Izhac
  • 11