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?
― koogs, Monday, 29 June 2015 20:43 (eight years ago) link
f(n+1) = f(n) * (2 + (2(n - 1) / (n + 2))
which probably resolves down a lot
― koogs, Monday, 29 June 2015 21:08 (eight years ago) link
(oh, i've numbered those 1 - n where they should be 2 - 2n as only the even numbers work)
― koogs, Monday, 29 June 2015 21:14 (eight years ago) link
and f(1) = 1
― koogs, Monday, 29 June 2015 21:15 (eight years ago) link
scale factors between values are2 + (0 / 3)2 + (2 / 4)2 + (4 / 5)2 + (6 / 6)2 + (8 / 7)2 + (10 / 8)2 + (12 / 9)2 + (14 / 10)etc
― koogs, Monday, 29 June 2015 21:20 (eight years ago) link
Searching for "thr" in thread titles works well. Not necessarily so easy to remember, though.
― anatol_merklich, Monday, 29 June 2015 21:54 (eight years ago) link
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.
― Help Me, Zond 4 (James Redd and the Blecchs), Tuesday, 30 June 2015 00:19 (eight years ago) link
i just search for "gromov" now
― the late great, Tuesday, 30 June 2015 00:26 (eight years ago) link
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.
― o. nate, Tuesday, 30 June 2015 02:00 (eight years ago) link
Indeed.
― Help Me, Zond 4 (James Redd and the Blecchs), Tuesday, 30 June 2015 02:07 (eight years ago) link
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.
― Help Me, Zond 4 (James Redd and the Blecchs), Tuesday, 30 June 2015 02:13 (eight years ago) link
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.
― o. nate, Tuesday, 30 June 2015 03:12 (eight years ago) link
> 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
― koogs, Tuesday, 30 June 2015 08:33 (eight years ago) link
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
― Help Me, Zond 4 (James Redd and the Blecchs), Tuesday, 30 June 2015 11:04 (eight years ago) link
Aka Dyck paths to watch out for
flopson to thread, to comment on our progress and assign new problems
― I Want My LLTV (James Redd and the Blecchs), Tuesday, 30 June 2015 23:11 (eight years ago) link
flopson has given up on us
― I Want My LLTV (James Redd and the Blecchs), Wednesday, 1 July 2015 09:11 (eight years ago) link
is a single step along a Dyck Path called a Dyck Move?
― koogs, Wednesday, 1 July 2015 10:04 (eight years ago) link
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.
― I Want My LLTV (James Redd and the Blecchs), Wednesday, 1 July 2015 10:37 (eight years ago) link
Been resisting the temptation to say:flopson has gone off the net because of koogs
― I Want My LLTV (James Redd and the Blecchs), Wednesday, 1 July 2015 10:45 (eight years ago) link
Do not peek if you are still calculating: http://www.math.ucla.edu/~pak/lectures/Cat/pakcat.htm
― How I Wrote Matchstick Men (James Redd and the Blecchs), Sunday, 5 July 2015 21:58 (eight years ago) link
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
― flopson, Sunday, 5 July 2015 22:52 (eight years ago) link
I liked this particular write-up: http://www.math.ku.edu/~jmartin/courses/math724-F13/count-dyck.pdf
― How I Wrote Matchstick Men (James Redd and the Blecchs), Sunday, 5 July 2015 23:12 (eight years ago) link
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 :-)
― got bent (mild cheezed off vibes) (s.clover), Sunday, 5 July 2015 23:42 (eight years ago) link
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?
― the late great, Monday, 13 July 2015 01:45 (eight years ago) link
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?
― the late great, Monday, 13 July 2015 01:48 (eight years ago) link
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/
― o. nate, Thursday, 23 July 2015 02:30 (eight years ago) link
still looking for a group theory book
― the late great, Thursday, 23 July 2015 02:40 (eight years ago) link
Try Springer undergrad book by Armstrong.
(Xp)Interesting. Will read later hopefully
― Archaic Buster Poindexter, Live At The Apollo (James Redd and the Blecchs), Thursday, 23 July 2015 02:44 (eight years ago) link
Μ. Α. Armstrong, Groups and Symmetry. His topology book seems to be pretty good as well.
― Archaic Buster Poindexter, Live At The Apollo (James Redd and the Blecchs), Thursday, 23 July 2015 03:04 (eight years ago) link
^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
― flopson, Thursday, 23 July 2015 03:44 (eight years ago) link
Lol. Yes, he does the basic symmetry ideas early on and then leads to stuff like orbits and stabilizers in the second half.
― Archaic Buster Poindexter, Live At The Apollo (James Redd and the Blecchs), Thursday, 23 July 2015 03:50 (eight years ago) link
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.
― Archaic Buster Poindexter, Live At The Apollo (James Redd and the Blecchs), Thursday, 23 July 2015 03:56 (eight years ago) link
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/
― Archaic Buster Poindexter, Live At The Apollo (James Redd and the Blecchs), Thursday, 23 July 2015 10:56 (eight years ago) link
thx for the recommend ... just grabbed the .djvu of "groups and symmetry" and also his (?) "basic topology" too
― the late great, Thursday, 23 July 2015 15:45 (eight years ago) link
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. Doesthere exist a subsequence whose intersections all have measure > 1/2?
― flopson, Saturday, 1 August 2015 23:24 (eight years ago) link
sorry for dropping the ball on those combo coin flipping problems. i wanted to write up a nice proof for 2a that everyone could understand but i'm too busy writing a dumbass masters thesis right now. anyways 2a uses reflection principle and for 2b you can find a bijection between unique maximums and multiple maximums by reflecting about the peak /\ in a clever way. the proof of 2b my friend showed me was actually an original one that he's getting published so i prob shouldn't write it here. but i'll link to it later
bonus (easy) analysis question with multiple answers:
find a sequence X_n in R such that lim_{n->infty} X_n - X_{n-1} = 0 but lim_{n->infty} X_n doesn't exist
― flopson, Saturday, 1 August 2015 23:31 (eight years ago) link
i think this is 'yes' but cannot prove it
― dead (Lamp), Tuesday, 11 August 2015 01:45 (eight years ago) link
after posting and thinking about those for 5 mins i realized none of those questions make sense, i think there's some missing info
like, En = [0,1] for all n is an answer to that one you mention Lamp. m(En) -> 1 and m(Ei int Ej) = 1 > 1/2 for all i, j (taking the sequence itself as subsequence)
― flopson, Tuesday, 11 August 2015 01:59 (eight years ago) link
either that or princeton oral exams are a scam
― flopson, Tuesday, 11 August 2015 02:00 (eight years ago) link
i need to revisit rudin someday, never got a good handle on measure they/real analysis and ended up doing actuary stuff so having that basis for probability would be valuable if only for exams
― art, Tuesday, 11 August 2015 02:06 (eight years ago) link
ilx poster eteaoe convinced me to take measure theory in this very thread. it's ok, a little too dry for me but i didn't pursue stochastic calculus or any of the fancy applications of it, so it mostly just looked like an overly fussy way of doing integration to me at the same. this is my favourite result from measure theory https://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma which states that
if the sum of probabilities of a random sequence of events is finite, the probability that infinitely many of them occur is zero
― flopson, Tuesday, 11 August 2015 02:20 (eight years ago) link
my advisor was super psyched to teach a real analysis class (he was an algebraic topology/knot theory guy) bc he said he felt like he really "got" the subject, but the course was still, as you say, pretty dry. your synopsis is about where i landed, but having gotten into stats since i feel like i shd take another stab.
― art, Tuesday, 11 August 2015 02:34 (eight years ago) link
like, En = [0,1] for all n is an answer to that one you mention Lamp.
I took it to mean "is it the case that, for EVERY sequence E_n....."
― Guayaquil (eephus!), Tuesday, 11 August 2015 06:06 (eight years ago) link
Once you reach M such that, for m > M, m(Em) > .75 then the maximum disjunction between Em1 and Em2 for m1,m2 > M is strictly less than .25 + .25 = .5 so their intersection has to have measure > 1/2
― Eternal Return To Earth (James Redd and the Blecchs), Tuesday, 11 August 2015 10:29 (eight years ago) link
So, any subsequence starting from that point
― Eternal Return To Earth (James Redd and the Blecchs), Tuesday, 11 August 2015 10:30 (eight years ago) link
starting from that point on
― Eternal Return To Earth (James Redd and the Blecchs), Tuesday, 11 August 2015 10:43 (eight years ago) link
ohhh got it
― flopson, Tuesday, 11 August 2015 14:53 (eight years ago) link
hmm ok and since it's cauchy you can always find such a point. might there not be some weird ass measurable sets that would contradict though?
― flopson, Tuesday, 11 August 2015 15:09 (eight years ago) link
Don't think you need to bring Cauchy into it, limit is already defined. But I think what is showed is only pairwise intersection, it is possible that out on the tail the intersection of all the sets might have measure < 1/2.
― Eternal Return To Earth (James Redd and the Blecchs), Tuesday, 11 August 2015 16:11 (eight years ago) link