I've been working on a problem my friend posed he calls the "Car and Garage" problem. For a given N, where you have doors label 1 to N and cars numbered 1 to N, how many valid ways are there to garage all five cars where you cannot place a car it a garage of the same number. For example, car #1 cannot go in garage #1. This is fairly simple to calculate by hand up to about N=5 or 6, and uses factorials. I am now stuck trying to boil down the general expression for N garages/cars. I believe I have found the answer, but I don't know how to write it as an equation. I presume summation notation, but the number of terms in each expression is dependent on N, and the series/terms vary for odd and even N values....I will explain:
The answer is N! minus N series (N of the rows below), where the series are:
For example, in the four car/garage case, N=4. We add the first four rows and subtract from N!:
The answer is N! - [(n-1)!]+[(n-1)!-(n-2)!]+[(n-1)!-2(n-2)!+(n-3)!]+[(n-1)!-3(n-2)!+3(n-3)!-(n-4)!].
Plugging in 4=N:
4! - [(4-1)!]+[(4-1)!-(4-2)!]+[(4-1)!-2(4-2)!+(4-3)!]+[(4-1)!-3(4-2)!+3(4-3)!-(4-4)!].
= 4! - [(3)!]+[(3)!-(2)!]+[(3)!-2(2)!+(1)!]+[(3)!-3(2)!+3(1)!-(0)!].
= 24 - [(6)]+[(6)-(2)]+[(6)-2(2)+(1)]+[(6)-3(2)+3(1)-(1)].
= 24 - [6+4+3+2]
= 24 - 15
= 9
There are patterns in the series above. Obviously (n-1)! is common and can probably be factored out. The exponents follow a seemingly recursive pattern (i.e. the difference of the third and fourth exponents in the fourth series -(-3 minus +3) is fourth exponent in the fourth series (+6). This is true for all the exponents, in that the previous series term dictates the exponent.
Any ideas on how to write the sum of the the entire table (1st term/series + 2nd term/series + 3rd term series +....... Nth term series) ?
The answer is N! minus N series (N of the rows below), where the series are:
| First term/series: | (n-1)! |
| Second term/series: | (n-1)!-(n-2)! |
| Third term/series: | (n-1)!-2(n-2)!+(n-3)! |
| Fourth term/series: | (n-1)!-3(n-2)!+3(n-3)!-(n-4)! |
| Fifth term/series: | (n-1)!-4(n-2)!+6(n-3)!-4(n-4)!+(n-5)! |
| Sixth term/series: | (n-1)!-5(n-2)!+10(n-3)!-10(n-4)!+5(n-5)!-(n-6)! |
For example, in the four car/garage case, N=4. We add the first four rows and subtract from N!:
The answer is N! - [(n-1)!]+[(n-1)!-(n-2)!]+[(n-1)!-2(n-2)!+(n-3)!]+[(n-1)!-3(n-2)!+3(n-3)!-(n-4)!].
Plugging in 4=N:
4! - [(4-1)!]+[(4-1)!-(4-2)!]+[(4-1)!-2(4-2)!+(4-3)!]+[(4-1)!-3(4-2)!+3(4-3)!-(4-4)!].
= 4! - [(3)!]+[(3)!-(2)!]+[(3)!-2(2)!+(1)!]+[(3)!-3(2)!+3(1)!-(0)!].
= 24 - [(6)]+[(6)-(2)]+[(6)-2(2)+(1)]+[(6)-3(2)+3(1)-(1)].
= 24 - [6+4+3+2]
= 24 - 15
= 9
There are patterns in the series above. Obviously (n-1)! is common and can probably be factored out. The exponents follow a seemingly recursive pattern (i.e. the difference of the third and fourth exponents in the fourth series -(-3 minus +3) is fourth exponent in the fourth series (+6). This is true for all the exponents, in that the previous series term dictates the exponent.
Any ideas on how to write the sum of the the entire table (1st term/series + 2nd term/series + 3rd term series +....... Nth term series) ?
