In the book Those Fascinating Numbers by Jean-Marie De Konick they find interesting (or `interesting') things to say about many numbers. I reviewed the book in a SIGACT News book review column here. The entry for 13 is odd: 13 is the third Horse Number. The nth Horse number is the number of ways n horses can finish a race. You might think: OH, that's just n!. AH- horses can tie. So it's the number of ways to order n objects allowing ties.
Is there a closed form for H(n)? We will come back to that later.
0) The Wikipedia Entry on horse races that ended in a dead heat is here. They list 78 dead heats (two horses tie for first place) and 10 triple dead heats (three horses tie for first place). For the horse numbers we care if (say) two horses tie for 4th place. In reality nobody cares about that.
1) I have found nowhere else where these numbers are called The Horse Numbers.
2) They are called the Ordered Bell Numbers. The Wikipedia entry here has some applications.
3) They are also called the Fubini Numbers according to the Ordered Bell Number Wikipedia page.
4) I had not thought about the Horse Numbers for a long time when they came up while I was making slides for the proof that (Q,<) is decidable (the slides are here).
5) There is an OEIS page for the Horse Numbers, though they are called the Ordered Bell Numbers and the Fubini Numbers. It is here. That page says H(n) is asymptotically \(\frac{1}{2}n!(\log_2(e))^{n+1}\) which is approx \(\frac{1}{2}n!(1.44)^{n+1}\).
6) There is a recurrence for the Horse Numbers:
H(0)=1
H(1)=1
H(2)=3
For all \(n\ge 3\) we split H(n) into what happens if i horses are tied for last place (choose i out of n) and if the rest are ordered H(n-i) ways. Hence
\( H(n) = \binom{n}{1}H(n-1) + \binom{n}{2}H(n-2) + \cdots + \binom{n}{n}H(0) \)
Using \(\binom{n}{i} = \binom{n}{n-i}\) we get
\( H(n) = \binom{n}{0}H(0) + \binom{n}{1}H(1) + \cdots + \binom{n}{n-1}H(n-1) \)
STUDENT: Is there a closed form for H(n)?
BILL: Yes. Its H(n).
STUDENT: That's not closed form.
BILL: Is there a closed form for the number of ways to choose i items out of n?
STUDENT: Yes, \(\binom{n}{i}\) or \( \frac{n!}{i!(n-i)!}\)
BILL: Does that let you compute it easily? No. The way you compute \(\binom{n}{i}\) is with a recurrence. The way you compute H(n) is with a recurrence. Just having a nice notation for something does not mean you have a closed form for it.
STUDENT: I disagree! We know what n! is!
BILL: Do not be seduced by the familiarity of the notation.
Good line of inquiry, what or who prompted your curiosity and exploration? It's certainly useful to link idea of closed form to efficiency of computation. Therefore knowing if there is a closed form in some formalized sense is meaningful.
ReplyDelete(Bill) (I thought I already posted this) The student asking if there was a closed Form made me consider What is closed form?
DeleteGood topic, but the question is probably ill-posed (or too context agnostic) and should be amended to `Under what notion or in what sense is it considered closed-form?' A well-formalized, algorithmically accessible, and accepted notion of `closed form' exists within the framework established by Bill Gosper and Doron Zeilberger. This provides more fruitful ground to constructively explore the question, along with other TCS related questions. For instance, in what sense or under what model of computation is a `closed-form' solution, if one exists in the Zeilberger/Gosper sense, more efficient.
DeleteAn equally essential must read is Don Knuth's April 1970s letter to John Riordan (Rockefeller) and May 1970s letter to Neil Sloane and c/o Ron Graham who were both at Bell Labs, about sequence A670 (Bill, your Horse Numbers. Knuth stumbled upon them in connection to computer sorting). Knuth euphorically remarks to Neil Sloane, his first success using a predecessor of OEIS. (Incidentally, this validates that the best startup ideas usually always come in form of pet projects. Bell Labs must have been one of these three good places!)
"Does that let you compute it easily? No."
ReplyDeleteI disagree, it is more computationally efficient, not just notation. Write out the number of steps a computer takes!
(Bill) Are you saying that computing n!/(n/2)!(n/2)! is more efficien then the recurrence (n choose k) = (n-1 choose k-1) + (n-1 choose k)? One issue with computing n!/... is that there will be HUGE intermediary numbers which are a problem.
ReplyDeleteehh? when computing n!(n/2)!(n/2)! many terms cancel out, resulting in fewer overall operations to computing both n! and (n/2)!
ReplyDeletewhat happens when n is large and k is close to n/2 computing n!/...... is more efficient, no?
writing a program to carefully look at n! and cancel it with terms in the denom sounds like it would be tricky. You would store n! as the tuple (1,2,3,...,n) and then look at the tuples in the num and denom and cancel. Seems complicated. More efficient then the recurrence? I didn't think so but I now see it as an interesting question. (OH- this is Bill)
Deletecomrades, what am i missing?
Deletethe complexity of calculation factorials is known O(log log n M (n log n)), where M(n) is the complexity of multiplying two n-digit numbers but time complexity of recurrence (n choose k) is in O(2^n)ish?
(Bill) AH- when I said `recurrence' I meant `dynamic program' which will compute the first n rows of Pascal's Triangle, each entry requiring one addition. For (n choose k) for any k this takes O(n^2) time. I don't know the current bounds on M(n log n) so I don't know if your technique is better than using Dyn prog or not.
Deleteeven if we consider dynamic program running in O(n^2) time, would O(sqrt(n)*log log(n)) not be substantially better?
DeleteBut here is an older result still running better.
"On the complexity of calculating factorials" by Peter Borwein Volume 6, Issue 3, September 1985. Time complexity O(n(log(n)*log*log(n))^2). What's the take now?
(Bill) My take is that I am enlightened and I thank you for that!
DeleteIt would be helpful to know who or what instigated this topic. H(n) is not strictly closed form, but you make 0 efforts in motivating what you mean by closed form. Finally, computing n!/.... instead of recursion could be more efficient for specific values, due to cancellations.
ReplyDeleteI would rather say closed from is not an absolute concept, it is relative to language you choose.
ReplyDeleteIs it essentially asking if some function can be represented as a term in a language.
The recurrence is off by one, I think. h(0) = 1, h(1) = 1, h(2) = 3,…
ReplyDelete(Bill) Thanks, fixed.
ReplyDeletePersonally I would say the student is first right (H(n) is not closed form) and then wrong, as n! is not a closed form expression.
ReplyDeleteFrom https://en.wikipedia.org/wiki/Closed-form_expression :
In mathematics, an expression is in closed form if it is formed with constants, variables and a finite set of basic functions connected by arithmetic operations (+, −, ×, /, and integer powers) and function composition. Commonly, the allowed functions are nth root, exponential function, logarithm, and trigonometric functions.
It does not specify the factorial.
lol. let's not rely on wikipedia about math specifics. just imagine had they included factorial!
DeleteTo me closed form is a computational concept, a value that can be computed without loops or recursion, for example the nth Fibonacci number is \(\frac{\phi^n - \psi^n}{\sqrt{5}}\) where \(\phi = \frac{1 + \sqrt{5}}{2}\) and \(\psi = \frac{1 - \sqrt{5}}{2}\)
ReplyDeleteWhat you can compute without loop in language depends on your programming language, exponentiation is often implemented in programming languages with a loop. Ask a numerical analysis person about all that problems that once needs to deal with when computing exp.
DeleteOften people in math take elementary functions as the definition of closed form.
https://en.wikipedia.org/wiki/Elementary_function
Unless you do logic of course.
@Lance, this resonates with the margin definition in Concrete Mathematics [GKP] on page 7.
Delete@Bill, [GKP] also answers the relevant point about `n!' "The product of the first n integers, n!, has proved to be so important that we now consider it a basic operation. The formula `n!' is therefore in closed form." It also mentions that the recursive
formulation 1 . 2 . \dots . n is NOT a closed form. (citing Knuth!)
When in doubt, consult with the latest version/edition of [GKP] about what is accepted.
https://en.wikipedia.org/wiki/Closed-form_expression
ReplyDeleteI'm guessing the phrase "closed form" may have evolved as a way of saying "easy to compute", before the notion of "program" was as formalized?
ReplyDeleteAlso, although the "Horse Numbers" are defined by equations, it looks like at any point, only one case applies. So you could imagine writing it in Haskell or OCaml, with a "case" or "match" statement.
It might not be very efficient, though. Back in the day, a gratuitously-inefficient definition of n! ("nfib") was a toy benchmark for parallel Haskell implementations...
computational complexity is not the only valid perspective. one can be interested on other aspects, e.g. functions that are well behaved in some manner, particularly in mathematical analysis; concepts from a set of well studied functions as in statistics (Gamma function is a core concept), etc.
Delete