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 !

"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" <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
> ? 
>
> 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" <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
> Y 
be 
> working 
upper 
that 
> the 
any 
>
> 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:
> [url]http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi[/url
]
>
> -- 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 :)

"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 
can be 
upper 
that 
to 
any 
http://www.research.att.com/cgi-bin...nces/eismum.cgi 
>
>
> 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 
>  [url]http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi[/ur
l] 
>
> 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 networ
k field.


Regards,
Ray