Math Is Fun Forum

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

You are not logged in.

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Race with possibility of ties (permutations!)

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

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

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

Re: Race with possibility of ties (permutations!)

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


Why did the vector cross the road?
It wanted to be normal.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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)


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

Then you saw this cute one:


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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


"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

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

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

Re: Race with possibility of ties (permutations!)

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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.


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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)


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

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


"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

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

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

Re: Race with possibility of ties (permutations!)

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

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

Yes, we are all here to enjoy the math!


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Race with possibility of ties (permutations!)

Hi bobbym,

Thanks for trying that out smile


"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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Race with possibility of ties (permutations!)

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB