/sci/ - Science & Math

[Anonymous No.6572050]

So I was on a plane most of the day and was doodling on my tablet when I came up with this question:
Given two points in the taxicab metric space (the Euclidean space with taxicab metric) where the horizontal distance between the two points equals the vertical distance between the two points, how many unique paths between the points are there so that the path is as short as possible?
If <span class="math">r = [/spoiler] horizontal distance
<span class="math">r = 1 \to[/spoiler] 2 paths
<span class="math">r = 2 \to[/spoiler] 4 paths
<span class="math">r = 3 \to[/spoiler] 12 paths
<span class="math">r = 4 \to[/spoiler] 32 paths
What about <span class="math"> r = k[/spoiler]?
It seems pretty obvious that induction should be used, but I'm having trouble knowing how to set it up.
Any help? I've been thinking about this for a while and it's really irritating me...
Pic highly related.

[Anonymous No.6572065]

>>6572050
that shits related to pascals triangle, believe it or not. I've been shitting my brains out the last few day over something similar
this is actually pretty simple, if you lay out pascals triangle on that grid, with the first one in the corner, and they add up towards the opposite corner
the square (or vertex) where each number lands is going to be the number of optimal paths to that point
in short;
<div class="math"> r = k \rightarrow \binom{2k}{k} </div>

[Anonymous No.6572068]

<span class="math">{2k \choose k}[/spoiler]

[Anonymous No.6572070]

>>6572065
sci cant do nCr, ill have to botch it
<div class="math"> r = k \rightarrow \, _{(2k)} C_{k} </div>

[Anonymous No.6572071]

>>6572068
How did you do it, good sir?

[Anonymous No.6572074]

>>6572065
>>6572068

>>6572070
Oh wow. Okay thanks.
I was totally going down a different path, no pun intended.
How do you do binomial coefficients here anyway?

[Anonymous No.6572081]

>>6572074
<div class="math"> \left 2k\choose{k} \right </div>
I forgot that you can double click latex and itll show you what they typed
\left 2k\choose{k} \right

[Anonymous No.6572084]

>>6572074
You can double-click rendered jsMath to see the source.

[Anonymous No.6572093]

>>6572074

It might be easier to understand if you enumerate the different paths as "lists" instead of drawing them out. e.g, r = 2 has the following 6 paths:

(R,R,L,L)
(R,L,R,L)
(R,L,L,R)
(L,L,R,R)
(L,R,L,R)
(L,R,R,L)

There are <span class="math">{2k \choose k}[/spoiler] distinct ways to put k "R"s in this list and <span class="math">{k \choose k} = 1[/spoiler] to fill the remaining k "L"s in each of those arrangements, giving<span class="math">{2k \choose k}[/spoiler] total distinct paths.

[Anonymous No.6572094]

>>6572065
If you are interested in this problem i basically did what you did, except you can go diagonally too, and i also wasnt interested in just the corner of a square, i wanted them all
what i found is similar to pascals triangle, except instead of adding the two numbers above, you add three.
whats really got my nuts in a twist about this problem is that i dont know how to get a function of its rows and columns like the choose function does for pascals

[Anonymous No.6572099]

>>6572050
You forgot to write out the restriction that you have to move on a grid. you made me confus

[Anonymous No.6572100]

>>6572099
I figured it was implicit in the fact that it's all taxicab'd

[Anonymous No.6572112]

This thread is fuvking retarded and gay you fags dont know what the fuck youre talkig about. The op is talking about thr UNIQUE lattice paths in space. Unique up to rotation/reflection Op is talking about combinations. Pascals triangle arises when you take into account rotations/reflection ie permutations. Fuckinv saged fuck you dalton

[Anonymous No.6572115]

>>6572112
did you not see OPs pic you nigger
reflections are explicitly included, even color coded for your blind ass

[Anonymous No.6572140]

>>6572115
yeah you're right is the op thats retarded his drawing is wronv it should be 2 for r=1, 6 for r=2, 20 for r=3, etc

[Anonymous No.6572142]

>>6572140
OP here. What I said was <span class="math"> r [/spoiler]= horizontal distance. What <span class="math"> you ~think[/spoiler] I said or meant was that <span class="math"> r[/spoiler] = the distance between the two points.
Maybe instead of claiming everyone else is retarded you should work on your reading comprehension.
When everyone else but you gets it maybe it's not them it's you.

[Anonymous No.6572155]

>>6572142
he's saying your list in the op is wrong, you should probably read the post again.
for r = 2 the number of paths is 6, you forgot two
r = 3 gives 20, you missed 8, etc
pic related, probably the 2 you missed for r=2
youll notice that a similar pattern is missing for r=3

[Anonymous No.6572156]

>>6572142
>>6572142
>>6572142
lol you are a dumb fag and you jist proved it you fail to realize I do understand your definition its you who clearly doest read my previous post fag theres SIX with r=2 . Nice try but I'm smarter than you

[Anonymous No.6572168]

>>6572093
>>6572155
anyways
I think this is an interesting approach, and i think that it can be used to solve our problem

[Anonymous No.6572178]

>>6572168
Wo w this ops clearly a fucking retard. I'm going to sleep.

[Anonymous No.6572181]

>>6572178
dont be a cock sucker carlos that shit was me
think about that approach, srs
write out the paths and look for a pattern

[Anonymous No.6572193]

>>6572181
Nope sorry bro opeez definitely afaggot for not realizing he didnt find all the paths for 2 wow also im tired bye

[Anonymous No.6572194]

test

[Anonymous No.6572200]

The taxicab metric has nothing to do with this.
A metric just tells you the distance between two points.

[Anonymous No.6572838]

>>6572200
... With the taxicab metric on the space OP described there are more than one unique paths of the same distance.
OP is asking how many paths that would be

[Anonymous No.6572857]

It's an easy problem and solution is
>>6572093

[Anonymous No.6572863]

Infinitely many unless the number of points in euclidean space became countable suddenly. But yeah pascal's triangle.

[Anonymous No.6572880]

For people using combinations: you can simplify it to (2n)!/2(n!). For the project euler question you need to figure out something smarter or implement arbitrary size integers. Or perhaps yours is a programming language that already has such a type. The standard int type will overflow

[Anonymous No.6572888]

Check project euler challenge #15, it's the same thing.
Here's an insight:
In a nxn lattice, the number of paths is n choose n.
display the number of paths for each cell and you'll soon realize... you're writing out the pascal triangle

[Anonymous No.6572923]

>>6572838
Infinitely many.

[Anonymous No.6573210]

>>6572193
wait explain what the fuck

[Anonymous No.6573924]

Here's a way to think about it. The distance between the two points is 2r in this metric, so 2r moves from one point will be needed to get to the other. Of these 2r moves, r of them will have to be in the up-down direction, the other r in the left-right direction. Thus, there are 2r choose r paths.

[Anonymous No.6573927]

>>6573924
Building on this, you can find the number of paths between any two points in this metric. I'll leave the solution to you. Math isn't a spectator sport.