most recent 30 from http://mathoverflow.net 2013-05-23T21:26:31Z http://mathoverflow.net/feeds/question/44517 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44517/how-to-restore-the-original-formula-from-a-binomial-like-expansion Anixx 2010-11-02T04:45:17Z 2010-11-02T13:26:33Z

<p>I encountered with a recursive formula of the following kind:</p> <p>$$A(0,x)=1$$</p> <p>$$A(n,x)= \sum _{j=0}^{n-1} \binom{n-1}{j} A(n-j-1,x) \sum _{k=0}^{x-1} A(j,k)$$</p> <p>The sum terms can be re-arranged so to get the following expression under the external sum:</p> <p>$$\sum _{j=0}^{n-1}\binom{n-1}{j} A(n-j-1,x)A(j,k)$$</p> <p>Which seems to be perfectly similar to the formula for a power of a binomial or for a derivative of a product with an exception that A(n,x) is neither power nor derivative. </p> <p>But one can suppose that this is in fact an expansion of a form</p> <p>$$A(n-1,x*k)$$</p> <p>where * is some binary operation and A plays the role of power.</p> <p>So my question is whether it possible to recover this expression from the binomial-like expansion and if it possible please give me some hints on a research or summary about common name and properties of binomial-like expansions, which properties should have two operations so that their combination gives binomial-like formula etc.</p> <p>An approach to find a general formula for A(n,x) using generating functions apparently leads to nothing useful.</p>

http://mathoverflow.net/questions/44517/how-to-restore-the-original-formula-from-a-binomial-like-expansion/44553#44553 JBL 2010-11-02T13:26:33Z 2010-11-02T13:26:33Z

<p>This is not exactly an answer, but it's too long for a comment and also probably contains all the information you need. From the form of the recursion, it looks like an enumeration of trees, set partitions, or something similar. It's easy to compute the first few rows of the array, and indeed, throwing the first few terms into the <a href="http://www.research.att.com/~njas/sequences/" rel="nofollow">OEIS</a> comes up with four compelling-looking hits: </p> <p><a href="http://www.research.att.com/~njas/sequences/A111672" rel="nofollow">http://www.research.att.com/~njas/sequences/A111672</a></p> <p><a href="http://www.research.att.com/~njas/sequences/A144150" rel="nofollow">http://www.research.att.com/~njas/sequences/A144150</a></p> <p><a href="http://www.research.att.com/~njas/sequences/A153277" rel="nofollow">http://www.research.att.com/~njas/sequences/A153277</a></p> <p>(These appear to actually be three copies of essentially the same array that differ only in the number of 1s included at the boundary; there may also be other instances if one reads the array in a different order.) And I think that it should not be difficult to show that your numbers do indeed correspond to the numbers in any one of these tables.</p>