|
%I #15 Jun 13 2015 00:51:16
%S 1,4,12,35,103,306,914,2737,8205,24608,73816,221439,664307,1992910,
%T 5978718,17936141,53808409,161425212,484275620,1452826843,4358480511,
%U 13075441514,39226324522,117678973545,353036920613,1059110761816,3177332285424,9531996856247
%N Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols.
%H Colin Barker, <a href="/A090328/b090328.txt">Table of n, a(n) for n = 1..1000</a>
%H P. R. J. Asveld, <a href="http://dx.doi.org/10.1016/j.tcs.2005.11.010">Generating all permutations by context-free grammars in Chomsky normal form</a>, Theoretical Computer Science 354 (2006) 118-130.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,3).
%F a(n) = (5*3^n)/12 + n/2 - 3/4.
%F a(n) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3). - _Colin Barker_, Jan 15 2015
%F G.f.: x*(x^2 + x - 1) / ((x-1)^2*(3*x-1)). - _Colin Barker_, Jan 15 2015
%e S -> AD | DA | BE | EB | CF, D-> BC, E -> AC, F -> AB | BA, A -> a, B -> b, C -> c; so a(3)=12.
%t a[n_] := (15*3^n)/36 + n/2 - 3/4; Table[ a[n], {n, 1, 26}] (* _Robert G. Wilson v_, Jan 29 2004 *)
%o (PARI) Vec(x*(x^2+x-1)/((x-1)^2*(3*x-1)) + O(x^100)) \\ _Colin Barker_, Jan 15 2015
%K nonn,easy
%O 1,2
%A _Peter R. J. Asveld_, Jan 27 2004
%E More terms from _Robert G. Wilson v_, Jan 29 2004
|
