|
|
A092285
|
|
Number of productions of a certain "divide-and-conquer" context-free grammar in Chomsky normal form that generates all permutations of n symbols.
|
|
2
|
|
|
1, 4, 12, 22, 65, 116, 399, 554, 2475, 3232, 14938, 20208, 101413, 130846, 691890, 924946, 4867559, 6281552, 35154066, 46902128, 253485141, 328375720, 1877693458, 2504042868, 13754442225, 17885555976, 103317302754, 137761862662, 765705075439, 998817493980
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
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.
|
|
PROG
|
(PARI) a(n)={my(b=vector(n)); for(i=0, logint(n, 2), b[n>>i]=1; b[((n-1)>>i)+1]=1); sum(k=1, n, b[k]*binomial(n, k)*binomial(k, k\2))} \\ Andrew Howroyd, Feb 29 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|