A376269 - OEIS

%I #44 Sep 27 2024 23:01:06

%S 3,9,33,152,867,5884,46085,408246,4032007,43908488,522547209,

%T 6745939210,93884313611,1401079680012,22317642547213,377917892352014,

%U 6778983923712015,128403161542656016,2560949482291200017,53645489280294912018,1177524571957493760019,27027108408834293760020

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

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

%H Paolo Xausa, <a href="/A376269/b376269.txt">Table of n, a(n) for n = 2..400</a>

%H Anonymous 4chan poster, Robin Houston, Jay Pantone, and Vince Vatter, <a href="/A180632/a180632.pdf">A lower bound on the length of the shortest superpattern</a>, 2018.

%H Michael Engen and Vincent Vatter, <a href="https://doi.org/10.1080/00029890.2021.1835384">Containing All Permutations</a>, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (<a href="https://doi.org/10.48550/arXiv.1810.08252">preprint version</a>).

%H James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=wJGE4aEWc28">Superpermutations</a>, Numberphile video, 2018.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Superpermutation">Superpermutation</a>.

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

%F 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

%F a(n) = (n-2)!*n^2 + n - 3. - _Chai Wah Wu_, Sep 20 2024

%F 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

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

%o (Python)

%o from sympy import factorial

%o def A376269(n): return n**2*factorial(n-2)+n-3 # _Chai Wah Wu_, Sep 20 2024

%Y Cf. A054119, A180632, A332089, A341300.

%K nonn,easy

%O 2,1

%A _Paolo Xausa_, Sep 18 2024