Distributing $33$ employees to $3$ projects $A, B, C$ at least $1$ employee to $A$ and $B$, at least $2$ employees to $C$

Question

Determine the number of ways to distribute $33$ distinguishable employees of the corporation to three different projects $A, B, C$ so that:

• each employee is assigned to exactly one of the projects,
• someone is assigned to each project,
• at least $2$ employees are assigned to project $C$.

---

The question is similar to: Calculating the total number of surjective functions.

However, my main concern in that case is assigning $2$ employees to project $C$ I get some x' that do not cancel out in the final solution. Therefore I don't know how to solve it.

My proposed solution using exponential generating functions:

$$\left(x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... \right)^2 \left( \frac{x^2}{2!} + \frac{x^3}{3!} + ... \right) = \\= \big( e^x - 1 \big)^2 \big(e^x - 1 - x \big) = \\= (e^{2x} - 2e^x + 1)(e^x - 1 - x) = \\= e^{3x} - e^{2x} - xe^{2x} -2e^{2x} + 2e^{x} + 2xe^{x} + e^x - 1 - x = \\= e^{3x} - xe^{2x} - 3e^{2x} + 2xe^x + 3e^x -1 -x$$

• $ \left[ \frac{x^{33}}{33!} \right] \ e^{3x} = \left[ \frac{x^{33}}{33!} \right] 1 + 3x + \frac{(3x)^2}{2!} + ... + \frac{(3x)^{33}}{33!} + ... = 3^{33}$
• $ \left[ \frac{x^{33}}{33!} \right] \ xe^{2x} = \left[ \frac{x^{33}}{33!} \right] x + 2x^2 + \frac{4x^3}{2!} + ... + \frac{2^{32}x^{33}}{32!} + ... = 33 \cdot 2^{32}$
• $ \left[ \frac{x^{33}}{33!} \right] \ 3e^{2x} = \left[ \frac{x^{33}}{33!} \right] 3 + 6x + \frac{12x^2}{2!} + ... + \frac{3 \cdot 2^{33}x^{33}}{33!} + ... = 3 \cdot 2^{33}$
• $ \left[ \frac{x^{33}}{33!} \right] \ 2xe^{x} = \left[ \frac{x^{33}}{33!} \right] 2x + 2x^2 + \frac{2x^3}{2!} + ... + \frac{2 x^{33}}{32!} + ... = 66$
• $ \left[ \frac{x^{33}}{33!} \right] \ 3e^{x} = \left[ \frac{x^{33}}{33!} \right] 3 + 3x + \frac{3x^2}{2!} + ... + \frac{3x^{33}}{33!} + ... = 3$

From that I get (I canceled "$-1 -x$" because those don't provide any coefficients by $x^{33} \ $):

$3^{33} - 33 \cdot 2^{32} - 3 \cdot 2^{33} + 66 + 3 = 3^{33} - 39 \cdot 2^{32} + 69$

Is that correct?

Answer 1

Sanity Checking:

You can use basic Inclusion Exclusion to derive the right answer. This response is off-topic to examining your use of generating functions, except that if your answer disagrees with the right answer, you know that you've done something wrong.

See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

Constraints:

• C-1
  each employee is assigned to exactly one of the projects,

• C-2
  someone is assigned to each project,

• C-3
  at least $2$ employees are assigned to project $C$.

---

Let $~S~$ denote the set of all distributions that satisfy constraint C-1, without any regard for whether constraints C-2 or C-3 are satisfied.

Let $~S_1~$ denote the subset of $~S~$ that violates constraint C-2, by assigning $~0~$ people to group A.

Let $~S_2~$ denote the subset of $~S~$ that violates constraint C-2, by assigning $~0~$ people to group B.

Let $~S_3~$ denote the subset of $~S~$ that violates constraint C-3, by assigning less than $~2~$ people to group C.

Then, the desired computation is

$$|S| - |S_1 \cup S_2 \cup S_3|. \tag1 $$

Let :

• $T_0~$ denote $~|S|.$

• $T_1~$ denote $~|S_1| + |S_2| + |S_3|.$

• $T_2~$ denote $~|S_1 \cap S_2| + |S_1 \cap S_3| + |S_2 \cap S_3|.$

• $T_3~$ denote $~|S_1 \cap S_2 \cap S_3|.$

Then, by Inclusion Exclusion theory, the computation in (1) above is equivalent to

$$T_0 - T_1 + T_2 - T_3.$$

---

$\underline{\text{Computation of} ~T_0}$

To compute $~T_0,~$ note that you have $~3~$ choices for each of the $~33~$ people. Therefore,

$$T_0 = |S| = 3^{33}.$$

---

$\underline{\text{Computation of} ~T_1}$

Similar to the computation of $~T_0 = |S|~$ in the previous section, $~|S_1| = |S_2| = 2^{33}.$

The computation of $~|S_3|~$ has two mutually exclusive parts:

• No people are assigned to group C:
  $2^{33}.$

• Exactly one person is assigned to group C:
  $\displaystyle \binom{33}{1} \times 2^{32}.$

Therefore,

$$T_1 = \left[3 \times 2^{33}\right] + \left[33 \times 2^{32}\right].$$

---

$\underline{\text{Computation of} ~T_2}$

$~S_1 \cap S_2~$ represents assigning no people to either group A or group B. Therefore, $~|S_1 \cap S_2| = 1.$

The computation of $~|S_1 \cap S_3|~$ has two mutually exclusive parts:

• No people are assigned to group A and no people are assigned to group C:
  $1~$ way.

• No people are assigned to group A and exactly one person is assigned to group C:
  $\displaystyle \binom{33}{1}.$

So, $~|S_1 \cap S_3| = 1 + 33 = 34.$

By considerations of symmetry, $~|S_2 \cap S_3| = 34.$

Therefore,

$$T_2 = 1 + \left[2 \times 34\right] = 69.$$

---

$\underline{\text{Computation of} ~T_3}$

Under the assumption that constraint $~C_1$ is satisfied (i.e. each of the $~33~$ people is assigned to one of groups A, B, or C), it is impossible to simultaneously violate the constraints represented by $~S_1, ~S_2, ~$ and $~S_3.$

Therefore,

$$T_3 = |S_1 \cap S_2 \cap S_3| = 0.$$

---

$\underline{\text{Final Computation}}$

The desired computation is

$$T_0 - T_1 + T_2 - T_3.$$

$$T_0 = 3^{33}.$$

$$T_1 = \left[3 \times 2^{33}\right] + \left[33 \times 2^{32}\right].$$

$$T_2 = 69.$$

$$T_3 = 0.$$

Note:
This agrees with the original poster's computation of

$$3^{33} - \left(39 \times 2^{32}\right) + 69.$$

Answer 2

I suppose you are trying to use the theory of combinatorial species/ labelled structures.

We take the $``n"$ labels and partition it into $3$ blocks. The first and second blocks should be nonempty set structure. The third must have the structure of at least $2$ elements. This corresponds to the product species of the three species.

The egf of this species will be the product of the three species. The first and second species $\mathcal{S}_1$ and $\mathcal{S}_2$ have the egf $e^x-1$. The last one $\mathcal S _3$ has the egf $e^x-x-1$. The product of these is $(e^x-1)^2(e^x-x-1)$.

We want to find the coefficient of $\frac{x^{33}}{33!}$ from $(e^x-1)^2(e^x-x-1)$, which should be doable.