|
Search: id:A090326
|
|
|
| A090326 |
|
Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols. |
|
+0
1
|
|
| 1, 4, 15, 54, 185, 608, 1939, 6058, 18669, 57012, 173063, 523262, 1577953, 4750216, 14283387, 42915666, 128878037, 386896220, 1161212911, 3484687270, 10456158921, 31372671024, 94126401635, 282395982074, 847221500605
(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) = 3^n - 2^(n+1) + n + 1.
|
|
EXAMPLE
|
S -> AD | DA | BE | EB | CF | FC, D -> BC | CB, E -> AC | CA, F -> AB | BA, A -> a, B -> b, C -> c; so a(3)=15.
|
|
MATHEMATICA
|
f[n_] := 3^n - 2^(n + 1) + n + 1; Table[ f[n], {n, 1, 26}] (from Robert G. Wilson v Jan 30 2004)
|
|
CROSSREFS
|
Sequence in context: A162978 A071719 A164619 this_sequence A006234 A094821 A071723
Adjacent sequences: A090323 A090324 A090325 this_sequence A090327 A090328 A090329
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Peter R. J. Asveld (infprja(AT)cs.utwente.n), Jan 27 2004
|
|
EXTENSIONS
|
More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Jan 30 2004
|
|
|
Search completed in 0.002 seconds
|
