My attempt:

Surjections from 8-element set to 6-element can be divided into 2 cases.

  1. Three of the elements from 8-element set are mapped to single element in 6-element set.

  2. Four of the elements from 8-element set, which are divided into groups of two, are mapped to two elements in 6-element set.

For the first case, we have ${8}\choose{3}$ $\cdot$ $6!$ possible surjections.

The second case has ${8}\choose{2}$ $\cdot$ ${6}\choose{2}$ $\cdot$ $6!$ possible surjections.

In total, there are ${8}\choose{3}$ $\cdot$ $6!$ + ${8}\choose{2}$ $\cdot$ ${6}\choose{2}$ $\cdot$ $6!$ $= 342720$ possible surjections.

Is this a correct approach to solve the problem?

Any advice would be appreciated.

Thank you!


Almost perfect. You simply have to apply the $(1/2)$ scalar to the second case to compensate for over-counting.

For example: If you are sending $\{a,b,c,d,e,f,g,h\}$ to $\{1,2,3,4,5,6\}$
your present formula counts twice $(a,b) \to 1, ~~(c,d) \to 2$.

Your approach is very elegant in construing double or triple letters as a single unit. The common trap here is if two of your units each have a size greater than 1, and each are the same size, as in your second case, then you get over-counting.


Your Answer

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