%I #12 Feb 07 2019 19:32:06
%S 1,4,15,48,190,600,2205,6720,29988,95760,364980,1108800,4813380,
%T 15135120,57432375,172972800,892371480,2916033120,11616348744,
%U 35384469120,162510369840,514937142720,1992665514840,5996736345600,30797112654000,100124080056000
%N Alphabetic length of a divide-and-conquer approach to the regular expression for permutations of n symbols.
%C Consider generating a regular expression for the permutations of a set S. We can do this by divide-and-conquer: sum over all subsets T of S of size floor(n/2), and for each subset, concatenate the (recursive) result for T to the result for S-T. For example, for S = {1,2,3,4} one gets (12+21)(34+43)+(13+31)(24+42)+(23+32)(14+41)+(14+41)(23+32)+(24+42)(13+31)+(34+43)(12+21). The length of such an expression (where one counts only elements of S) is a(n).
%C It is easy to prove that a(n) <= 4^n.
%H Michael De Vlieger, <a href="/A320460/b320460.txt">Table of n, a(n) for n = 1..1673</a>
%H Antonio Molina Lovett, Jeffrey Shallit, <a href="https://arxiv.org/abs/1812.06347">Optimal Regular Expressions for Permutations</a>, arXiv:1812.06347 [cs.FL], 2018.
%F a(n) = binomial(n, floor(n/2))*(a(floor(n/2)) + a(ceiling(n/2))), a(1) = 1.
%t Nest[Append[#1, Binomial[#2, Floor[#2/2]] (#1[[Floor[#2/2] ]] + #1[[Ceiling[#2/2]]] )] & @@ {#, Length@ # + 1} &, {1}, 25] (* _Michael De Vlieger_, Feb 07 2019 *)
%K nonn
%O 1,2
%A _Jeffrey Shallit_, Oct 13 2018