Yi came to visit UCSB today. As usual, Ryavec gave Yi all his usual favorite unsolved problems, namely his (3n+j choose n) Hankel determinant problems and Danzer’s Conjecture. For some reason, Ryavec thinks that I am good at doing arithmetic, and he kept asking me to compute binomial coefficients for him. They also discussed some combinatorial problems that I hadn’t seen before. This caused me to think of a generalization of catalan numbers: How many ways are there to get from (0,0) to (n,n) on a grid by taking right steps and up steps that cross the line y=x no more than j times (or exactly j times, for that matter)?

Another thought crossed my mind at another time during the discussion. Ryavec asked about the prime factors of a+b if we know the prime factors of a and b. Naturally, that’s a very tough (and unsolved) problem. But he wrote something like n=2^4*3^4*11^6+5^3*7^8*13^2 on the board, and it occurred to me that this number has a much greater chance of being prime than a random number that’s close to that size (i.e. 1/log(n)) since it isn’t divisible by 2, 3, 5, 7, 11, or 13.

I think I’ll do my measure theory research project on Haar measure of abelian groups. It looks interesting.

The current piece on the radio (not my current music) is a terrible insult to Vivaldi. People should really leave great works alone.

### Like this:

Like Loading...

*Related*

## About Simon

Hi. I'm Simon Rubinstein-Salzedo. I'm a mathematics postdoc at Dartmouth College. I'm also a musician; I play piano and cello, and I also sometimes compose music and study musicology. I also like to play chess and write calligraphy. This blog is a catalogue of some of my thoughts. I write them down so that I understand them better. But sometimes other people find them interesting as well, so I happily share them with my small corner of the world.

That thing about the primes is definitely interesting, or rather would be, except that n is divisble by 2, 3, and 5. (and 31 and 648719, and yes, I used a TI89) I was excited by that for a minute, though.

How is it divisible by 2, 3, and 5 if it’s the sum of, for example, a number divisible by 5 and a number not divisible by 5?

By the way, my calculator seems to think that that number is prime.

Whoops, it seems that I entered +13^2 into the calculator instead of *13^2

How many ways are there to get from (0,0) to (n,n) on a grid by taking right steps and up steps that cross the line y=x no more than j times (or exactly j times, for that matter)?I think the generating function for the second question should be (C(x)-1)^(j+1) for j > 1 where C(x) is the gf for the Catalan #’s. Then of course you could get a gf for the first problem by taking the sum of a geometric series. Though actually that first gf could be simplified with the identity xC(x)^2 = C(x) + 1 to give a formula for the second problem as a sum of Catalan numbers. Of course that’s only useful for a fixed j, since I doubt the general form will come out nice. Hmmm…

Oopers. Should be “xC(x)^2 + 1 = C(x)”. Same principle, though.

Yes, I do not think that this problem has a closed form answer for general j; the two-variable generating function is simply too ugly… I played with it for a while and only got a few messy summation expressions. One slightly similar question that does have a very nice answer asks how many up-right paths there are from (0,0) to (n,n) with exactly j vertical unit segments (up steps) below the line y=x. Perhaps this is a more natural question to ask?