|
%I #16 Jun 13 2015 00:51:16
%S 1,4,11,30,83,234,671,1950,5723,16914,50231,149670,446963,1336794,
%T 4002191,11990190,35937803,107747874,323112551,969075510,2906702243,
%U 8719058154,26155077311,78461037630,235374724283,706107395634,2118288632471,6354798788550
%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="/A090327/b090327.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 (6,-11,6).
%F a(n) = ceiling[ (5*3^(n-2))/2 + 2^(n-1) - 1/2 ] for n > 1.
%F G.f.: -x*(2*x^3-2*x^2-2*x+1) / ((x-1)*(2*x-1)*(3*x-1)). - _Colin Barker_, Jan 15 2015
%F a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3) for n >= 5. - _Robert Israel_, Jan 15 2015
%e S -> AD | DA | BE | EB, D -> BC | CB, E -> AC | CA, A -> a, B -> b, C-> c; so a(3)=11.
%p f:= gfun:-rectoproc({a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3),a(1)=1,a(2)=4,a(3)=11,a(4)=30},a(n),'remember'):
%p seq(f(n),n=1..100); # _Robert Israel_, Jan 15 2015
%t f[n_] := Ceiling[5/2*3^(n - 2) + 2^(n - 1) - 1/2]; Table[ f[n], {n, 2, 27}] (* _Robert G. Wilson v_, Jan 30 2004 *)
%o (PARI) Vec(-x*(2*x^3-2*x^2-2*x+1)/((x-1)*(2*x-1)*(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 30 2004
|
