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
Examples
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.
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).
Programs
-
Mathematica
f[n_] := 3^n - 2^(n + 1) + n + 1; Table[ f[n], {n, 1, 26}] (* Robert G. Wilson v, Jan 30 2004 *) -
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
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
Extensions
More terms from Robert G. Wilson v, Jan 30 2004