A257234 - OEIS

%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