Race with possibility of ties (permutations!)

gAr · 2011-01-11 23:38:19

How many ways are there for a horse race with 6 horses to finish if ties are possible?

It somewhat looks like a multiset problem to me, but a finish like 1,3,3,5,5,5 isn't possible. Is there a solution other than by cases?
Can we generalise to n horses?

mathsyperson · 2011-01-12 01:21:24

I think the best way to do this is to build up from one horse.

With a one-horse race, there's only one way it can finish: [1].

With a two-horse race, the finish can either be [1,1] or [1,2].

With three horses, one of three things happens:

All horses tie.
The first two horses tie.
One horse gets an outright finish.

So the finishes for these would respectively look like [1,1,1]; [1,1,?]; [1,?,?].

To fill in the question marks, we can refer back to our results for the smaller races.
We know that there is one way to finish a one-horse race, and two ways to finish a two-horse race.

Therefore, all the ways a 3-horse race can finish are:

[1,1,1]
[1,1,3]
[1,2,2]
[1,2,3]

We can do a similar thing with 4-horse races.
First we observe that there are four patterns of firsts possible:
[1,1,1,1]
[1,1,1,?]
[1,1,?,?]
[1,?,?,?]

Then we refer back to every smaller race to fill in the blanks:

[1,1,1,1]
[1,1,1,4]
[1,1,3,3]
[1,1,3,4]
[1,2,2,2]
[1,2,2,4]
[1,2,3,3]
[1,2,3,4]

You should now be able to see a clear pattern in the number of results possible for n horses.

gAr · 2011-01-12 01:48:19

Mathsy, we must treat horses to be distinct... E.g. there are 13 ways for 3 horses to finish the race.

bobbym · 2011-01-12 04:46:59

Hi gAr;

May I see those 13 ways for 3 horses. Can you list them?

gAr · 2011-01-12 04:58:27

Hi bobbym,

I'll tell how I calculated it.
When race results in -
1: No tie - i.e. [1 2 3] - the possibility is 3! ways
2: All tie - [1 1 1] - 1 way
3: 2 finish second -[1 2 2] - 3!/2! = 3 ways
4: 2 finish first - [1 1 2] - 3!/2! = 3 ways.

Hence totals to 13 ways. I hope I'm clear.

bobbym · 2011-01-12 05:27:39

Hi gAr;

My notes have this:

Your answers are called the ordered bell numbers:

{1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261,...}

They can be computed by this sum for 3.

Where that big S are stirling numbers of the second kind. There is no known closed form for this problem.

gAr · 2011-01-12 06:01:29

Wow! I see, Stirling's number of second kind.
But who saw it first, Stirling or Bell?!

Last edited by gAr (2011-01-12 06:05:17)

bobbym · 2011-01-12 06:04:21

Hi;

A whole list of people. A closed form is not likely.

Go here:

http://www.qbyte.org/puzzles/p131s.html

This problem is related to the well known combination lock problem:

http://mathworld.wolfram.com/CombinationLock.html

gAr · 2011-01-12 06:08:11

Yes, I went exactly to those two pages before replying
Thanks...

bobbym · 2011-01-12 06:10:56

Then you saw this cute one:

gAr · 2011-01-12 14:50:37

Yes, that's cute indeed! Amazing...

4DLiVing · 2011-01-12 15:22:45

Hi gAr and bobbym;

I approached this problem by looking at the ways the race could finish, based on the number of ties possible.

For 1 horse, 0 ties are possible.
For 2 horses, 0 ties and 2 ties are possible.
For 3 horses, 0, 2, and 3 ties are possible.
For 4 horses, 0, 2, 3, and 4 ties are possible. etc.

The number of ways that the places(1st, 2nd, 3rd, 4th, etc.) can be assigned to all the horses, ties included, has given me this triangle.
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 8 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1

Lets look at the 4th row, when 4 horses are racing.

The first number tells us that there is 1 way to assign the finishing places of the race if there is 0 ties (1 2 3 4), which has 4! = 24 possible outcomes.

The second number tells us that there are 2 ways to assign the finishing places of the race if 2 horses tie (2 2) and (2 1 1) which has
2!/2!(4!/2!2!) + 3!/2!1!(4!/2!1!1!) = 1(6) + 3(12) = 42 possible outcomes.

The third number tells us that there is 1 way to assign the finishing places to the race if 3 horses tie (3 1) which has 2!/1!1!(4!/3!1!) = 2(4) = 8 possible outcomes.

The fourth number tells us that there is 1 way to assign the finishing places to the race if 4 horses tie (4) which has 1!/1!0! = 1 outcome.

Which gives us a total of 24 + 42 + 8 + 1 = 75 outcomes.

I was wondering if one of you two can notice a pattern in the triangle that will give us the next line.

I did notice bobbym that you did some research and noted that a closed form is not likely.

Would this indicate that there is not a pattern that we could find to predict the next line in this triangle?

Last edited by 4DLiVing (2011-01-13 13:38:14)

bobbym · 2011-01-12 16:07:38

Would this indicate that there is not a pattern that we could find to predict the next line in this triangle?

Hi 4DLiVing;

A pattern in your table is possible. Although I am not seeing one. Finding that pattern does not imply that there is a closed form.

So everybody knows what is already known about this problem.

This difference equation generates the table below.
S(n + 1, k) = S(n, k − 1) + kS(n, k)
S(n, 1) = S(n, n) = 1

These are the stirling numbers of the second kind. Now for an 8 horse trace.

That is the formula I posted already. When we expand it out we get.

Hi 4DLiVing;

As a partial answer to your question although there is a pattern in the above table there is no closed form known for it.

gAr · 2011-01-12 17:37:37

Hi 4DLiVing,
I can't say for now. It may be possible to derive the next line, like finding numbers in bell triangle or pascal triangle, but a closed form may not exist.

Hi bobbym,
Has anyone proved that a closed form cannot exist for recurrences like Stirling numbers? Is there any approximation like stirling's approximation for n! ?

bobbym · 2011-01-12 18:14:17

Hi;

Has anyone proved that a closed form cannot exist for recurrences like Stirling numbers?

I do not think it has been proven but no closed form has been found for that recursion.

Is there any approximation like stirling's approximation for n!

Yes, there are approximations for large n

gAr · 2011-01-12 19:22:14

Thanks bobbym, that's nice.
I didn't know the approximation was that simple... Should n be very large? I saw that the approximation deviated rapidly for n=300.

bobbym · 2011-01-12 19:35:26

What are you using to do the calculations I am getting good results for even small numbers for instance:

S(40, 5 ) ≈ 7.57408542517 * 10^25

Using the first one.

(5^40) / 5! ≈ 7.57912251 * 10^25

That is a pretty good approximation but it decays rapidly.

They came from here.

http://dlmf.nist.gov/26.8#SS7.p4

near the bottom. I do not think they are very good either.

gAr · 2011-01-12 19:53:10

I was checking the difference. On seeing its order of magnitude, I felt like that...
Thanks for the link.

Last edited by gAr (2011-01-12 19:55:42)

bobbym · 2011-01-12 20:01:23

Hi gAr;
I will look around for something else and post as soon I see something that looks promising.

gAr · 2011-01-12 20:36:05

Thank you bobbym.
Once I know enough, I'll also start

4DLiVing · 2011-01-12 23:09:14

Thanks bobbym and gAr for looking into the triangle for me.

My mind is continuing to expand on this site!

It is exactly what I have needed and have been looking for!

gAr · 2011-01-12 23:26:09

Yes, we are all here to enjoy the math!

bobbym · 2011-01-13 08:45:28

Hi gAr;

The literature for an asymptotic approximation is scarce. Seems like they are holding on to that one. I did some work on one myself.

While trying to get my own this one pops up

It was not as bad as we thought because we are using it wrong. There are improvements to it but the amount calculation grows with each one.

gAr · 2011-01-13 15:02:10

Hi bobbym,

Thanks for trying that out

bobbym · 2011-01-13 21:04:07

Hi;

This monstrosity will respond well for values where n ≥ 5k

It also might blow up for some particular values. It was done using the Riemann Rearrangement Algorithm.

Math Is Fun Forum

#1 2011-01-11 23:38:19

Race with possibility of ties (permutations!)

#2 2011-01-12 01:21:24

Re: Race with possibility of ties (permutations!)

#3 2011-01-12 01:48:19

Re: Race with possibility of ties (permutations!)

#4 2011-01-12 04:46:59

Re: Race with possibility of ties (permutations!)

#5 2011-01-12 04:58:27

Re: Race with possibility of ties (permutations!)

#6 2011-01-12 05:27:39

Re: Race with possibility of ties (permutations!)

#7 2011-01-12 06:01:29

Re: Race with possibility of ties (permutations!)

#8 2011-01-12 06:04:21

Re: Race with possibility of ties (permutations!)

#9 2011-01-12 06:08:11

Re: Race with possibility of ties (permutations!)

#10 2011-01-12 06:10:56

Re: Race with possibility of ties (permutations!)

#11 2011-01-12 14:50:37

Re: Race with possibility of ties (permutations!)

#12 2011-01-12 15:22:45

Re: Race with possibility of ties (permutations!)

#13 2011-01-12 16:07:38

Re: Race with possibility of ties (permutations!)

#14 2011-01-12 17:37:37

Re: Race with possibility of ties (permutations!)

#15 2011-01-12 18:14:17

Re: Race with possibility of ties (permutations!)

#16 2011-01-12 19:22:14

Re: Race with possibility of ties (permutations!)

#17 2011-01-12 19:35:26

Re: Race with possibility of ties (permutations!)

#18 2011-01-12 19:53:10

Re: Race with possibility of ties (permutations!)

#19 2011-01-12 20:01:23

Re: Race with possibility of ties (permutations!)

#20 2011-01-12 20:36:05

Re: Race with possibility of ties (permutations!)

#21 2011-01-12 23:09:14

Re: Race with possibility of ties (permutations!)

#22 2011-01-12 23:26:09

Re: Race with possibility of ties (permutations!)

#23 2011-01-13 08:45:28

Re: Race with possibility of ties (permutations!)

#24 2011-01-13 15:02:10

Re: Race with possibility of ties (permutations!)

#25 2011-01-13 21:04:07

Re: Race with possibility of ties (permutations!)

Board footer