1
$\begingroup$

A survey consists of recording, the number of cars presently owned by a household among six major manufacturers. Order does not matter.

i. Suppose that no household has more than four cars. In how many different ways can the survey sheet be filled out?

I was thinking maybe it would just be 4! + 6! but I have a feeling that is wrong, I'm not sure if that would account for multiple cars being from the same brand

$\endgroup$
2
  • $\begingroup$ It depends on what ways of filling out are to be considered different. Is a Toyota. a Toyota, and a Ford to be considered different from a Toyota, a Ford, and a Toyota? $\endgroup$
    – André Nicolas
    Mar 14, 2015 at 21:12
  • $\begingroup$ @AndréNicolas no, order does not matter in this case $\endgroup$
    – seanscal
    Mar 14, 2015 at 21:15

2 Answers 2

Reset to default
2
$\begingroup$

Let $x_1$ be the number of GMs, let $x_2$ the number of Fords, and so on up to $x_6$ being the number of Nissans. We want to find the number of solutions of $$x_1+x_2+\cdots+x_6\le 4$$ in non-negative integers. This is the same as the number of solutions of $$x_1+x_2+\cdots+x_6+x_7= 4$$ (the variable $x_7$ counts the number of empty slots in the four-car garage).

Now we have a standard Stars and Bars problem (please see Wikipedia). The number of solutions is $\binom{4+7-1}{7-1}$, that is, $\binom{10}{6}$, or equivalently $\binom{10}{4}$.

$\endgroup$
4
  • $\begingroup$ It is good to point out the fact that it is indeed possible for someone to own zero of the major brand cars (something which many people would overlook for this problem). This answer correctly accounts for that small subtlety. $\endgroup$
    – JMoravitz
    Mar 14, 2015 at 21:27
  • $\begingroup$ This makes a lot of sense to me, but I can't really see why the other answer of 6^n for n = 0 to 4 is wrong. Can someone point out what is wrong with it that I dont see? @JMoravitz $\endgroup$
    – seanscal
    Mar 14, 2015 at 21:33
  • $\begingroup$ @seanscal $\sum\limits_{n=0}^4 6^n$ answers the question of if the order of the vehicles listed matters. (seen from multiplication principle). This is however not the case, as the OP clarified, ToyotaToyotaFord is the same as ToyotaFordToyota, so you have overcounted. $\endgroup$
    – JMoravitz
    Mar 14, 2015 at 21:35
  • $\begingroup$ ahhh ok, totally get it now, thanks a lot to both @JMoravitz and Andre! $\endgroup$
    – seanscal
    Mar 14, 2015 at 21:39
1
$\begingroup$

Look at the cases of different numbers of cars:

  1. No cars: 1 way of filling out the survey
  2. 1 car: 6 ways of filling out the survey.
  3. 2 cars: 6*5/2 ways of filling out the survey without repetition; 6 ways of filling out the survey with all the same manufacturer.
  4. 3 cars: 6*5*4/(3*2*1) ways of filling out the survey without repetitions; 6*5 ways of filling out the survey with 2 cars the same and 1 different; 6 ways of filling out the survey with all the same manufacturer.
  5. 4 cars: 6*5*4*3/(4*3*2*1) ways of filling out the survey without repetitions; 6*5*4/2 ways of filling out the survey with 2 cars the same and the other 2 different (from each other and the first 2); 6*5/2 ways of filling out the survey with 2 and 2; 6*5 ways of filling out the survey with 3 cars the same and 1 different; 6 ways of filling out the survey with all the cars from the same manufacturer.

Python has a built in module called itertools (https://docs.python.org/2/library/itertools.html) which has a iterator called combinations_with_replacement.

import itertools as it

tot = 0

for r in range(5):

 s=0

 for i in it.combinations_with_replacement("ABCDEF",r):

      s+=1

 t+=s

 print r,s,t

0 1 1 1 6 7 2 21 28 3 56 84 4 126 210

Total is 210

$\endgroup$
1
  • $\begingroup$ Stars and bars. How could I have forgotten. That's a much better way of doing it. $\endgroup$
    – Dr Xorile
    Jun 22, 2015 at 0:59

You must log in to answer this question.

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