Man needs to buy cars (combinatorics)

In summary, the problem of a man buying 12 cars of 4 different kinds can be solved using a recursive scheme or the stars and bars method. Using the recursive scheme, we can find the number of solutions for different values of n and then add them up to get the total number of ways to buy 12 cars. Using the stars and bars method, we can express the problem as finding the number of ways to distribute 12 objects into 4 groups, which can be solved by the formula ##\binom{n+k-1}{k-1}##, where n is the number of objects and k is the number of groups. Both methods give the same result of 455 possible ways to buy 12 cars.
  • #1
kent davidge
933
56

Homework Statement



A man needs to buy 12 cars. There are 4 kinds available. He can buy any number of cars of each kind, the condition being 12 cars in total. In how many ways can he buy the 12 cars?

Homework Equations

The Attempt at a Solution



Hmmm as he can buy any number of each kind my guess is that this is not going to be a simple problem. Using only permutations will not be enough. If we let each kind of car be ##k_i##, then we have ##k_1 + k_2 + k_3 + k_4 = 12## and the problem reduces to finding all possible quadruples ##(k_1, k_2, k_3, k_4)## that satisfy that equation. It turns out that there are 455 possible ways of buying the 12 cars (book answer). How can I procceed?
 
Physics news on Phys.org
  • #2
kent davidge said:

Homework Statement



A man needs to buy 12 cars. There are 4 kinds available. He can buy any number of cars of each kind, the condition being 12 cars in total. In how many ways can he buy the 12 cars?

Homework Equations

The Attempt at a Solution



Hmmm as he can buy any number of each kind my guess is that this is not going to be a simple problem. Using only permutations will not be enough. If we let each kind of car be ##k_i##, then we have ##k_1 + k_2 + k_3 + k_4 = 12## and the problem reduces to finding all possible quadruples ##(k_1, k_2, k_3, k_4)## that satisfy that equation. It turns out that there are 455 possible ways of buying the 12 cars (book answer). How can I procceed?

A somewhat better method than complete enumeration is a recursive scheme. For ##n = 0,1, \ldots, 12## let ##N_2(n)## be the number of non-negative integer solutions to the equation ##k_1+k_2 = n##. The number of solutions ##N_3(n)## to the equatio ##k_1+k_2+k_3=n## is ##\sum_{j=0}^n N_2(j)##; do you see why? So, we can get all the ##N_3(n)## for ##n = 0,1, \ldots, 12.## Finally, you can get the answer as ##N_4(12) = \sum_{j=0}^{12} N_3(j).## This is well suited to implementation in a spreadsheet.

You could also try to adapt the "stars and bars" method to help shorten the calculations.
 
  • Like
Likes mattt and kent davidge
  • #3
Ray Vickson said:
you can get the answer as ##N_4(12) = \sum_{j=0}^{12} N_3(j).## This is well suited to implementation in a spreadsheet.
Oh good. How can I solve it for the problem in question?
 
  • #4
kent davidge said:
Oh good. How can I solve it for the problem in question?

What is stopping you from doing the calculations?
 
  • #5
Ray Vickson said:
What is stopping you from doing the calculations?
I don't know how to express ##N_{3}(j)## in a solvable way.
 
  • #6
kent davidge said:
I don't know how to express ##N_{3}(j)## in a solvable way.

That does not matter; you can easily figure out the values of ##N_2(j)##, then just add them up to get ##N_3(n)##. Just do arithmetic, until something better comes along.
 
  • Like
Likes kent davidge
  • #7
Would it be

$$N_3 (0): k_1 = -(k_2 + k_3) \ \{ \text{0 solutions, since the k's should be positive integers} \} \\ N_3 (1): k_1 = 1 - (k_2 + k_3) \ \{ \text{2 solutions, 0 or 1} \} \\ ... \ \text{etc up to} \\ N_3 (12): k_1 = 12 - (k_2 + k_3) \ \{ \text{13 solutions, from 0 to 12} \}$$
 
  • #8
kent davidge said:
Would it be

$$N_3 (0): k_1 = -(k_2 + k_3) \ \{ \text{0 solutions, since the k's should be positive integers} \} \\ N_3 (1): k_1 = 1 - (k_2 + k_3) \ \{ \text{2 solutions, 0 or 1} \} \\ ... \ \text{etc up to} \\ N_3 (12): k_1 = 12 - (k_2 + k_3) \ \{ \text{13 solutions, from 0 to 12} \}$$

##N_2(n) = n+1## because we can have ##k_1=0,1,2, \ldots, n## (and then ##k_2 = n - k_1##). We need non-negative integers, not necessarily positive ones, because (presumably) we are allowed to buy 0 of a particular type of car. Therefore, ##N_2(0)=1##, because ##(k_1,k_2) = (0,0)## is a solution of ##k_1+k_2 = 0.##

Similarly, ##N_3(0)=1## and for ##n=1,2, \ldots, 12## we have ##N_3(n) = N_2(0) + N_2(1) + N_2(2) + \cdots + N_2(n)##. In in principle you could work out an explicit formula, using known formulas for sums like ##\sum_{k=1}^n 1## and ##\sum_{k=0}^n k##,.
 
  • Like
Likes kent davidge
  • #9
kent davidge said:

Homework Statement



A man needs to buy 12 cars. There are 4 kinds available. He can buy any number of cars of each kind, the condition being 12 cars in total. In how many ways can he buy the 12 cars?

Homework Equations

The Attempt at a Solution



Hmmm as he can buy any number of each kind my guess is that this is not going to be a simple problem. Using only permutations will not be enough. If we let each kind of car be ##k_i##, then we have ##k_1 + k_2 + k_3 + k_4 = 12## and the problem reduces to finding all possible quadruples ##(k_1, k_2, k_3, k_4)## that satisfy that equation. It turns out that there are 455 possible ways of buying the 12 cars (book answer). How can I procceed?
Are you familiar with the stars and bars method?
 
  • #10
I get $$ \sum_{j=1}^{12} N_{3}(j) = 1 + 2 + ... + 13 = 13 \frac{14}{2} = 91$$ Somehow we need to multiply this by 5 to get 455. Where does the 5 come from?
 
  • #11
tnich said:
Are you familiar with the stars and bars method?
No, but let's see if I get to the result using @Ray Vickson's method.
 
  • #12
kent davidge said:
I get $$ \sum_{j=1}^{12} N_{3}(j) = 1 + 2 + ... + 13 = 13 \frac{14}{2} = 91$$ Somehow we need to multiply this by 5 to get 455. Where does the 5 come from?

No: here you are summing the values of ##N_2(j)##, not ##N_3(j)##!
 
  • #13
No: here you are summing the values of ##N_2(j)##, not ##N_3(j)##!
Oh, I figured it should be $$\sum_{j=0}^{n} \sum_{k=0}^{j} k + 1$$ I solved it with Mathematica and it gives exactly 455! My question, How did you come to your conclusions in post #2? Is it by your self or did you learn of them somewhere?
 
  • #14
Ready to try stars and bars?
 
  • Like
Likes kent davidge
  • #15
kent davidge said:
Oh, I figured it should be $$\sum_{j=0}^{n} \sum_{k=0}^{j} k + 1$$ I solved it with Mathematica and it gives exactly 455! My question, How did you come to your conclusions in post #2? Is it by your self or did you learn of them somewhere?

The basic idea is simple. You can do this on a spreadsheet or a piece of paper. I'll do it with 6 cars to make it easier to write down.

1) You can have any number (up to 6) of the first type of car:

0
1
2
3
4
5
6

2) To get a certain total after two numbers, the previous total must have been less than or equal to that. To get 3 after two numbers, for example, you could have:

0 + 3
1 + 2
2 + 1
3 + 0

That is the sum of the ways to get 0-3 on the first pick.

Then, we can see that there is one way to get 0; two ways to get 1 ( 0 + 1; 1+0), three ways to get 2 (0+2; 1+1; 2+0) etc. This is a general pattern that gives us the number of ways to get ##n## cars after two cars have been picked. Or, in general, the numer of ways to add 2 non-negative integers to get 6 or less:

0 (1 way)
1 (2 ways)
2 (3)
3 (4)
4 (5)
5 (6)
6 (7)

3) We can continue with the third number. This time, to get 3 say, we need the total above to be less than or equal to 3:

0 + 3 (1 way)
1 + 2 (2 ways)
2 + 1 (3 ways)
3 + 0 (4 ways)

So, the number of ways of getting 3 after three numbers is 10 etc:

0 (1)
1 (3)
2 (6)
3 (10)
4 (15)
5 (21)
6 (28)

Note: you should recognise part of Pascal's triangle appearing here.

4) Using the same method for the final number - this time we are only interested in the total being 6 - we simply add up what we have to get a total of 84.

If you look at Pascal's triangle, you can see that in this case we end up with ##\binom{9}{3}##.

That leads on to the stars and bars method ...
 
  • Like
Likes kent davidge
  • #16
@Ray Vickson, @tnich, @PeroK I realized a way for obtaining the result using only permutations. Please tell me if this is similarly in how the stars and bars method works.

Let's say we have 2 types of car and want to buy 3 cars. The leading equation is ##k_1 + k_2 = 3##. This can be solved for ##k_1## to give ##k_1 = 3 - k_2##. For the sack of just knowing how many possibilites are there, we can regard this as a problem of one variable instead of two, because for each value of ##k_2##, ##k_1## assumes a single value under the established conditions (that they must be integer ##\geq 0##).

Now let the set ##\{1,2,3,A,B \}## represent the three times the man buys a car and the two types of car, respectively. We can agree that the elements on the left of a given type of car represents the amount of that type the man buys, e.g., ##12A## means he buys two cars of type A.

The possible rows are obtained by permuting only one type, say A, because this is a problem of one variable, with each of the three times he buys a car. We would not permute the ##\{1,2,3 \}## among themselves because that doesn't matter, neither does the type of car among themselves. The possible rows are $$123 A \\ A231 \\ 1A32 \\ 12A3 $$ This is equal to ##4! / (3! 1!) = 4##. This same reasoning apparently holds for any number of cars the man buys and any number of types of car available.

Maybe I'm messing up things, but this seems to work.
 
  • #17
kent davidge said:
@Ray Vickson, @tnich, @PeroK I realized a way for obtaining the result using only permutations. Please tell me if this is similarly in how the stars and bars method works.

Let's say we have 2 types of car and want to buy 3 cars. The leading equation is ##k_1 + k_2 = 3##. This can be solved for ##k_1## to give ##k_1 = 3 - k_2##. For the sack of just knowing how many possibilites are there, we can regard this as a problem of one variable instead of two, because for each value of ##k_2##, ##k_1## assumes a single value under the established conditions (that they must be integer ##\geq 0##).

Now let the set ##\{1,2,3,A,B \}## represent the three times the man buys a car and the two types of car, respectively. We can agree that the elements on the left of a given type of car represents the amount of that type the man buys, e.g., ##12A## means he buys two cars of type A.

The possible rows are obtained by permuting only one type, say A, because this is a problem of one variable, with each of the three times he buys a car. We would not permute the ##\{1,2,3 \}## among themselves because that doesn't matter, neither does the type of car among themselves. The possible rows are $$123 A \\ A231 \\ 1A32 \\ 12A3 $$ This is equal to ##4! / (3! 1!) = 4##. This same reasoning apparently holds for any number of cars the man buys and any number of types of car available.

Maybe I'm messing up things, but this seems to work.

You can arrive at binomial coefficient answers in two ways, at least: (1) apply the recursive scheme, but before going to the next step, take the trouble to actually evaluate the summations. (2) The stars and bars method.

Here is what I mean by (1): first, if ##N_r(n)## is the number of non-negative integer solutions ##(k_1, k_2, \ldots, k_r)## to the equation ##k+1 + k_2 + \cdots + k_r = n## then we have ##N_2(n) = n+1## for all ##n##, because you can take ##k_1 = 0,1,\ldots, n##. For the same reason, ##N_3(n) = \sum_{k=0}^n N_2(k)##. But, instead of putting this into a spreadsheet (a perfectly acceptable and respectable method), let's push it further, to see if we can get a closed-form formula, by applying formulas for sums like ##\sum 1, \sum k,## etc. We have
$$N_3(n) = \underbrace{\sum_{k=0}^n 1}_{(a)} + \underbrace{ \sum_{k=0}^n k}_{(b)} =
\underbrace{(n+1)}_{(a)} +\underbrace{ \frac{1}{2}n(n+1)}_{(b)} = \frac{(n+1)(n+2)}{2}$$
Note that ##N_2(n) = C(n+1,1)## and ##N_3(n) = C(n+2,2)##, where ##C(a,b)## denotes the binomial coefficient "a choose b".

So, we can either compute ##N_3(n)## recursively, or else compute it as a binomial coefficient.

In a similar way,
$$N_4(n) = \sum_{k=0}^n N_3(k) = \frac{1}{6} (n+3)(n+2)(n+2) = C(n+3,3).$$
To get this we need to use formulas for ##\sum_{k=0}^n 1, \sum_{k=0}^n k## and ## \sum_{k=0}^n k^2##.

Anyway, this gives the answer as ##N_4(12) = C(12+3,3)=C(15,3)=455## as you have already found.
 
Last edited:
  • Like
Likes kent davidge
  • #18
OK. You are going to buy (up to) m types of cars and the total number of cars will be n. So set aside contiguous parking spaces for the cars with enough extra spaces to put orange cones between the different types. Each orange cone will take up one space. You will end up with m groups of cars separated by orange cones. So how many total spaces will you need? How many ways are there to choose which spaces the (identical) orange cones will go in?
kent davidge said:
@Ray Vickson, @tnich, @PeroK I realized a way for obtaining the result using only permutations. Please tell me if this is similarly in how the stars and bars method works.

Let's say we have 2 types of car and want to buy 3 cars. The leading equation is ##k_1 + k_2 = 3##. This can be solved for ##k_1## to give ##k_1 = 3 - k_2##. For the sack of just knowing how many possibilites are there, we can regard this as a problem of one variable instead of two, because for each value of ##k_2##, ##k_1## assumes a single value under the established conditions (that they must be integer ##\geq 0##).

Now let the set ##\{1,2,3,A,B \}## represent the three times the man buys a car and the two types of car, respectively. We can agree that the elements on the left of a given type of car represents the amount of that type the man buys, e.g., ##12A## means he buys two cars of type A.

The possible rows are obtained by permuting only one type, say A, because this is a problem of one variable, with each of the three times he buys a car. We would not permute the ##\{1,2,3 \}## among themselves because that doesn't matter, neither does the type of car among themselves. The possible rows are $$123 A \\ A231 \\ 1A32 \\ 12A3 $$ This is equal to ##4! / (3! 1!) = 4##. This same reasoning apparently holds for any number of cars the man buys and any number of types of car available.

Maybe I'm messing up things, but this seems to work.
Yes, that is the stars and bars approach. The usual representation is to substitute asterisks for your numerals and vertical lines for your letters like this:
***|
**|*
*|**
|***

As @Ray Vickson points out, you can find the binomial coefficients using formulas for sums of ##x^n##. You can also do it by turning Pascal's triangle on it's ear like this:
##\begin{matrix}
& k & 0 & 1 & 2 & 3 & 4 & 5 & . . . \\
n \\
0 & & 1 & 0 & 0 & 0 & 0 & 0 & . . . \\
1 & & 1 & 1 & 1 & 1 & 1 & 1 & . . . \\
2 & & 1 & 2 & 3 & 4 & 5 & 6 & . . . \\
3 & & 1 & 3 & 6 & 10 & 15 & 21 & . . .\\
5 & & 1 & 4 & 10 & 20 & 35 & 56 & . . .\\
\vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &
\end{matrix}##

Call this matrix D. In this form, it is easy to see that each column provides a running total of the column to its left, because ##D(n,k) = D(n-1,k) + D(n,k-1)##. It is also easy to see that ##D(n,k) = \begin{pmatrix} n+k-1\\k\end{pmatrix}##. That gives you an easy way to calculate those sums of sums of sums.
 
  • Like
Likes kent davidge and StoneTemplePython
  • #19
tnich said:
OK. You are going to buy (up to) m types of cars and the total number of cars will be n. So set aside contiguous parking spaces for the cars with enough extra spaces to put orange cones between the different types. Each orange cone will take up one space. You will end up with m groups of cars separated by orange cones. So how many total spaces will you need? How many ways are there to choose which spaces the (identical) orange cones will go in?

Yes, that is the stars and bars approach. The usual representation is to substitute asterisks for your numerals and vertical lines for your letters like this:
***|
**|*
*|**
|***

As @Ray Vickson points out, you can find the binomial coefficients using formulas for sums of ##x^n##. You can also do it by turning Pascal's triangle on it's ear like this:
##\begin{matrix}
& k & 0 & 1 & 2 & 3 & 4 & 5 & . . . \\
n \\
0 & & 1 & 0 & 0 & 0 & 0 & 0 & . . . \\
1 & & 1 & 1 & 1 & 1 & 1 & 1 & . . . \\
2 & & 1 & 2 & 3 & 4 & 5 & 6 & . . . \\
3 & & 1 & 3 & 6 & 10 & 15 & 21 & . . .\\
5 & & 1 & 4 & 10 & 20 & 35 & 56 & . . .\\
\vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &
\end{matrix}##

Call this matrix D. In this form, it is easy to see that each column provides a running total of the column to its left, because ##D(n,k) = D(n-1,k) + D(n,k-1)##. It is also easy to see that ##D(n,k) = \begin{pmatrix} n+k-1\\k\end{pmatrix}##. That gives you an easy way to calculate those sums of sums of sums.

The standard answer to this question is ##{n+k-1, \choose k-1},## as given in numerous sources.
 
  • #20
Ray Vickson said:
The standard answer to this question is ##{n+k-1, \choose k-1},## as given in numerous sources.
It depends on what you call n and what you call k.
##\begin{pmatrix} n+k-1\\k-1\end{pmatrix} = \begin{pmatrix} n+k-1\\n\end{pmatrix}##
 
  • #21
This problem has lots of names -- one of which is combinations of multi-sets. A nice summary table is:

##
\begin{bmatrix}
&\text{replacement allowed} & \text{replacement NOT allowed}\\
\text{order does matter} & k^n & P(n,k) \\
\text{order does NOT matter} & \text{this problem} & C(n,k)
\end{bmatrix}##

Hopefully complementary to the bijective / stars and bars approach: there is a nice generating function approach on page 22 of this:

https://ocw.mit.edu/courses/electri...ce-fall-2010/readings/MIT6_042JF10_chap12.pdf

- - - -
I wouldn't recommend starting with with generating functions, but they come at things from a different angle and this one is pretty straightforward.
 
  • Like
Likes kent davidge
  • #22
tnich said:
It depends on what you call n and what you call k.
##\begin{pmatrix} n+k-1\\k-1\end{pmatrix} = \begin{pmatrix} n+k-1\\n\end{pmatrix}##

Right, but neither of these is equal to ##{n+k-1 \choose k}##.

Anyway, all through this thread the concern was to count the number of solutions of ##x_1+x_2+ \cdots + x_k = n##, assuming restriction either to positive integers or to non-negative integers. The latter has answer ##{n+k-1 \choose k-1} = {n+k-1 \choose n},## while the former has answer ##{n-1 \choose k-1}.##
 
  • #23
Ray Vickson said:
Right, but neither of these is equal to ##{n+k-1 \choose k}##.
Back to my point that it depends on what you call n and what you call k. If you swapped your definitions of n and k, then our formulas would agree.
 
Last edited:
  • #24
  • #25
kent davidge said:
@tnich, @Ray Vickson thank you for your explanations

@StoneTemplePython The pdf you linked is amazing

@Ray Vickson I would just like to ask you how can we see that ##N_3 (n) = \sum_{j=0}^{n} N_2 (j)##. I still don't see it.

What is the number of solutions to ##x_1 + x_2 + x_3 = n,## assuming all ##x_i \geq 0 ## are integers? Well, if ##x_1 = n## there is just one solution, which is ##N_2(0),## the number of solutions to ##x_2+x_3 = 0.## If ##x_1 = n-1## we need to know the number of solutions to ##x_2+x_3 = 1##, because each such solution to the 2-summand problem gives us a different solution to the 3-summand problem. The number of solutions to ##x_2+x_3 = 1## is our previously-computed number ##N_2(1).##

Continue like that: if ##x_1 = n-k## the number of solutions is the number of ways of getting ##x_2+x_3 = k##, and that is ##N_2(k).## We have to add up all the possibilities for the different possible values of ##x_1##.
 
Last edited:
  • Like
Likes kent davidge
  • #26
I got it
 

Related to Man needs to buy cars (combinatorics)

1. How many different ways can a man buy a car?

The number of different ways a man can buy a car depends on several factors such as the type of car, the payment method, and the dealership. It is difficult to give an exact number, but it can be calculated using combinatorics principles.

2. What are the possible combinations of car features a man can choose from?

The number of possible combinations of car features is infinite, as there are countless car models with various combinations of features. It also depends on the man's preferences and budget.

3. How does combinatorics play a role in buying cars?

Combinatorics plays a crucial role in buying cars as it helps in calculating the number of possible outcomes and combinations when making decisions about the type of car, features, and payment method.

4. Are there any strategies based on combinatorics that can help a man make a car buying decision?

Yes, there are strategies based on combinatorics that can help a man make a car buying decision. For example, using the combination formula to determine the number of possible outcomes and then narrowing down the options based on personal preferences and budget.

5. Can combinatorics be used to optimize the car buying process?

Yes, combinatorics can be used to optimize the car buying process by helping to determine the most efficient way to make a decision. For instance, using the permutation formula to calculate the number of different orders in which a man can test drive different car models before making a final decision.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
32
Views
987
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
10
Views
2K
  • Advanced Physics Homework Help
Replies
20
Views
1K
  • Advanced Physics Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
  • Introductory Physics Homework Help
Replies
17
Views
4K
  • Precalculus Mathematics Homework Help
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
1K
Back
Top