OFFSET
1,3
COMMENTS
A 1-dimensional fountain given by a permutation is a 1 X n grid of squares with a source on the left and a sink on the right, where the permutation gives the height of each square of the fountain. Starting from the source, the water fills up each square of the fountain at the rate of one unit volume per unit time. The water immediately flows to all adjacent regions of lower height. The water flows out immediately upon reaching the sink.
The expected amount of time to fill a fountain given by a random permutation in S_n is a(n)/n!.
a(n) <= (n!-1)*binomial(n,2).
LINKS
Peter Kagey, Table of n, a(n) for n = 1..400
Chalkdust Magazine, Well, well, well.... (Construction is slightly different.)
FORMULA
a(n) = n!*Sum_{k=0..n} (n-k)*k/(k+1).
E.g.f.: (x + (1-x)*log(1-x))/(1-x)^3. - G. C. Greubel, Dec 04 2018
a(n) = (n+1)!(n+2-2H(n+1))/2, where H(n) = 1+1/2+...+1/n is the n-th Harmonic number. - Jeffrey Shallit, Dec 31 2018
EXAMPLE
For the permutation 15234, the well takes a total of seven seconds to reach the sink: it takes 4 seconds to fill to 55234, then it takes 1 second to fill to 55334, then it takes 2 seconds to fill to 55444, where it reaches the sink.
For n = 3 the a(3) = 10 sum occurs from summing over the times in the following table:
+-------------+------+-------------+
| permutation | time | final state |
+-------------+------+-------------+
| 123 | 3 | 333 |
| 132 | 2 | 332 |
| 213 | 3 | 333 |
| 231 | 1 | 331 |
| 312 | 1 | 322 |
| 321 | 0 | 321 |
+-------------+------+-------------+
MAPLE
a:=n->factorial(n)*add((n-k)*k/(k+1), k=0..n): seq(a(n), n=1..22); # Muniru A Asiru, Dec 05 2018
MATHEMATICA
Table[n!*Sum[(n - k)*k/(k + 1), {k, 1, n - 1}], {n, 1, 21}]
PROG
(PARI) vector(25, n, n!*sum(k=0, n, (n-k)*k/(k+1))) \\ G. C. Greubel, Dec 04 2018
(Magma) [Factorial(n)*(&+[(n-k)*k/(k+1): k in [1..n]]): for n in [1..25]]; // G. C. Greubel, Dec 04 2018
(Sage) [factorial(n)*sum((n-k)*k/(k+1) for k in (1..n)) for n in (1..25)] # G. C. Greubel, Dec 04 2018
(GAP) List([1..22], n->Factorial(n)*Sum([0..n], k->(n-k)*k/(k+1))); # Muniru A Asiru, Dec 05 2018
(Python)
from sympy.abc import k, a, b
from sympy import factorial
from sympy import Sum
for n in range(1, 25): print(int(factorial(n)*Sum((n-k)*k/(k+1), (k, 0, n)).doit().evalf()), end=', ') # Stefano Spezia, Dec 05 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Kagey, Nov 19 2018
STATUS
approved