Author |
Topic: Horse race (Read 692 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
In how many ways, counting ties, can 8 horses go through the finish?
(For example, two horses can finish in three different ways: A then B, B then A, A and B tie.)
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
LZJ
Junior Member
Gender:
Posts: 82
|
 |
Re: Horse race
« Reply #1 on: May 10th, 2003, 4:35am » |
 Quote  Modify
|
Well, my first guess would be Summation(n!) from n = 1 to n = 8
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Horse race
« Reply #2 on: May 10th, 2003, 5:11am » |
Quote Modify
|
Quote:| Well, my first guess would be Summation(n!) from n = 1 to n = 8 |
|
This would give an answer of 6 for 3 horses.
But there are 3! = 6 ways for the horses to finish, even without dead-heats (ties).
|
| « Last Edit: May 10th, 2003, 5:12am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
LZJ
Junior Member
Gender:
Posts: 82
|
|
Re: Horse race
« Reply #3 on: May 10th, 2003, 11:11pm » |
Quote Modify
|
Nope, it would give 9 ways for 3 horses: 1! + 2! + 3! = 9.
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Horse race
« Reply #4 on: May 11th, 2003, 12:06am » |
Quote Modify
|
Oh, but there are 13 ways for 3 horses:
1. a>b>c
2. a>c>b
3. b>a>c
4. b>c>a
5. c>a>b
6. c>b>a
7. a=b>c
8. a=b<c
9. a=c>b
10. a=c<b
11. b=c>a
12. b=c<a
13. a=b=c
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
LZJ
Junior Member
Gender:
Posts: 82
|
|
hMMRe: Horse race
« Reply #5 on: May 11th, 2003, 12:51am » |
Quote Modify
|
Thanks, my bad. I forgot that for 2 or more horses having a tie, the intermediary terms should be multiplied by a factor of nCr, where n is the total number of horses, and r is the number of horses tied. Furthermore, I didn't account for more than 1 position tied together: for example,
A=B>C>D=E
Was sleepy last night. 
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Horse race
« Reply #6 on: May 11th, 2003, 11:58am » |
Quote Modify
|
I come up with 545835.
I used a spreadsheet and found the 22 ways of dividing into groups:
8 differently ranked individual horses, no ties;
6 differently ranked individual horses, 1 tie with 2 horses;
5 individual, 1 tie involving 3 horses;
...
1 individual, 2 ties one involving 4 horses, one with 3
...
For each category, it is relatively easy to evaluate the number of permutations.
Also, I double checked by figuring out how many ways 8 horses can assigned N different places with each place from 1 to N assigned to at least one horse (but multiple horses in the same place permitted). Then added for N=1 to 8.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Horse race
« Reply #7 on: May 12th, 2003, 12:07pm » |
Quote Modify
|
For n horses, it is the number of ways of partitioning a set of n indistinguishable elements into non-empty distinguishable ordered sets, where set membership is equivalent to being tied with other members of the set.
n
This is given by SIGMA k! S(n,k) where S(n,k) are Stirling numbers of the second kind.
k=1
See http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
They are called ordered Bell numbers:
1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, 1622632573, 28091567595, 526858348381, 10641342970443, 230283190977853, 5315654681981355, 130370767029135901, 3385534663256845323
|
| « Last Edit: May 13th, 2003, 9:39pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
LZJ
Junior Member
Gender:
Posts: 82
|
|
Re: Horse race
« Reply #8 on: May 14th, 2003, 4:40am » |
Quote Modify
|
Got it too, but I didn't know about the ordered Bell numbers.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print