Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We want to distribute $10$ persons into $6$ different cars knowing that each car can take three persons. How many ways have to do it. The order of the person inside the same car is not important and the car can be empty.

share|improve this question
2  
does each car need to be driven? (aka do we need at least one person per car?) –  kaine Aug 5 '13 at 15:55
    
No, there is a driver in the car, and the order of persons inside the car is not important –  Noureddine Aug 5 '13 at 16:00
    
In other words, it is possible for some cars to have 0 people? –  Doctor Dan Aug 5 '13 at 16:16
    
YES it is possible –  Noureddine Aug 5 '13 at 16:26
    
In problems like this it is necessary to state what the objective is. In this problem for example, the objective could be to fill each car, for each car to have at least one person, or for each person to be placed into a car. From what you've stated in the comments it is the latter, but next time be sure to state it more clearly in the question. –  Ataraxia Aug 5 '13 at 16:33

1 Answer 1

If we put $i$ people in the 1-st car, there's $\binom{10}{i}$ ways to do this. Once this is done, we put $j$ people in the 2-nd car, and there's $\binom{10-i}{j}$ ways to do this. And so on, until we get to the final car, where we attempt to put in all of the unassigned passengers. If there's more than 3, we discard this case.

Hence the number of ways is: $$\scriptsize \sum_{i=0}^3 \binom{10}{i} \sum_{j=0}^3 \binom{10-i}{j} \sum_{k=0}^3 \binom{10-i-j}{k} \sum_{\ell=0}^3 \binom{10-i-j-k}{\ell} \sum_{m=0}^3 \binom{10-i-j-k-\ell}{m} [0 \leq 10-i-j-k-\ell-m \leq 3].$$

Here $[0 \leq 10-i-j-k-\ell-m \leq 3]$ takes the value $1$ if $0 \leq 10-i-j-k-\ell-m \leq 3$ is true and $0$ otherwise.

In GAP this is computed by

WithinBounds:=function(n)
  if(n>=0 and n<=3) then return 1; fi;
  return 0;
end;;

Sum([0..3],i->Binomial(10,i)*Sum([0..3],j->Binomial(10-i,j)*Sum([0..3],k->Binomial(10-i-j,k)*Sum([0..3],l->Binomial(10-i-j-k,l)*Sum([0..3],m->Binomial(10-i-j-k-l,m)*WithinBounds(10-i-j-k-l-m))))));

which returns $36086400$.


Alternatively, let $\mathcal{G}$ be the set of partitions of $\{1,2,\ldots,10\}$ of size at most $6$ with parts of size at most $3$. Given a partition $P \in \mathcal{G}$, there are $\binom{6}{|P|} |P|!$ ways to distribute the passengers among the cars in such a way to as give rise to the partition $P$ (after discarding empty cars). So, the number is also given by $$\sum_{P \in \mathcal{G}} \binom{6}{|P|} |P|!.$$

This is implemented in GAP via:

S:=Filtered(PartitionsSet([1..10]),P->Size(P)<=6 and Maximum(List(P,p->Size(p)))<=3);;
Sum(S,P->Binomial(6,Size(P))*Factorial(Size(P)));

which also returns $36086400$.

share|improve this answer
    
the result seem very huge than the reality!! I notice that the order is not important –  Noureddine Aug 6 '13 at 14:10
    
Okay. I answered what I considered to be the most likely interpretation of what you asked. I'm happy to help, but I'm not going to keep guessing what you have in mind (e.g. you say "the order is not important" -- are you saying this about my answer or your question, and the order of what is not important?). Why not put some effort into improving your question (i.e., edit it)? E.g. add examples of what is considered a valid arrangement, and explain when two arrangements are equivalent. –  Douglas S. Stones Aug 6 '13 at 15:30
    
I am very sorry for my question formulation, I have tried to enhance it. –  Noureddine Aug 6 '13 at 17:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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