3
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ What does your question have to do with abstract algebra? $\endgroup$
    – Ryan Budney
    Commented Nov 2, 2010 at 6:23
  • $\begingroup$ @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. $\endgroup$
    – Anixx
    Commented Nov 2, 2010 at 6:36
  • $\begingroup$ Have you looked at the exponential generating function of $A(j,k)$? $\endgroup$
    – Robin Chapman
    Commented Nov 2, 2010 at 7:22
  • $\begingroup$ @ 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. $\endgroup$
    – Anixx
    Commented Nov 2, 2010 at 7:43
  • 3
    $\begingroup$ @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... $\endgroup$
    – sleepless in beantown
    Commented Nov 2, 2010 at 7:49

2 Answers 2

Reset to default
2
$\begingroup$

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

http://www.oeis.org/A153277

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Anixx
    Commented Nov 2, 2010 at 21:52
  • $\begingroup$ 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? $\endgroup$
    – Anixx
    Commented Nov 3, 2010 at 0:05
2
$\begingroup$

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?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .