Let’s count – Sharings into nonempty sets

Do your best in trying to solve the following problems. It is normal that this step will take some time, we recommend to perseverate and wait before looking at the complete solution of the exercises in the video or in the pdf below.

Before looking at the exercise let us suggest to convert a problem of looking at the (n)-sharings of (I_k) without empty sets (here (k,ninmathbb N_{ge 1})) into a problem of (k)-sequences of (I_n) where all the elements of (I_n) appear. The formula of their number, equal to

[n^k-binom{n}{n-1} (n-1)^k+binom{n}{n-2}(n-2)^k+cdots +(-1)^{n-1} binom{n}1 1^k]

begins with the number (n^k) of (k) sequences of (I_n). Then you subtract the number(displaystylebinom{n}{n-1}(n-1)^k) of sequences that contain only (n-1) elements of (I_n), and then you add the number(displaystylebinom{n}{n-2}(n-2)^k) of sequences that contain only (n-2) elements of (I_n), and so on…

Exercise 3.

Write how many ways there are to subdivide 4 people into 3 (nonempty) distinguishable groups (A, B, C) in two different ways:
a) by means of a known formula;
b) Count first partitions into 3 nonempty sets and then “label’’ the sets.