login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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 (5,-7,3).

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

Sequence in context: A079736 A035045 A196859 * A200541 A149318 A233181

Adjacent sequences:  A090325 A090326 A090327 * A090329 A090330 A090331

KEYWORD

nonn,easy

AUTHOR

Peter R. J. Asveld, Jan 27 2004

EXTENSIONS

More terms from Robert G. Wilson v, Jan 29 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 05:41 EDT 2021. Contains 348035 sequences. (Running on oeis4.)