OFFSET
0
COMMENTS
The row length sequence N (the Narayana sequence) of this irregular triangle is A000930(n+2), n >= 0.
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.
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.
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.
The row sums give 1, 1, 1, 0, for n = 0..3, and A097333(n-4) for n >= 4.
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.
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.
The number of 0's at level n is N(n) - A(n) = A(n+2) - A(n) = A058278(n+2), n >= 0.
This is a rooted incomplete binary tree with vertices (nodes) 0 having outdegree 1, and the other vertices, 1 and -1, have outdegree 2.
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.
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.
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).
REFERENCES
A. P. Juschkewitsch, Geschichte der Mathematik im Mittelalter, 1964, Pfalz-Verlag, Basel, p. 152.
LINKS
FORMULA
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".
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.
EXAMPLE
The irregular triangle T(n, k) with row length A000930(n+2) begins:
n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
0: 1
1: 1 0
2: 1 0 0
3: 1 0 0 -1
4: 1 0 0 -1 1 0
5: 1 0 0 -1 1 0 1 0 0
6: 1 0 0 -1 1 0 1 0 0 1 0 0 -1
...
7: 1 0 0 -1 1 0 1 0 0 1 0 0 -1 1 0 0 -1 1 0,
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,
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,
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.
...
Number of 1's and -1's at level 4 (absolute row sum): 2 = A000930(4).
Growth (length increase) from level 4 to 5 is 3 because level 4 has two 1's and one -1's.
Row length level 5: N(5) = N(4) + A000930(4) = 6 + 3 = 9.
Number of 0's and -1's at level 5: 5 + 1 = 6 =
A000930(5+1).
Number of -1's at level 6: 2 = A000930(6-3).
CROSSREFS
KEYWORD
sign,easy,tabf
AUTHOR
Wolfdieter Lang, Apr 20 2015
STATUS
approved