A090326 Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols.

1, 4, 15, 54, 185, 608, 1939, 6058, 18669, 57012, 173063, 523262, 1577953, 4750216, 14283387, 42915666, 128878037, 386896220, 1161212911, 3484687270, 10456158921, 31372671024, 94126401635, 282395982074, 847221500605, 2541731610628, 7625329049559

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

P. R. J. Asveld, Generating all permutations by context-free grammars in Chomsky normal form, Theoretical Computer Science 354 (2006) 118-130.

Index entries for linear recurrences with constant coefficients, signature (7,-17,17,-6).

Formula

a(n) = 3^n - 2^(n+1) + n + 1.

G.f.: x*(4*x^2-3*x+1) / ((x-1)^2*(2*x-1)*(3*x-1)). - Colin Barker, Jan 15 2015

E.g.f.: exp(x)*(1 - 2*exp(x) + exp(2*x) + x). - Stefano Spezia, Apr 25 2023

Example

S -> AD | DA | BE | EB | CF | FC, D -> BC | CB, E -> AC | CA, F -> AB | BA, A -> a, B -> b, C -> c; so a(3)=15.

Mathematica

f[n_] := 3^n - 2^(n + 1) + n + 1; Table[ f[n], {n, 1, 26}] (* Robert G. Wilson v, Jan 30 2004 *)

Prog

(PARI) Vec(x*(4*x^2-3*x+1)/((x-1)^2*(2*x-1)*(3*x-1)) + O(x^100)) \\ Colin Barker, Jan 15 2015

Crossrefs

Sequence in context: A289927 A164619 A227382 * A291032 A006234 A094821

Adjacent sequences: A090323 A090324 A090325 * A090327 A090328 A090329

Keyword

nonn,easy

Author

Peter R. J. Asveld, Jan 27 2004

Extensions

More terms from Robert G. Wilson v, Jan 30 2004

Status

approved