|
%I #10 Jun 16 2019 08:07:18
%S 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,
%T 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
%N 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.
%H P. R. J. Asveld, <a href="http://dx.doi.org/10.1016/j.tcs.2005.11.010">Generating all permutations by context-free grammars in Chomsky normal form</a>, Theoretical Computer Science 354 (2006) 118-130.
%F 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.
%e Triangle begins:
%e 1;
%e 2, 1;
%e 3, 3, 1;
%e 4, 6, 0, 1;
%e 5, 10, 10, 0, 1;
%e 6, 15, 20, 0, 0, 1;
%e 7, 21, 35, 35, 0, 0, 1;
%e 8, 28, 0, 70, 0, 0, 0, 1;
%e 9, 36, 84, 126, 126, 0, 0, 0, 1;
%e 10, 45, 120, 0, 252, 0, 0, 0, 0, 1;
%e ...
%e 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.
%K nonn,tabl
%O 1,2
%A _Peter R. J. Asveld_, Jan 29 2004
|
