|
Search: id:A092285
|
|
|
| A092285 |
|
Number of productions of a certain ``divide-and-conquer'' context-free grammar in Chomsky normal form that generates all permutations of n symbols. |
|
+0
2
|
|
| 1, 4, 12, 22, 65, 116, 399, 554, 2475, 3232, 14938, 20208, 101413, 130846, 691890, 924946, 4867559, 6281552, 35154066, 46902128
(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) = Sum(k=1..n, t(n, k)*C(k, ceiling[k/2])), where t(n, k) is the n-th row in the Pascal-like triangle of A090349, and C(k, i) is the binomial coefficient.
|
|
EXAMPLE
|
a(4) = 4*C(1,1) + 6*C(2,1) + 0*C(3,2) + 1*C(4,2) = 4 + 12 + 0 + 6 = 22; cf. the example grammar in A090349.
|
|
CROSSREFS
|
Cf. A090349.
Sequence in context: A008161 A008243 A008194 this_sequence A016440 A008010 A047957
Adjacent sequences: A092282 A092283 A092284 this_sequence A092286 A092287 A092288
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Peter R. J. Asveld (infprja(AT)cs.utwente.nl), Jan 30 2004
|
|
|
Search completed in 0.002 seconds
|
