Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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?

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Why did the vector cross the road?

It wanted to be normal.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

Hi gAr;

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

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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.

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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)*

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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:

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Yes, I went exactly to those two pages before replying

Thanks...

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

Then you saw this cute one:

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**4DLiVing****Member**- Registered: 2011-01-08
- Posts: 22

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)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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! ?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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)*

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

Hi gAr;

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

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Thank you bobbym.

Once I know enough, I'll also start

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**4DLiVing****Member**- Registered: 2011-01-08
- Posts: 22

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!

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Yes, we are all here to enjoy the math!

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

Thanks for trying that out

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 87,164

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline