cp's OEIS Frontend

A321853 a(n) is the sum of the fill times of all 1-dimensional fountains given by the permutations in S_n.

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