A straightforward combinatorial argument leads to the conjectural identity (in Mma-speak) Binomial[2 n-k, n-1] (n-k+1) - n Sum[Binomial[2 i-k, i-1] Binomial[2 n-2 i, n-i] / (n-i+1), {i, k-1, n-1}] = 0 for natural n, k . Now both Mathematica and Maple insist on converting the LHS to HypergeometricPFQ [ {(k-1)/2, k/2, k - n - 2}, {k - 1, k - n - 1/2}, 1 ] - (1 - k/2)/2 Binomial[2 n - k + 1, k] / Binomial[n, k] which does also appear to vanish, at any rate for integer 2 <= k <= n+1 (despite the combinatorics requiring 0 <= k <= n+1 .) Is there some obvious reason why the latter expression should vanish? It seems there might be denominator Gamma[c-n] lurking, which would settle the issue ... Fred Lunnon On 5/30/13, Fred lunnon <fred.lunnon@gmail.com> wrote:
Now why did I want to generate n-bracketings in the first place ... or what amounts to the same thing, ordered rooted trees (ORTs) with n+1 nodes?
[Here each node corresponds to a matching pair of brackets, and its children to the pairs immediately within the parent pair. An ORT will be equipped with an extra half-edge ("bole"?) leading into the root node, which corresponds to a virtual outer pair of brackets imagined enclosing any given bracketing.]
How many k-valent nodes occur among the set of all distinct (n+1)-ORTs? After spending all that time generating the damn' things, the answer is an anticlimax: apparently it's just (2n-k)_C_(n-1) the dear old binomial coefficient!
Is this well-known? Can anyone suggest a proof?
If so, should OEIS A007318 be amended to incorporate: " n_C_k = number of (2k+2-n)-valent nodes occurring among distinct ordered rooted trees with k+2 nodes, provided each root node is equipped with an extra inward half-edge " ?
Example: n = 3 bracketing valency 1,...,4 ( ((())) ) [1, 3, 0, 0] ( (()()) ) [2, 1, 1, 0] ( ()(()) ) [2, 1, 1, 0] ( (())() ) [2, 1, 1, 0] ( ()()() ) [3, 0, 0, 1] totals [10, 6, 3, 1]
Fred Lunnon