|
|
A090349
|
|
Pascal-like triangle read by rows. Number of nonterminal symbols (which generate strings of length k) in a certain "divide-and-conquer" context-free grammar in Chomsky normal form that generates all permutations of n symbols.
|
|
2
|
|
|
1, 2, 1, 3, 3, 1, 4, 6, 0, 1, 5, 10, 10, 0, 1, 6, 15, 20, 0, 0, 1, 7, 21, 35, 35, 0, 0, 1, 8, 28, 0, 70, 0, 0, 0, 1, 9, 36, 84, 126, 126, 0, 0, 0, 1, 10, 45, 120, 0, 252, 0, 0, 0, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
a(n,k) = C(n,k), if k = ceiling(n/(2^i)) or k = floor(n/(2^i)) for some i with 0 <= i <= ceiling(log_2 n); a(n,k)=0 otherwise.
|
|
EXAMPLE
|
Triangle begins:
1;
2, 1;
3, 3, 1;
4, 6, 0, 1;
5, 10, 10, 0, 1;
6, 15, 20, 0, 0, 1;
7, 21, 35, 35, 0, 0, 1;
8, 28, 0, 70, 0, 0, 0, 1;
9, 36, 84, 126, 126, 0, 0, 0, 1;
10, 45, 120, 0, 252, 0, 0, 0, 0, 1;
...
Example grammar: S -> EF | FE | GH | HG | IJ | JI, E -> AB | BA, F -> CD | DC, G -> AC | CA, H -> BD | DB, I -> AD | DA, J-> BC | CB, A-> a, B-> b, C-> c, D -> d; so a(4,4)=#{S}=1, a(4,3)=#{}=0, a(4,2)=#{E,F,G,H,I,J}=6 and a(4,1)= #{A,B,C,D}=4.
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|