Man needs to buy cars (combinatorics)

[kent davidge]

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?

 

[Ray Vickson]

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.

 

[kent davidge]

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?

 

[Ray Vickson]

Oh good. How can I solve it for the problem in question?

What is stopping you from doing the calculations?

 

[kent davidge]

What is stopping you from doing the calculations?

I don't know how to express $N_{3}(j)$ in a solvable way.

 

[Ray Vickson]

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.

 

[kent davidge]

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} \}$$

 

[Ray Vickson]

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$,.

 

[tnich]

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?

 

[kent davidge]

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?

 

[kent davidge]

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.

 

[Ray Vickson]

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)$!

 

[kent davidge]

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?

 

[tnich]

Ready to try stars and bars?

 

[PeroK]

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 ...

 

[kent davidge]

@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.

 

[Ray Vickson]

@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.

 

[tnich]

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?

@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.

 

[Ray Vickson]

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.

 

[tnich]

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}$

 

[StoneTemplePython]

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.

 

[Ray Vickson]

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}.$

 

[tnich]

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.

 

[kent davidge]

@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.

 

[Ray Vickson]

@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$.

 

[kent davidge]

I got it