The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #46 Sep 08 2022 08:46:23
%S 0,1,10,86,756,7092,71856,787824,9329760,118956960,1627067520,
%T 23786386560,370371536640,6122231942400,107109431654400,
%U 1977781262284800,38445562145894400,784885857270681600,16792523049093120000,375755553108633600000,8777531590107033600000
%N a(n) is the sum of the fill times of all 1-dimensional fountains given by the permutations in S_n.
%C 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.
%C The expected amount of time to fill a fountain given by a random permutation in S_n is a(n)/n!.
%C a(n) <= (n!-1)*binomial(n,2).
%H Peter Kagey, <a href="/A321853/b321853.txt">Table of n, a(n) for n = 1..400</a>
%H Chalkdust Magazine, <a href="http://chalkdustmagazine.com/blog/well-well-well/">Well, well, well...</a>. (Construction is slightly different.)
%F a(n) = n!*Sum_{k=0..n} (n-k)*k/(k+1).
%F a(n) = A001804(n) - A002538(n-1) for n > 1.
%F E.g.f.: (x + (1-x)*log(1-x))/(1-x)^3. - _G. C. Greubel_, Dec 04 2018
%F 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
%e 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.
%e For n = 3 the a(3) = 10 sum occurs from summing over the times in the following table:
%e +-------------+------+-------------+
%e | permutation | time | final state |
%e +-------------+------+-------------+
%e | 123 | 3 | 333 |
%e | 132 | 2 | 332 |
%e | 213 | 3 | 333 |
%e | 231 | 1 | 331 |
%e | 312 | 1 | 322 |
%e | 321 | 0 | 321 |
%e +-------------+------+-------------+
%p 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
%t Table[n!*Sum[(n - k)*k/(k + 1), {k, 1, n - 1}], {n, 1, 21}]
%o (PARI) vector(25, n, n!*sum(k=0,n, (n-k)*k/(k+1))) \\ _G. C. Greubel_, Dec 04 2018
%o (Magma) [Factorial(n)*(&+[(n-k)*k/(k+1): k in [1..n]]): for n in [1..25]]; // _G. C. Greubel_, Dec 04 2018
%o (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
%o (GAP) List([1..22],n->Factorial(n)*Sum([0..n],k->(n-k)*k/(k+1))); # _Muniru A Asiru_, Dec 05 2018
%o (Python)
%o from sympy.abc import k, a, b
%o from sympy import factorial
%o from sympy import Sum
%o 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
%Y Cf. A002538.
%K nonn
%O 1,3
%A _Peter Kagey_, Nov 19 2018