Wikipedia:Reference desk/Archives/Mathematics/2015 May 22

Mathematics desk
< May 21	<< Apr | May | Jun >>	May 23 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 22

Generating function of the central binomial coefficients

The generating function for the central binomial coefficients is f(z) = (1-4z)^-1/2 which follows by expanding f using either the binomial theorem or Taylor's series. The OEIS page (OEIS: A000984) mentions that if the sequence is convolved with itself you get powers of 4. In terms of the generating functions this amounts to ((1-4z)^-1/2)² = (1-4z)^-1. The combinatorial interpretation of this is that the number of ordered pairs of strings a's and b's, having total length 2n, and with both strings having equal numbers of a's and b's, is equal to the number of strings of a's and b's having length 2n. For example, for n=2 this says

#{aabb|, abab|, abba|, baab|, baba|, bbaa|, ab|ab, ab|ba, ba|ab, ba|ba, |aabb, |abab, |abba, |baab, |baba, |bbaa}

=

#{aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb}.

Is there a combinatorial proof of this? In other words, is there a one-one correspondence between these two sets that works for all n? --RDBury (talk) 23:35, 22 May 2015 (UTC)

This is in Richard Stanley's Enumerative Combinatorics, Volume 1, first edition, exercise 1.2(c), where he gives it a difficulty rating 3-. In the solution, he remarks that your question was "raised by P. Veress and solved by G. Hajos in the 1930s. A recent proof appears in D. J. Kleitman, Studies in Applied Math 54 (1975), 289--292. See also M. Sved, Math. Intelligencer, vol 6 #4 (1984) 44--45." Possibly it is worth checking the second edition (free on Richard's website) to see if it says anything else. --JBL (talk) 17:25, 2 June 2015 (UTC)

Thanks. It makes sense that it a fairly old problem, but I didn't know how to look for it. It is in Stanley's 2nd ed., still a 3, so it's good it know it's regarded as somewhat difficult and not something obvious that I'm missing. I also found r the M. Sved paper on-line. It's posed there as a question in part I and answered in part II. --RDBury (talk) 00:44, 3 June 2015 (UTC)