|
|
A090328
|
|
Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols.
|
|
1
|
|
|
1, 4, 12, 35, 103, 306, 914, 2737, 8205, 24608, 73816, 221439, 664307, 1992910, 5978718, 17936141, 53808409, 161425212, 484275620, 1452826843, 4358480511, 13075441514, 39226324522, 117678973545, 353036920613, 1059110761816, 3177332285424, 9531996856247
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (5*3^n)/12 + n/2 - 3/4.
a(n) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3). - Colin Barker, Jan 15 2015
G.f.: x*(x^2 + x - 1) / ((x-1)^2*(3*x-1)). - Colin Barker, Jan 15 2015
|
|
EXAMPLE
|
S -> AD | DA | BE | EB | CF, D-> BC, E -> AC, F -> AB | BA, A -> a, B -> b, C -> c; so a(3)=12.
|
|
MATHEMATICA
|
a[n_] := (15*3^n)/36 + n/2 - 3/4; Table[ a[n], {n, 1, 26}] (* Robert G. Wilson v, Jan 29 2004 *)
|
|
PROG
|
(PARI) Vec(x*(x^2+x-1)/((x-1)^2*(3*x-1)) + O(x^100)) \\ Colin Barker, Jan 15 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|