login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A320460 Alphabetic length of a divide-and-conquer approach to the regular expression for permutations of n symbols. 1
1, 4, 15, 48, 190, 600, 2205, 6720, 29988, 95760, 364980, 1108800, 4813380, 15135120, 57432375, 172972800, 892371480, 2916033120, 11616348744, 35384469120, 162510369840, 514937142720, 1992665514840, 5996736345600, 30797112654000, 100124080056000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

It is easy to prove that a(n) <= 4^n.

LINKS

Michael De Vlieger, Table of n, a(n) for n = 1..1673

Antonio Molina Lovett, Jeffrey Shallit, Optimal Regular Expressions for Permutations, arXiv:1812.06347 [cs.FL], 2018.

FORMULA

a(n) = binomial(n, floor(n/2))*(a(floor(n/2)) + a(ceiling(n/2))), a(1) = 1.

MATHEMATICA

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

CROSSREFS

Sequence in context: A225976 A093967 A052201 * A178704 A099167 A056337

Adjacent sequences:  A320457 A320458 A320459 * A320461 A320462 A320463

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, Oct 13 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 20 01:04 EDT 2022. Contains 353847 sequences. (Running on oeis4.)