ℝolliℵg M∀th Thr∑a∂

can you explain

Sketch:

Let f(n) be the number of such paths for a given n.

For any n/2, always have solution +1 -1 + 1 -1 +1 -1 ....

One can also group the +1 -1s into pairs. In fact for any even k < n/2 one can choose choose a subset of k of the pairs and regroup into pairs of +1s and -1s and rearrange these groups so as to be solutions for k for the same problem ( you can divide by 2 or restate problem slightly ) This gives n/2 C k f(k) solutions.

General recursive formula is then
f(n) = n/2 C 0 * f(0) + n/2 C 2 * f(0) + ...

(continued in the next post)

Sorry, typo
f(n) = n/2 C 0 * f(0) + n/2 C 2 * f(2) + 2/2 C 4 * f(4)...

(continued in next post)

Examples

For n = 0 we say f(0) =1 (have to think about this)

For n =2 we have one path, namely +1 -1

For n= 4 we have +1 -1 + 1 - 1 or performing the "double up operation" +1 +1 -1 -1 so two paths.

Checking, f(4) ?= 2 C 0 * 1 + 2 C 2 * 1 = 2 check

(continuing)

f(6) = 3 C 0 * f(0) + 3 C 2 * f(2) = 1 + 3 *1 =4
f(8) = 4 C 0 * f(0) + 4 C 2 * f(2) + 4 C 4 * f(4) = 1 + 6 + 2 = 9

(cont..)

So was looking like powers of two until that last one. Now we observe that

m C 0 + m C 2 + m C 4 + ... = 2 ^(m-1)

which gives the leading term of my answer.

Why is the above identity true? Way I just saw it was to take

(1+1)^m + (1-1)^m = 2^m, see that alternating terms of the expansion cancel, and divide.

This is where I ran out gas for now.

Sorry, typo
f(n) = n/2 C 0 * f(0) + n/2 C 2 * f(2) + 2/2 C 4 * f(4)...

Typo^2 This should have been:
f(n) = n/2 C 0 * f(0) + n/2 C 2 * f(2) + 2/2 C 4 * f(4)...

At this point I don't know if I should keep studying/manipulating this formula until I get a simpler formula, or see if I made an error in deriving it, or try a different approach altogether.

Think I did indeed make an error and overlooked some cases and undercounted. Will ponder a while longer.

Still tinkering can't quite get the precise adjustment to my lower bound. Sorry to break thread.

Okay, now think the recursion formula is
f(n) = 2 f(n-2) + f (n-4) , n even

Aargh, still missing a few

Re-reading the circle question, I think I misunderstood it. The arbitrary point (a, b) must be given, otherwise it's too easy. I should have been suspicious that I made some headway on it so quickly.

Gave up and looked up this morning. Interesting. Hopefully can read more carefully tonight.

this thread is hard to find

anyway, first bunch of results for the 'mustn't go below zero, must end at zero' question
// 2 = 1
// 4 = 2
// 6 = 5
// 8 = 14
// 10 = 42
// 12 = 132
// 14 = 429
// 16 = 1430
// 18 = 4862

it's like a map

     /\
    /\/\
   /\/\/\
  /\/\/\/\
 /\/\/\/\/\
A   -t->   B

how many routes from A to B without backtracking?

f(n+1) = f(n) * (2 + (2(n - 1) / (n + 2))

which probably resolves down a lot

(oh, i've numbered those 1 - n where they should be 2 - 2n as only the even numbers work)

and f(1) = 1

scale factors between values are
2 + (0 / 3)
2 + (2 / 4)
2 + (4 / 5)
2 + (6 / 6)
2 + (8 / 7)
2 + (10 / 8)
2 + (12 / 9)
2 + (14 / 10)
etc

this thread is hard to find

Searching for "thr" in thread titles works well. Not necessarily so easy to remember, though.

Glad someone is taking a more methodical approach than my inept scribbling. Must have heard this topic mentioned in passing decades ago but obviously I never studied it. Lots of stuff about it on the web, can post link to one nice write-up later if you want.

this thread is hard to find

i just search for "gromov" now

This morning I was thinking about the simplified version of 2b where the sequence can't go negative but it doesn't have to end on zero, and I had the brainwave that the solution could be written as a recursive function, starting from n=1, and then defining f(n) in terms of f(n-1), since the path dependence means that at the solution at any value of n must build on the solutions at smaller values of n. However, I didn't get much beyond that. Nice to see koogs take it further. I really like the little map drawing.

Indeed.

One can see that there has to be a lot of structure there but it is hard to know exactly what it is, or even to enumerate the first few values correctly unless one is very careful or writes a little program to generate them, which I presume is what koogs did. Anyway impressed that he forged so far ahead on his own.

Oops, I was stumbling around related concepts on Wikipedia, starting from Fibonacci numbers and I stumbled on the answer. There is a name for the sequence of numbers that Koog started enumerating above, which apparently solve lots of combinatorics problems, including this one. Now I'm torn on whether I should read the proof, or keep thinking about it.

> writes a little program to generate them, which I presume is what koogs did

busted...

was a tiny recursive loop to generate all the possibilities and another method to validate them afterwards. inefficient but was surprisingly quick but i've since (read: in bed this morning) thought of a way of discarding invalid choices whilst creating them, thus cutting down a lot of the work. (although my first attempt got into an infinite loop and i had to kill it, having forgotten to save before running it)...

then it was just a case of trying to spot a pattern in the results. started by dividing the one by the previous, got lucky.

would like to see the proper answer - it feels so far like those calculus lessons where they get you to derive everything from first principles and then point out that it was just n * a^(n - 1) all along

I would definitely read up on it. Isn't this how the learning process is supposed to work: you try to do it yourself first, you do some calculations, you look for some relationships, patterns and connections, you beat your head against the wall and then, unless you are very very smart, diligent and lucky, you throw in the towel and look at the literature. Then it makes much more sense: I knew there was a relation something like that, I knew I needed an extra gimmick I couldn't come up with in the time allotted

Aka Dyck paths to watch out for

flopson to thread, to comment on our progress and assign new problems

flopson has given up on us

is a single step along a Dyck Path called a Dyck Move?

Dunno.

Two things I was able to observe during my initial fumblings:

1) The number of paths that are strictly positive until they return to zero at 2n is the same as the number of paths that are nonnegative that return to zero at 2n-2.

2) The recurrence formula seems to depend on more than a handful of prior terms. As we now know, it depends on all of them.

Should have been able to use 1) to derive the recurrence relationship if I had thought about it long enough. I think somebody posted a similar sentiment a few posts ago.

Been resisting the temptation to say:
flopson has gone off the net because of koogs

Do not peek if you are still calculating: http://www.math.ucla.edu/~pak/lectures/Cat/pakcat.htm

sorry i've been slacking on serving up with the answer, i'm trying to get a detail right and the friend who told me these riddles isn't responding. be back very soon with a fully satisfying proof

I liked this particular write-up: http://www.math.ku.edu/~jmartin/courses/math724-F13/count-dyck.pdf

oh hah! once you see the pun it all follows (well, 2b does). here is something that i think is not too terrible a hint. write "i get a dollar" as "(" (open paren) and "i give a dollar" as ")" (closed paren). now consider what "allowable" sequences look like syntactically in such a translation :-)

my dad is asking for a good introductory group theory text. nothing too dry.

he is working on this, but i think he finds it dry:

http://www.amazon.com/gp/product/0521312493/

any suggestions?

he specifically asked for group theory, so my sense is maybe some of the stuff in that book is over his head and he wants something a little more basic?

Kind of an interesting article about the Navier-Stokes equations, which tormented me in my days as a Mechanical Engineering student:

https://www.quantamagazine.org/20150721-famous-fluid-equations-are-incomplete/

still looking for a group theory book

Try Springer undergrad book by Armstrong.

(Xp)Interesting. Will read later hopefully

Μ. Α. Armstrong, Groups and Symmetry. His topology book seems to be pretty good as well.

^that's probably a good rec. i read his topo book, very fun. iirc there's a good chapter in coxeter's geometry textbook. group theory can't be learned without reference to geometry/symmetry imo. i learnt groups from a number theorist, took years to undo the damage

Lol. Yes, he does the basic symmetry ideas early on and then leads to stuff like orbits and stabilizers in the second half.

Book we used in college was Jacobsen, probably a little too abstract for most tastes. Teacher was awesome though, Jonathan Rogawski (RIP), who was a student of Langlands himself.

Just glanced at Armstrong again. Really touches on a lot of good, interesting stuff in a nice way, such as the kind of group theory and linear algebra that physicists use, or the free group- as seen in topology! - as opposed to a Hard Algebra approach, say, in which you might spend a lot more time on rings and monoids. His topology book comes highly recommended in The Princeton Companion by this guy: http://www.math.ucla.edu/~totaro/

thx for the recommend ... just grabbed the .djvu of "groups and symmetry" and also his (?) "basic topology" too

http://web.math.princeton.edu/generals/examiner.html

princeton oral math exams

some nice questions in there

If f_n is a seqeunce of integrable functions, when is int(f_n)
convergent? Can you give an example where this fails?

Set a(n) = 1/n + ... + 1/2n. Compute lim a(n) as n --> infinity.

Let En be a sequence of measurable sets in [0,1] with m(En) --> 1. Does
there exist a subsequence whose intersections all have measure > 1/2?