|
Search: id:A090328
|
|
|
| A090328 |
|
Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols. |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
P. R. J. Asveld, Generating all permutations by context-free grammars in Chomsky normal form, Theoretical Computer Science 354 (2006) 118-130.
|
|
FORMULA
|
a(n) = (5*3^n)/12 + n/2 - 3/4.
|
|
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}] (from Robert G. Wilson v Jan 29 2004)
|
|
CROSSREFS
|
Adjacent sequences: A090325 A090326 A090327 this_sequence A090329 A090330 A090331
Sequence in context: A084362 A079736 A035045 this_sequence A053595 A062858 A095735
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Peter R. J. Asveld (infprja(AT)cs.utwente.nl), Jan 27 2004
|
|
EXTENSIONS
|
More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Jan 29 2004
|
|
|
Search completed in 0.002 seconds
|
