Let $A$ and $B$ be two finite sets. I'd basically need to find the number of all Relations $R \subseteq A\times B$, possessing the following properties:
a) $R$ is right-unique
b) $R$ is right-unique, but not left-total
c) $R$ is either left-total or not right-unique.
For the first two points I've come up with the following function to calculate all the right-unique relations from A, to B, containing all the subsets of A with respectively from 1 to n elements: $$f(A, B, n) = \sum_{i = 1}^n \Biggl[C^i_{|A|}\cdot\sum_{k = 1}^{\min(i, |B|)}\bigg(V^k_{|B|}\bigg) \Biggr]$$
So I've come to the following results for the first two points:
a) right-unique relations: $S_1 = f(A, B, |A|)$
b) right-unique, but not left-total relations, which would mean the same as above, but without the case where the subset contains all the elements of A, so: $S_2 = f(A, B, |A| - 1)$
Now, what remains for c) is the hardest for me. Let's set:
$n(Lt)$ be the number of all left-total relations;
$n(Nru)$ be the number of all the non-righ-unique relations.
If we approach the issue logically, the statement would be equivalent to finding: $$n(Lt) + n(Nru) - n(Lt \cap Nru)$$
So far I've been able to find: $$n(Lt) = \Bigr( \sum_{i = 1}^{|B|}C^i_{|B|}\Bigl)^{|A|}$$ $$n(Nru) = |B|^{|A|} - f(A, B, n)$$
At the end, my two questions would be:
1) Is the function $f(A, B, n)$ correct at what it should do? I suspect it's not fully correct for the case where $|A| > |B|$... 2) How can I calculate $n(Lt\cap Nru)$?
This has been a really interesting challenge for me, thanks a lot in advance to anyone who proposes help!