1

Are there any systematic approaches developed on how to derive some "succinct" combinatorial formulas e.g. using factorials/hypergeometric terms and polynomials with integer coefficients that fit the first few terms of a given integer counting sequence? Perhaps a database of known sequences and formulas is also provided, so e.g. it could be detected if a sequence seems to be double or the square of another sequence with a known formula. It seems like it would be very useful if a mathematician could get some automatically generated proposals for a counting formula, and see if any of them "make sense" as relates to the counting problem so the formula can then be proved.

user2566092
  • 26,142
  • 7
    Like https://oeis.org/ ? – Amzoti Sep 05 '14 at 19:48
  • OEIS is a database but as far as I know, it doesn't detect whether a given sequence is a simple transform of another sequence. So sure, we can assume OEIS is provided but I'm asking more for algorithmic techniques to derive proposed "succinct" formulas given a sequence and given some known formulas, e.g. factorials and OEIS formulas. – user2566092 Sep 05 '14 at 19:49
  • @user2566092: Some CAS program (like Mathematica) have some functionality like that, but I doubt it is as thorough as you are looking for. – Amzoti Sep 05 '14 at 19:50
  • 3
    OEIS does have a feature called "superseeker" that can potentially detect if a sequence is a transform of a sequence already in the database. (See https://oeis.org/superhelp.txt for a list of transforms applied.) May not be exactly what you're looking for but it's good to know about at least. – Eric M. Schmidt Sep 05 '14 at 19:58
  • You can check if it appears to obey a linear recurrence relation. See this question, for example. – Jair Taylor Sep 06 '14 at 00:17

1 Answers1

0

Yes. The term used is "guessing".

Given $n$ points you can fit a polynomial of degree $n-1$ through them. If that polynomial turns out to have degree much less than $n-1$ then you have a plausible guess for a formula for the sequence.

The same idea can be generalised to other types of function. The old well-known names in the field are RATE (by Christian Krattenthaler, for Mathematica) and gfun (by Bruno Salvy and Paul Zimmermann, for Maple). There are many more recent packages; see, for example, the references in The Holonomic Toolkit, Manuel Kauers, Computer Algebra in Quantum Field Theory, Springer, 2013, pp.119-144.

Peter Taylor
  • 13,425