Question

Ten students shall be sorted into the four houses (namely Gryffindor, Slytherin, Ravenclaw, and Hufflepuff) in Hogwarts. If at least one student shall go to each house, how many ways can the students be sorted?

Answer 1

For the sake of simplicity , let us denote Gryffindor by G, Slytherin by S, Ravenclaw by R and Hufflepuff by H.

Let the 10 students be denoted by a₁ , a₂ , ....a₁₀.

Suppose we have a sorting of the 10 students into the four houses such that at least one student has been assigned to each house. Each student can be assigned to a unique house. However, one or more students can be assigned to the same house. Thus, we have a function f : {a₁,a₂,...a₁₀} {G,S,R,H} defined by f(a_i) = The house to which a_i is assigned to in the sorting for each i in {1,2,...10},

such that every element in the codomain (every house) has at least one student(preimage) assigned to it. In other words, a sorting of the 10 students into the four houses such that at least one student has been assigned to each house corresponds to unique onto function f : {a₁,...a₁₀} {G,S,R,H} such that f(a_i) = The house to which a_i has been assigned to  in the sorting for all i in {1,2,...10}.

Conversely, given an onto function f : {a₁,....a₁₀} {G,S,R,H} , we get a unique sorting of the 10 students into the 4 houses such that at least one student has been assigned to each house ( assign student a_i to house f(a_i) for all i in {1,2,...10} ).

Thus, the set of all such sortings of the 10 students into the four houses such that each house contains at least one student is in bijective correspondence with the set of all onto functions from {a₁,....a₁₀} onto {G,S,R,H}.

Hence, the required number of ways of sorting the 10 students is equal to the number of onto functions from the set of the 10 students onto the set of the 4 houses.

The solution calculates this using the Principle of Inclusion and Exclusion.