# Surjections using Stirling-numbers

I have a task in which I can't really see what I'm doing wrong. The recommended answer differs from mine and it kind of makes sense to me, but I can't see what's wrong with my solution. The problem is as follows;

In a family of 4 all the 7 deadly sins are present. Every family member exercises(?)
atleast 1 of the 7 sins, but there are no sins that two distinct family members 'exercise'.
(The original problem formulation is not in english, sorry)


The task is to find out how many combinations there are if no single family member can exercise both greed and gluttony.

Basically what I did was to find out the total amount of combinations without taking the constraint into consideration (Surjection from a 7-subset to a 4-subset; $4! * S(7,4)$. After that I wanted to subtract the 'illegal' combinations. The way I figured I would find them out is as follows:

There are 4 possible family members that can exercise both greed and gluttony. After that we have 5 additional sins to 'hand out' amongst all the remaining people (including the one that we already 'handed' both gluttony and greed) so I figure'd we'd then get the total amount of 'illegal' combinations as $4 * 4! * S(5,4)$ but in the recommended solution the amount of illegal combinations was $4! * S(6,4)$ - which I understand (I guess you 'group up' both gluttony and greed as one sin and count the surjections).

But I don't understand why my solution is wrong. Any help greatly appreciated, sorry for the wall of text!

• I don't think so ("But there are no sins that two distinc family members 'exercise') - shouldn't that point to the contrary? Maybe I translated it bad but it says in the text that one specific sin can't be 'exercised' by two family members :) – Nyfiken Gul Oct 18 '16 at 14:36
• Oops; wasn’t thinking clearly. But I do now see the problem: $S(5,4)$ counts only the partitions of the other five sins into four non-empty pieces, so your calculation misses the combinations in which one person has greed and gluttony and nothing else. – Brian M. Scott Oct 18 '16 at 14:38
• Aha! That actually makes perfect sense, didn't consider that at all. Thanks again Brian! ;-) I'll gladly mark it answered if you post your comment as an answer, you're the man! – Nyfiken Gul Oct 18 '16 at 14:44

The problem here is that $S(5,4)$ counts only partitions of the other $5$ sins into $4$ non-empty parts; when you then distribute the greed/gluttony pair to one of those parts, you ensure that the family member who gets that pair also gets at least one other sin. Thus, you’re missing all of the arrangements in which one family member gets greed and gluttony and nothing else.