1
$\begingroup$

I am going through a combinatorics textbook and in the process of solving a question, I began to wonder about something else and I was hoping someone could help me out with this. The question itself is relatively easy, to help set the stage for my question here's the original question:

A city with 6 districts has 6 robberies in a particular week. Assume the robberies are located randomly, with all possibilities for which robbery occurred where equally likely. What is the probability that some district had more than 1 robbery?

The answer to the question is relatively straightforward $1 - 6!/6^6$. I understand this answer, but the part I'm wondering about is the $6^6$ term. That term represents all possible configurations of where the robberies could have occured.

There are two ways/perspectives to arrive at that term in my mind, think from the perspective of the robbers, and think from the perspective of the city.

  1. The robber's POV is the easy one. Each robber has as choice of 6 cities to choose from, the first robber has 6, the second has 6 choices etc...thus $6^6$.

  2. What about from the point of view of the city though? This is where I'm stuck. How I would arrive at the $6^6$ from the point of view of each city.

My thoughts go something like this:

The first city could have 0 or 1, or 2 or...or 6 robberies. Mathematically we could represent this is as ${6 \choose 0}$ +${6 \choose 1}$....++${6 \choose 6}$. Where the first term represents 0 robberies happening in the city, the second term representing 1 robbery, and the last term representing all 6. This, if I'm not mistaken can be represented by $2^6$. This is where I get stuck though as I'm not sure how to get from $2^6$ "to" $6^6$.

But that's for 1 city, in this case the "first" city, arbitrarily designated. But now what about city 2, the number of robberies "left" for city #2 are determined in part by how many happened in city 1 etc.

I'm at a bit loss. I'm trying to solve each problem by counting multiple since combinatorics is a subject I've always always struggled with. I know the second way is a very convoluted way to try solve the problem. I'm wondering if there's a way to count the outcomes going the "other way" (from the city's POV) but struggling, if anyone has any guidance here I'd really appreciate it.

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

The number of ways a city can be robbed exactly $n$ times is $\binom{6}{n}\times5^{6-n}$. The $5^{6-n}$ is because the robbers that robbed other cities have 5 other cities to choose from. We have $\sum_{n=0}^6\left(\binom{6}{n}\times5^{6-n}\right)=6^6$ instead of $\sum_{n=0}^6\binom{6}{n}=2^6$.

$\endgroup$
2
  • $\begingroup$ Omg this is brilliant! I need to mull this over a few times. Holy toledo. The final derivation from the summation to the $6^6$ isn't super obvious to me, but I need to do it by hand. Your solution is so elegant. As a follow up though. So each city could be robbed n times, so wouldn't you need a double summation? One summation to account for each city, and one summation to account for ∑6n=0 representing each time that particular city could be robbed? $\endgroup$
    – Jackson
    Sep 6 at 2:27
  • $\begingroup$ So in your summand, n=1 represents the "first" city being robbed once etc.? I was wondering why you don't need to do the same for the "second" city and the third city etc. $\endgroup$
    – Jackson
    Sep 6 at 2:30

You must log in to answer this question.

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