1
$\begingroup$

Problem: $10$ people are standing in a queue when three new checkouts open. 8 people rush to the new checkouts and the new queues end up with at least two people in each.

In how many ways can the three new queues be formed?

Solution:

We are told that $q_1 + q_2 + q_3 = 8$ and that $q_i \geq 2$, where $q$ is short for queue.

This leaves six possibilities:

$$(q_1, q_2, q_3) \in \{(2,2,4), (2,3,3), (2,4,2), (3, 2, 3), (3, 3, 2), (4, 2, 2)\}$$

No matter what the triple $(q_1, q_2, q_3)$ is, we can imagine filling the three queues by first choosing eight people in order, in $P(10, 8)$ ways, and then placing the first $q_1$ people in the first quene, the second $q_2$ people in the second queue and the remaining $q_3$ people in the third queue.

This means that the total number of possibilities for the three queues are $6 \cdot P(10, 8)$.

Is this solution correct? And if the numbers and constraints gets messier is there a more elegant way to solve this?

(The different checkouts are distinguishable)

$\endgroup$
2
  • $\begingroup$ I always find it difficult in problems like these to discern how different two ways have to be in order to be counted as the same way. In one end of the spectrum, you have $\{(2, 2, 4), (2, 3, 3)\}$ as the only two ways ("How many queues have length $2$? What about $3$ and $4$?" and nothing more is what we care about). In the other end of the spectrum we have your solution, taking into account exactly which queue any given person gets in, and even which two people are left in the original queue. You seem to have gotten the right answer given your interpretation. $\endgroup$
    – Arthur
    Apr 14, 2016 at 16:11
  • $\begingroup$ @Arthur Yes, thats true. I am fairly new to this area of mathematics. But at least i have now added that the checkouts are to be considered distinguishable. $\endgroup$
    – JKnecht
    Apr 14, 2016 at 16:23

1 Answer 1

Reset to default
1
$\begingroup$

The answer seems ok to me.

For simplifying computation, instead of listing $(q_1,q_2,q_3)$
you could use the stars and bars combinatorics method to arrive at the figure of $6$

For this, firstly pre-place $2$ in each queue to take care of the constraint,
and fill the balance $2$ in $\binom{2+3-1}{3-1}\;$ to yield the figure of $6$ patterns.

$\endgroup$
11
  • $\begingroup$ Thanks! Could you explain in more detail how you get to $\binom{2+3-1}{3-1}\;$? E.g. they dont mention constraints in the wikipedia article and i couldnt find a good source for it, even tho it must exist. Btw i have noticed you are very knowledgeable in discrete mathematics, combinatorics and counting. Do you have a favourite book you could recommend that starts from the basics but still covers a good deal? Preferably it should deal with the intuition behind the theory too. $\endgroup$
    – JKnecht
    Apr 16, 2016 at 16:51
  • $\begingroup$ This is a simple constraint. At least $2$ are needed in each queue, so we pre-place $2$ in each. Now only $2$ more are to be placed by "normal" stars and bars. I have learned whatever little I know haphazardly, using the net, so I can't help you with books, but for an idea of how different constraints can be handled in "stars and bars" problems, for a start, you could have a look at csee.umbc.edu/~stephens/203/PDF/6-5.pdf $\endgroup$
    – true blue anil
    Apr 16, 2016 at 17:34
  • $\begingroup$ I have another short question. If you have more bars than stars does this method still work. I have no constraints but $x_1 + x_2...x_{10} = 5$ Is this still $$\binom{n+k-1}{n}=\binom{5+10-1}{5}=\binom{14}{5}$$ .Thanks. $\endgroup$
    – JKnecht
    Apr 23, 2016 at 21:35
  • $\begingroup$ The short answer is: yes ! $\endgroup$
    – true blue anil
    Apr 24, 2016 at 2:11
  • $\begingroup$ Of course, there is the usual constraint $x_i \ge 0$ $\endgroup$
    – true blue anil
    Apr 24, 2016 at 2:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .