Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have $$A = \{a_1,a_2,\ldots,a_5\}, B = \{b_1,b_2,\dots,b_4\}$$ Problem: Count the number $k$ of onto functions $g_j$ (over the integers thru $k$) such that $g_j(a_1) \neq g_j(a_2)$ for all $j$.

The way I'm thinking about this is in terms of alphabets $abcde$. For the first two slots, we choose 2 elements out of the 4, and permute those. Then for the other three slots, we choose 3 elements out of the 4 and then permute them. So in total we have:

$$ \begin{pmatrix} 4\\ 2 \end{pmatrix}2! + \begin{pmatrix} 4\\ 3 \end{pmatrix}3! = 36 $$

Is this correct?

EDIT: Thank you all. I've learnt from all of your answers, and it's amazing that I got to see three different ways of counting the same number. I tried to re-reason my approach to supply the missing factor (3!) but I couldn't get anywhere sensible. If you can see a cool way to reinterpret it I would be happy to hear about it too!

share|improve this question

3 Answers 3

up vote 2 down vote accepted

Alternatively. An onto map is determined in this case by which pair gets mapped to the same element, the element that pair gets mapped to, and then the number of ways of sending the remaining elements 3 elements $1-1$ to the remain $b_i$.

The number of pairs is $\binom {5}2 -1 = 9$ since we have to exclude the pair $\{a_1,a_2\}$, since they cannot go to the same element.

The number of ways of choosing which $b_i$ that the pair goes to is $4$.

The number of ways of sending the remaining three $a_i$ onto the remaining three $b_j$ is $3!=6$.

So the total is $9\cdot 4 \cdot 6 = 216$

share|improve this answer
    
Nice, significantly more elegant than my brute force-ish approach. –  Lord_Farin Oct 11 '12 at 16:58

It is not, for you have not ensured that $g$ will be onto in this calculation.

As a possible reasoning, we have the following:

  • Pick $g(1)$; 4 possibilities.

  • Pick $g(2)$ distinct from $g(1)$; 3 possibilities.

  • For simplicity of reasoning, but WLOG, say $g(1) = 1, g(2) = 2$.

  • The remaining 3 elements $g(3), g(4), g(5)$ need to contain at least one $3$ and one $4$. This gives (a bit of a messy calculation) $18$ possibilities.

Thus the result is $4 \times 3 \times 18 = 216$.

EDIT: For the messy calculation in the last step, consider the following:

There are two ways in which $g(3), g(4)$ together are $3,4$ ($g(3) = 3, g(4) = 4$ and swapped). These give freedom for $g(5)$; a total of 8 possibilities.

In the other case $g(5)$ is fixed by the condition that $g$ be onto. But at least one of $g(3),g(4)$ must be $3$ or $4$; this excludes the $6$ cases $(1,1),(1,2),(2,1),(2,2),(3,4),(4,3)$, leaving $10$. Hence the total is $18$ as asserted.

share|improve this answer

The number of ways to partition $n$ labeled objects into $k$ nonempty unlabeled subsets is $\left\{ n \atop k \right\}$, a Stirling number of the second kind.

An onto function from $A \to B$ is a partition of the 5 elements of $A$ into (labeled) sets corresponding to the elements of $B$. So, in total, there are

$$ 4! \left\{ 5 \atop 4 \right\} = 24 \cdot 10 = 240 $$

onto functions $A \to B$ (the $4!$ assigns the unlabeled subsets of $A$ to elements of $B$).

Next, you want to find the number of onto functions $g : A \to B$ where $g(a_1) = g(a_2)$, so we can subtract that from the $240$ above. To do this, first choose the common value for $g(a_1)$ and $g(a_2)$: there are $4$ possible choices here. Next, assign the $3$ remaining values from $B$ to $g(a_3)$, $g(a_4)$, and $g(a_5)$. This is just $3!$. So, the number of onto functions $A \to B$ where $g(a_1) = g(a_2)$ is

$$ 4 \cdot 3! = 24. $$

The value you want, the number of onto functions $A \to B$ where $g(a_1) \ne g(a_2)$, is

$$ 240 - 24 = 216. $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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