login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A090327 Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols. 2
1, 4, 11, 30, 83, 234, 671, 1950, 5723, 16914, 50231, 149670, 446963, 1336794, 4002191, 11990190, 35937803, 107747874, 323112551, 969075510, 2906702243, 8719058154, 26155077311, 78461037630, 235374724283, 706107395634, 2118288632471, 6354798788550 (list; graph; refs; listen; history; text; internal format)
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 (6,-11,6).

FORMULA

a(n) = ceiling[ (5*3^(n-2))/2 + 2^(n-1) - 1/2 ] for n > 1.

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

a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3) for n >= 5. - Robert Israel, Jan 15 2015

EXAMPLE

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

MAPLE

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'):

seq(f(n), n=1..100); # Robert Israel, Jan 15 2015

MATHEMATICA

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 *)

PROG

(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

CROSSREFS

Sequence in context: A019496 A021006 A078141 * A183118 A183125 A183123

Adjacent sequences:  A090324 A090325 A090326 * A090328 A090329 A090330

KEYWORD

nonn,easy

AUTHOR

Peter R. J. Asveld, Jan 27 2004

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 12:35 EDT 2018. Contains 316263 sequences. (Running on oeis4.)