A376269 a(n) = n! + (n - 1)! + (n - 2)! + n - 3.

3, 9, 33, 152, 867, 5884, 46085, 408246, 4032007, 43908488, 522547209, 6745939210, 93884313611, 1401079680012, 22317642547213, 377917892352014, 6778983923712015, 128403161542656016, 2560949482291200017, 53645489280294912018, 1177524571957493760019, 27027108408834293760020

Offset: 2

Author

Paolo Xausa, Sep 18 2024

Keywords

• nonn
• easy

Comments

a(n) is a lower bound for the length of every superpermutation on n symbols (see links). An upper bound for the length of a minimal superpermutation is given by A341300(n).

Links

• Paolo Xausa, Table of n, a(n) for n = 2..400
• Anonymous 4chan poster, Robin Houston, Jay Pantone, and Vince Vatter, A lower bound on the length of the shortest superpattern, 2018.
• Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
• James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
• Wikipedia, Superpermutation.

Crossrefs

Cf. A054119, A180632, A332089, A341300.

Programs

Mathematica

Table[n^2 * (n - 2)! + n - 3, {n, 2, 25}]

Python

from sympy import factorial
def A376269(n): return n**2*factorial(n-2)+n-3 # Chai Wah Wu, Sep 20 2024

Formula

a(n) = A054119(n) + n - 3.

E.g.f.: (3 - x - x^2 - exp(x)*(3 - 4*x + x^2) - (1 - x)*x*log(1 - x))/(1 - x). - Stefano Spezia, Sep 18 2024

a(n) = (n-2)!*n^2 + n - 3. - Chai Wah Wu, Sep 20 2024

D-finite with recurrence (-n+1)*a(n) +(n-2)*(n+2)*a(n-1) -(n-1)*(n-3)*a(n-2) -(4*n-7)*(n-4)=0. - R. J. Mathar, Sep 23 2024