The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #16 Apr 03 2017 23:11:13
%S 1,1,0,1,0,0,1,0,0,-1,1,0,0,-1,1,0,1,0,0,-1,1,0,1,0,0,1,0,0,-1,1,0,1,
%T 0,0,1,0,0,-1,1,0,0,-1,1,0,1,0,0,1,0,0,-1,1,0,0,-1,1,0,1,0,0,-1,1,0,1,
%U 0,0,1,0,0,-1,1,0,0,-1,1,0,1,0,0,-1,1,0,1,0,0,1,0,0,-1,1,0,1,0,0,1,0,0,-1,1,0,0,-1,1,0,1,0,0,-1,1,0,1,0,0,1,0,0,-1,1,0,1,0,0,1,0,0,-1
%N Levels of Narayana tree written as rows of an irregular triangle.
%C The row length sequence N (the Narayana sequence) of this irregular triangle is A000930(n+2), n >= 0.
%C This is a tree version of Pandit Narayana's cow problem (for a reference see Juschkewitsch, and references and links given in A000930). A cow is symbolized by 1 and after a year it produces a calf denoted by 0: 1 -> 1, 0. A newborn calf remains a calf after aging one year 0 -> 0. However, if a calf becomes two years old it is symbolized by -1 because after the next year it will become a cow which has produced also a calf: -1 -> 1, 0. At level 0 (begining of year 0) there is one cow, a 1 as root of the tree.
%C As a substitution rule with memory one takes: 1 -> 10, (1)0 -> 0, (0)0 -> -1 and -1 -> 10, where 0 is substituted depending on the number on its left, given here in brackets.The start is 1. Hence 1 -> 10 -> 100 -> 100-1 -> 100-110 -> ... . The number of symbols from {1, 0 ,-1} grows at each step by the number of 1's and -1's in the previous step.
%C The absolute row sum gives A(n) := A000930(n),which is the number of 1's and (-1)'s at level (year) n. Thus the row length N(n) = N(n-1) + A(n-1) for n >= 1.
%C The row sums give 1, 1, 1, 0, for n = 0..3, and A097333(n-4) for n >= 4.
%C The number of calves, that is, the number of 0's and (-1)'s is 0 for n = 0 and A(n+1) for n >= 1.
%C The number of -1's at level (row) n is the number of 00's in row n-1. This number is 0 for n = 0, 1, 2, and A(n-3) for n >= 3.
%C The number of 0's at level n is N(n) - A(n) = A(n+2) - A(n) = A058278(n+2), n >= 0.
%C This is a rooted incomplete binary tree with vertices (nodes) 0 having outdegree 1, and the other vertices, 1 and -1, have outdegree 2.
%C If in the Narayana tree each branch connecting two vertices 0 is contracted, together with the two end vertices 0, to a single vertex 0 then the Fibonacci tree will result.
%C The infinite NW word (NW(n), for n -> infinity) is selfsimilar if the following decimation rules (depending on the neighborhood of the letters 10 and 0) are applied: -1 -> 0, 10 (for n >=2 always existent) -> 1 for the first 10, and if the neighbors (in brackets) are (0)10 then 10 -> 1, if (-1)10(1) then 10 -> -1 and if (-1)10(0) then 10 -> 1. If (0)0 then 0 -> 0 and if (1)0 then 0 -> 1.
%C For the first 6 levels of the Narayana tree see the W. Lang link. Narayana asked how many animals are there at level n = 20, and the answer he gave was 2745 = N(20) = A000930(22).
%D A. P. Juschkewitsch, Geschichte der Mathematik im Mittelalter, 1964, Pfalz-Verlag, Basel, p. 152.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Narayana_Pandit">Narayana Pandit</a>.
%H Wolfdieter Lang, <a href="/A257234/a257234_2.pdf">Narayana Tree T_5</a>.
%F The Narayana word NW(n) over the alphabet {1, 0, -1} satisfies the Narayana recurrence NW(n) = concatenate(NW(n-1), NW(n-3)) with input NW(0) = "1", NW(1) = "10", NW(2) = "100", NW(3) = "100-1".
%F The row n of the irregular triangle T with row length N(n) = A000930(n+2) is given by NW(n) considered as a list.
%e The irregular triangle T(n, k) with row length A000930(n+2) begins:
%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
%e 0: 1
%e 1: 1 0
%e 2: 1 0 0
%e 3: 1 0 0 -1
%e 4: 1 0 0 -1 1 0
%e 5: 1 0 0 -1 1 0 1 0 0
%e 6: 1 0 0 -1 1 0 1 0 0 1 0 0 -1
%e ...
%e 7: 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0,
%e 8: 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0 1 0 0 -1 1 0 1 0 0,
%e 9: 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 1 0 0 1 0 0 -1,
%e 10: 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0.
%e ...
%e Number of 1's and -1's at level 4 (absolute row sum): 2 = A000930(4).
%e Growth (length increase) from level 4 to 5 is 3 because level 4 has two 1's and one -1's.
%e Row length level 5: N(5) = N(4) + A000930(4) = 6 + 3 = 9.
%e Number of 0's and -1's at level 5: 5 + 1 = 6 =
%e A000930(5+1).
%e Number of -1's at level 6: 2 = A000930(6-3).
%e Number of 0's at level 6: 7 = A000930(6+2) - A000930(6) = 13 - 6 = A058278(6+2).
%Y Cf. A000930, A097333, A058278.
%K sign,easy,tabf
%O 0
%A _Wolfdieter Lang_, Apr 20 2015