Home > Archive > Compression > November 2004 > mathematic combination of steps
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
mathematic combination of steps
|
|
|
| I have a problem like this,...
I have a pigeon hole like the below
X is where the pigeon stay
Y is where the pigeon want to go..
The rules is X can only move 1 step to the right at anytime
for the diagram below.. X can 3 choice of movement.
when x reach column 2 x can have N choices of movement depend on the choice
of first movement,... and so and so...
[ ]
[ ][ ][ ]
[ ][ ][ ][ ][ ]
[X][ ][ ][ ][ ][ ][Y]
[ ][ ][ ][ ][ ]
[ ][ ][ ]
[ ]
the Question is
How many route X can take to go to Y ?
and
If I enlarge the pigeon hole with more holes but shape the same
how could I formulate a formula to count the number of ways X can go to Y ?
Regards,
Ray
- I am mathematically dumb... anyone could help me !
| |
| Matt Mahoney 2004-11-08, 3:55 pm |
| "Ray" <nibanna@gmail.com> wrote in message
news:1759ba58.0411080056.1af4280e@posting.google.com...
> I have a problem like this,...
>
> I have a pigeon hole like the below
> X is where the pigeon stay
> Y is where the pigeon want to go..
>
> The rules is X can only move 1 step to the right at anytime
> for the diagram below.. X can 3 choice of movement.
> when x reach column 2 x can have N choices of movement depend on the
choice
> of first movement,... and so and so...
>
>
> [ ]
> [ ][ ][ ]
> [ ][ ][ ][ ][ ]
> [X][ ][ ][ ][ ][ ][Y]
> [ ][ ][ ][ ][ ]
> [ ][ ][ ]
> [ ]
>
> the Question is
> How many route X can take to go to Y ?
>
> and
>
> If I enlarge the pigeon hole with more holes but shape the same
>
> how could I formulate a formula to count the number of ways X can go to Y
?
>
>
>
> Regards,
> Ray
>
> - I am mathematically dumb... anyone could help me !
I am not sure what this has to do with compression, but the problem can be
solved by dynamic programming. Put a 1 in the leftmost hole. Then working
left to right, put in each hole the sum of the 3 boxes to the left, upper
left and lower left. This is the number of paths to that hole. Note that
all of the holes to the left of the diamond will be 0, and all holes to the
right don't need to be computed. You end up with this:
1
1 3 10
1 2 6 16 45
1 1 3 7 19 51 141
1 2 6 16 45
1 3 10
1
So for this case the answer is 141, and you can use this algorithm for any
size array.
There might be a closed form solution, but I don't know of one.
-- Matt Mahoney
| |
| Matt Mahoney 2004-11-08, 3:55 pm |
|
"Matt Mahoney" <matmahoney@yahoo.com> wrote in message
news:X5Ojd.8678$Gm6.6010@newsread3.news.atl.earthlink.net...
> "Ray" <nibanna@gmail.com> wrote in message
> news:1759ba58.0411080056.1af4280e@posting.google.com...
> choice
Y[color=darkred]
> ?
>
> I am not sure what this has to do with compression, but the problem can be
> solved by dynamic programming. Put a 1 in the leftmost hole. Then
working
> left to right, put in each hole the sum of the 3 boxes to the left, upper
> left and lower left. This is the number of paths to that hole. Note that
> all of the holes to the left of the diamond will be 0, and all holes to
the
> right don't need to be computed. You end up with this:
>
> 1
> 1 3 10
> 1 2 6 16 45
> 1 1 3 7 19 51 141
> 1 2 6 16 45
> 1 3 10
> 1
>
> So for this case the answer is 141, and you can use this algorithm for any
> size array.
>
> There might be a closed form solution, but I don't know of one.
There is. I searched on the sequence and found this:
http://www.research.att.com/cgi-bin...nces/eismum.cgi
-- Matt Mahoney
| |
| Matt Mahoney 2004-11-08, 8:55 pm |
|
"Matt Mahoney" <matmahoney@yahoo.com> wrote in message
news:YmOjd.8728$Gm6.1542@newsread3.news.atl.earthlink.net...
>
> "Matt Mahoney" <matmahoney@yahoo.com> wrote in message
> news:X5Ojd.8678$Gm6.6010@newsread3.news.atl.earthlink.net...
to[color=darkred]
> Y
be[color=darkred]
> working
upper[color=darkred]
that[color=darkred]
> the
any[color=darkred]
>
> There is. I searched on the sequence and found this:
>
http://www.research.att.com/cgi-bin...nces/eismum.cgi
That didn't work. Try http://www.research.att.com/~njas/sequences/ and
search for 1 1 3 7 19 51 141
-- Matt Mahoney
| |
|
| "Matt Mahoney" <matmahoney@yahoo.com> wrote in message news:<YmOjd.8728$Gm6.1542@newsread3.news.atl.earthlink.net>...
> "Matt Mahoney" <matmahoney@yahoo.com> wrote in message
> news:X5Ojd.8678$Gm6.6010@newsread3.news.atl.earthlink.net...
> choice
> Y
> ?
> working
> the
>
> There is. I searched on the sequence and found this:
> http://www.research.att.com/cgi-bin...nces/eismum.cgi
>
> -- Matt Mahoney
Thanks Matt.
You had helped alot. I was trying to move pigeon in pigeon hole...
Matt, where you study mathematics ? could you teach me ? pls... I
never got more then 60 marks in school. and even worse now.. I am
working.
Regards,
Ray
- we rejoice a smaller world :)
| |
| Matt Mahoney 2004-11-09, 8:55 pm |
|
"Ray" <nibanna@gmail.com> wrote in message
news:1759ba58.0411081715.32012245@posting.google.com...
> "Matt Mahoney" <matmahoney@yahoo.com> wrote in message
news:<YmOjd.8728$Gm6.1542@newsread3.news.atl.earthlink.net>...
to[color=darkred]
can be[color=darkred]
upper[color=darkred]
that[color=darkred]
to[color=darkred]
any[color=darkred]
http://www.research.att.com/cgi-bin...nces/eismum.cgi[color=darkred]
>
>
> Thanks Matt.
>
>
> You had helped alot. I was trying to move pigeon in pigeon hole...
> Matt, where you study mathematics ? could you teach me ? pls... I
> never got more then 60 marks in school. and even worse now.. I am
> working.
Well, yes, if you were going to Florida Tech., but I teach mostly
programming.
-- Matt Mahoney
| |
|
| "Matt Mahoney" <matmahoney@yahoo.com> wrote in message news:<aWbkd.10272$Gm6.3700@newsread3.news.atl.earthlink.net>...
> "Ray" <nibanna@gmail.com> wrote in message
> news:1759ba58.0411081715.32012245@posting.google.com...
> news:<YmOjd.8728$Gm6.1542@newsread3.news.atl.earthlink.net>...
> choice
> to
> can be
> working
> upper
> that
> to
> the
> any
> http://www.research.att.com/cgi-bin...nces/eismum.cgi
>
> Well, yes, if you were going to Florida Tech., but I teach mostly
> programming.
>
> -- Matt Mahoney
okay... if I do well in my work maybe I can have enough money to go there.. lol
anyway.. thanks.. I am a programmer too, a c/c++ programmer in mobile network field.
Regards,
Ray
|
|
|
|
|