0
$\begingroup$

How many ways can $N$ different people select from $k$ different options such that no two people select the same option and $k>N$?

Concrete example: suppose we have $N = 6$ distinct people and $k = 10$ different bus stops. How many ways can the 6 people choose from the 10 bus stops such that no two people get off on the same stop?

I'm thinking that the answer might be $10\choose 6$ since we must choose 6 different people for 10 possible bus stops, but I'm not sure if this is the correct way of going about this.

Followup question: Say $N = 6$ distinct people are on an elevator with $k = 10$ floors and each must push a button for their floor. How many ways can the buttons be chosen such that no two people can choose the same button? (The order in which the lights are chosen doesn't matter)

This questions sounds similar to the one above so would the answer here be $10\choose 6$ as well (or whatever the correct answer to the above question is)?

$\endgroup$
0
$\begingroup$

The first person has $k$ choices. The next person has $k-1$ choices (any option not chosen by the previous person) and so on so that the number of ways is $$ k(k-1)\dotsb (k-N+1)=N!\binom{k}{N}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.