# How to restore the original formula from a binomial-like expansion?

I encountered with a recursive formula of the following kind:

$$A(0,x)=1$$

$$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)$$

The sum terms can be re-arranged so to get the following expression under the external sum:

$$\sum _{j=0}^{n-1}\binom{n-1}{j} A(n-j-1,x)A(j,k)$$

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.

But one can suppose that this is in fact an expansion of a form

$$A(n-1,x*k)$$

where $*$ is some binary operation and $A$ plays the role of power.

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.

An approach to find a general formula for $A(n,x)$ using generating functions apparently leads to nothing useful.

• What does your question have to do with abstract algebra? – Ryan Budney Nov 2 '10 at 6:23
• @Ryan Budney probably, this en.wikipedia.org/wiki/… I just wonder in what circumstances such expansions occur and how one can find the * operation from the given binomial expansion. If it does not relate to abstract algebra, the tag can be removed. – Anixx Nov 2 '10 at 6:36
• Have you looked at the exponential generating function of $A(j,k)$? – Robin Chapman Nov 2 '10 at 7:22
• @ Robin Chapman I asked this question some time ago on another mathematical forum asking to find a common form for A(n,x). One participant of that forum suggested to use the generating function. But it turned out then that it does not lead to anything useful. – Anixx Nov 2 '10 at 7:43
• @Annix, that the generating function approach led nowhere would have been an informative point to have included in your original question posting, particularly if you had tried it and failed... – sleepless in beantown Nov 2 '10 at 7:49

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 OEIS comes up with four compelling-looking hits:

http://www.oeis.org/A111672

http://www.oeis.org/A144150

(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.

• Indeed. But there are some issues. - I need to compute it with x real - I wanted to have a smaller formula for such binomial expression. So the main question remains in force: is it possible to write binomial-like expression as $A(n−1,x∗k)$ where * is some function of two variables? – Anixx Nov 2 '10 at 21:52
• And it turned out that the A(a,b) are just Bell's numbers of b-th order. So now only the algebraic part of the question remains: how to reverse the binomial expansion in this case? – Anixx Nov 3 '10 at 0:05

The binomial formula holds for any pair of commuting elementa $u$ and $v$ in an associative algebra. So, for instance, if $A$ is some algebra of derivable functions and $D$ is the derivation, we can compose $n$ times the Leibniz rule (in $A\otimes A$):

$$(D\otimes 1 + 1 \otimes D) ^n = \sum_{p+q = n} {p \choose q} D^p \otimes D^q$$

Did you look at your recursive formula with such eyes?