|
| |
|
|
A321853
|
|
a(n) is the sum of the fill times of all 1-dimensional fountains given by the permutations in S_n.
|
|
2
|
|
|
|
0, 1, 10, 86, 756, 7092, 71856, 787824, 9329760, 118956960, 1627067520, 23786386560, 370371536640, 6122231942400, 107109431654400, 1977781262284800, 38445562145894400, 784885857270681600, 16792523049093120000, 375755553108633600000, 8777531590107033600000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
