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

0, 1, 10, 86, 756, 7092, 71856, 787824, 9329760, 118956960, 1627067520, 23786386560, 370371536640, 6122231942400, 107109431654400, 1977781262284800, 38445562145894400, 784885857270681600, 16792523049093120000, 375755553108633600000, 8777531590107033600000

Offset: 1

Author

Peter Kagey, Nov 19 2018

Keywords

• nonn

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).

Examples

			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     |
+-------------+------+-------------+
		

Links

• Peter Kagey, Table of n, a(n) for n = 1..400
• Chalkdust Magazine, Well, well, well.... (Construction is slightly different.)

Crossrefs

Cf. A002538.

Programs

GAP

List([1..22],n->Factorial(n)*Sum([0..n],k->(n-k)*k/(k+1))); # Muniru A Asiru, Dec 05 2018

Magma

[Factorial(n)*(&+[(n-k)*k/(k+1): k in [1..n]]): n in [1..25]]; // G. C. Greubel, Dec 04 2018

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}]

PARI

vector(25, n, n!*sum(k=0,n, (n-k)*k/(k+1))) \\ G. C. Greubel, Dec 04 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

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

Formula

a(n) = n!*Sum_{k=0..n} (n-k)*k/(k+1).

a(n) = A001804(n) - A002538(n-1) for n > 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