I would be very interested for examples of "natural" combinatorial functions for which it has been rigorously proven that there is no closed-from expression. By "natural", I mean, not a function which grows too fast to be a closed-form function, like Busy Beaver, but rather, something like "the number of associative operations on an $n$-element set" or "the number of binary operations which are groups on an $n$-element set" or "the number of transitive binary relations on an $n$-element set". Has anyone, in some paper or book or text, given a rigorous definition of closed-form expression, and proven rigorously that there is no closed-form expression for a given "natural" "combinatorial" function?
2026-04-02 20:55:34.1775163334
On
Examples of "natural" combinatorial functions for which it has been proven that there is no closed-form expression
67 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
Take the definition in Wikipedia: Closed-form expression.
It's not possible to prove that a closed-form solution doesn't exist, because you have to define which kind of expressions (functions, operations, symbols) you allow.
As mathematically well defined functions, you can get i. a. statements about the Elementary functions, the Liouvillian functions or some Special functions.
There are only few problems for which it has been proven that they don't have solutions in the Elementary functions, the Elementary numbers or the Liouvillian functions, e.g. Kepler's equation and Lambert W.
The proofs use Risch algorithm or Ritt-Risch structure theorem for Elementary functions.
The book A=B is all about finding closed forms or proving their nonexistence for a large class of combinatorial sums.