Stirling number and combination with repetition

Question

I have 3 questions regarding 3 different things which are Stirling number and Combination with repetition and confusion

The common question for all 3 questions is how many ways to distribute 7 packages among A, B, C ?

1. Stirling number:

(i) if the packages are all different and no one must miss out. I know this is 3! S(7,3), exactly the theorem about counting number of surjective function but then...

(ii)if the packages are all different and exactly one person must miss out. The answer to this is 3! S(7,2) which i do not know how. Why it is not 2! S(7,2) since we only have to worry about 2 people who receive the packages

2. Combination with repetition:

(i) if the packages are indistinguishable. The answer is 9C7 and my problem is that i do not know how to choose k. More precisely, i do not know why k = 7 in this question but k was actually 3 in the problem of Stirling number above. So that leads me to the fact that i cannot do (ii) and (iii). (Please notice that the k i refer to is the k in Stirling number , Stirling number is in the form S(n,k))

(ii) if the packages are indistinguishable and no one must miss out

(iii) if the packages are indistinguishable and exactly one must miss out

3. The confusion:

(i) If there is no restrictions: The answer is 3^7 (each package has 3 ways to be distributed) but why it is not 7^3 (each person has 7 choices to get the packages) ? Which question i should ask in order to get 7^3 because i think for the question in my problem, i can do either way (but i know it is wrong so please clarify !)

Thanks for your help and sorry if it is too long Thanks again!!

Answer 1

1.(ii): There are three ways to choose the one who didn't receive the package. Since both people and packages are distinct, $2!$ ways to distribute the two stacks of packages to the people.

2.(i) The $k$ in your question is not clear to me, consider provide the formula. Notice that $_9C_7={_9}C_2$, which can be visualized as follow

$$A,B,C:\\ OO||OOOOO$$

The '$O$'s represent the packages distributed for A,B,and C. The two 'O's on the left of the first bar is for A, and those on the right of the second bar is for C. There is no '$O$' in between, which means B didn't get any package.

---

2.(ii): Brute force should work:

$$\begin{align}\\ (5,1,1)&:\binom{3}{1},\\ (4,2,1)&:3!,\\ (3,3,1)&:\binom{3}{1},\\ (3,2,2)&:\binom{3}{1}. \end{align}$$

So the total is $3+6+3+3=15.$

2.(iii): Similar to (ii) but considering $(6,1),(5,2),(4,3).$ So the total of just distributing packages to the two who receive is $2!+2!+2!=6,$ and there are there ways to choose the one didn't receive, so

$$3\cdot6=18.$$

3.(i): Consider your $7^3$, the result will be hilarious since two guys might choose the same package and probably fight for it... . In short, it's:

$$(\textrm{Choice})^{\textrm{guys}}$$

Answer 2

In how many ways can seven different packages be distributed to three people?

There are three possible recipients for each of the seven packages, so there are $3^7$ ways to distribute the packages.

You asked why the answer is not $7^3$.

It helps to look at extreme cases. Suppose we had one package and three possible recipients. Clearly, there are three ways to distribute the package, depending on the recipient. Notice that $3 = 3^1$, not $1^3$.

Also, a person can receive more than one package, but a package cannot be assigned to more than one person, so there are not seven choices of package for each of the three people.

In how many ways can seven different packages be distributed to exactly two of three people?

There are three ways to select the person who does not receive a package. There are $S(7, 2)$ ways to group the packages into two non-empty piles and $2!$ ways to distribute those piles to the remaining two people. Hence, the number of ways to distribute the packages to exactly two of the three people is $$3 \cdot 2!S(7,2) = 3!S(7,2)$$

In how many ways can seven indistinguishable packages be distributed to three people?

Let $x_k$ be the number of packages received by the $k$th person. Then $$x_1 + x_2 + x_3 = 7$$ is an equation in the nonnegative integers. A particular solution of the equation corresponds to the placement of two addition signs in a row of seven ones. For instance, $$1 1 1 + 1 1 + 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = x_3 = 2$, while $$+ 1 1 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 4$, $x_3 = 3$. The number of such solutions is the number of ways we can select two of the nine positions required for seven ones and two addition signs to be filled with addition signs, which is $$\binom{9}{2}$$ or, equivalently, the number of ways we can choose seven of the nine positions to be filled with the ones, which is $$\binom{9}{7}$$

In how many ways can seven indistinguishable packages be distributed to three people if each person receives at least one package?

Let $x_k$ be the number of packages received by the $k$th person. Then $$x_1 + x_2 + x_3 = 7$$ is an equation in the positive integers. A particular solution corresponds to the placement of two addition signs in the six spaces between successive ones in a row of seven ones. $$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, if we place an addition sign in the second and fifth spaces, we obtain $$1 1 + 1 1 1 + 1 1$$ which corresponds to the solution $x_1 = 2$, $x_2 = 3$, $x_3 = 2$. The number of such solutions is the number of ways we can select two of the six spaces between successive ones to be filled with addition signs, which is $$\binom{6}{2}$$

In how many ways can seven indistinguishable packages be distributed to exactly two of three people?

There are three ways to select the person who does not receive a package. Arrange the remaining two people in some order. Let $x$ and $y$ represent the number of packages received by the remaining two people. Then $$x + y = 7$$ is an equation in the positive integers. A particular solution corresponds to selecting which of the six spaces between successive ones in a row of seven ones must be filled with an addition sign. There are six ways to do this. Hence, the number of such distributions is $3 \cdot 6$.