|
Search: id:A090327
|
|
|
| A090327 |
|
Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols. |
|
+0
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
(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) = ceiling[ (5*3^(n-2))/2 + 2^(n-1) - 1/2 ] for n > 1.
|
|
EXAMPLE
|
S -> AD | DA | BE | EB, D -> BC | CB, E -> AC | CA, A -> a, B -> b, C-> c; so a(3)=11.
|
|
MATHEMATICA
|
f[n_] := Ceiling[5/2*3^(n - 2) + 2^(n - 1) - 1/2]; Table[ f[n], {n, 2, 27}] (from Robert G. Wilson v Jan 30 2004)
|
|
CROSSREFS
|
Sequence in context: A019496 A021006 A078141 this_sequence A104743 A004080 A027115
Adjacent sequences: A090324 A090325 A090326 this_sequence A090328 A090329 A090330
|
|
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 30 2004
|
|
|
Search completed in 0.002 seconds
|
