0
$\begingroup$

Let $A,B$ be groups such that $\left | A \right | = 7$ $\left | B \right | = 5$ and let $a\in A$ and $b\in B$

Find the number of onto functions $f:A \mapsto B$ where $f(a) = b$

Using the inclusion - exclusion principle I found that all the surjective functions from $A$ to $B$ is $16,800$

My question is, should I treat somehow that $f(a) = b$ for $a\in A$ and $b\in B$?

Does it change the way I treat the question somehow? thanks.

$\endgroup$
2
$\begingroup$

You've over-counted, since you've also counted those surjections $f : A \to B$ such that $f(a) \ne b$.

To count it properly, note that there are two possible cases. Either:

  • $f(x) \ne b$ for any $x \ne a$. In this case, $f$ is uniquely determined by its restriction to a surjection $A \setminus \{ a \} \to B \setminus \{ b \}$; or
  • $f(x) = b$ for some $x \ne a$. In this case, $f$ is uniquely determined by its restriction to a surjection $A \setminus \{ a \} \to B$.

So you need to count the number of surjections $A \setminus \{ a \} \to B \setminus \{ b \}$ and the number of surjections $A \setminus \{ a \} \to B$. The sum of these two values is what you seek.

$\endgroup$
  • $\begingroup$ How could I instead subract all the surjections $f : A \to B$ such that $f(a) \ne b$ ? $\endgroup$ – vpam May 3 at 19:53
  • $\begingroup$ @vpam: You could also do that, but you'd need to consider whether the restriction of $f : A \to B$ to $A \setminus \{ a \}$ is surjective, which ultimately boils down to checking the two cases I mentioned in my answer. $\endgroup$ – Clive Newstead May 3 at 20:00
  • $\begingroup$ I am still not 100% sure why your method digs the right answer. Care elaborationg some more, or in a different way? $\endgroup$ – vpam May 3 at 20:19
  • 1
    $\begingroup$ @vpam: I'm partitioning the set of surjections $A \to B$ with $f(a)=b$ into two subsets. The first subset is those for which $a$ is the only element of $A$ that $f$ sends to $b$; the second subset is those for which there are other elements of $A$ that $f$ sends to $b$. The sizes of these subsets can then be computed by making the observations in my answer. $\endgroup$ – Clive Newstead May 3 at 20:24
3
$\begingroup$

Hint: Of all the surjective functions from $A$ onto $B$, what fraction have $f(a)=b$?

$\endgroup$
  • $\begingroup$ Im abit confused by that notion, is $a$ fixed? or arbitrary? Could you please elaborate furthermore? $\endgroup$ – vpam May 3 at 19:43
  • $\begingroup$ $a$ is some fixed member of $A$, and $b$ is some fixed member of $B$. It doesn't matter which. $\endgroup$ – Robert Israel May 3 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.