Divide $n$ people into $k$ teams with restrictions

Question

How many ways are there to divide $n$ people into $k$ distinct teams with the following restrictions:

1. Each person has to be in at least $1$ team
2. Each person can enlist to at most $2$ teams
3. Each team has to have at least $1$ person

It is inclusion-exclusion but I am not exactly sure how, I tried several things but failed.

My best attemp was:

Let $A_1$ be the number of ways to divide the people into all the teams beside team $1$ my attemp was I will first pick the number of people that are in $2$ teams $\binom{n}{j}$ and divide $n+j$ people to $k-1$ teams so I have $\sum_{j=0}^{n}\binom{n}{j}{(k-1)^{n+j}}$ and i think i also need to divide by $2^{j}$ but both ways doesnt add up when i try the formola for some numbers.

Answer 1

I think you counting strategy is flawed; you consider choosing the $j$ people who get two teams, forming "duplicates" of those people to make $n+j$ people, and then arbitrarily assigning the $n+j$ people to $k-1$ teams. (Side note: Why is it $k-1$? Shouldn't it be $k$?) However, this allows two duplicate people to be assigned to the same team, which is double counting.

Ignoring condition $3$, then number of ways to assign each person to $1$ or $2$ teams is $$ \bigg(k+\binom{k}2\bigg)^n, $$ because for each of the $n$ people, you can either assign them to $1$ team in $k$ ways, or $2$ teams in $\binom{k}2$ ways. To account for condition $3$, you need to subtract the "bad" arrangements where some team is empty. This is where the principle of inclusion exclusion comes in. For each of the $k$ teams, $T$, we subtract the arrangements where team $T$ has no members. The result is $$ \bigg(k+\binom{k}2\bigg)^n-k\times \bigg((k-1)+\binom{k-1}2\bigg)^n $$ However, this doubly subtracts the situations where two teams were empty, so to correct he above, we must add back in the number of situations where two particular teams are empty, for each of the $\binom{k}2$ pairs of teams. Continuing as you usually do when using the principle of inclusion-exclusion, you then add the situations with three empty teams, subtract the situations with $4$ empty teams, and so on.

I leaver it to you to fill in the rest of the details...