|
| |
|
|
A090326
|
|
Number of rules of a context-free grammar in Chomsky normal form that generates all permutations of n symbols.
|
|
0
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
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: A171309 A071719 A164619 * A006234 A094821 A071723
Adjacent sequences: A090323 A090324 A090325 * A090327 A090328 A090329
|
|
|
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
|
| |
|
|
