A369792 Triangle read by rows: T(n,k) is the number of steps in constructing a tree f(n,k) where f(a,b) = f(f(a-1,b), f(a,b-1)), f(0,b) = f(b-1,b-1), f(a,0) = f(a-1,a-1), f(0,0) = 0; n >= 0, k = 0..n.

1, 2, 6, 7, 15, 32, 33, 50, 84, 170, 171, 223, 309, 481, 964, 965, 1190, 1501, 1984, 2950, 5902, 5903, 7095, 8598, 10584, 13536, 19440, 38882, 38883, 45980, 54580, 65166, 78704, 98146, 137030, 274062, 274063, 320045, 374627, 439795, 518501, 616649, 753681, 1027745, 2055492

Offset

0,2

Comments

An application of one of the rules for f is one step.

Rule f(a,b) = f(f(a-1,b), f(a,b-1)) is one step, and when its components f(a-1,b) and f(a,b-1) both reach 0, rule f(0,0) = 0 is an additional step, and hence "+ 2" in the T formula below.

The rules are symmetric in a,b so the number of steps for f(a,b) is the same as for f(b,a), so the sequence is formed as a triangle 0 <= k <= n.

Links

Table of n, a(n) for n=0..44.

Formula

T(0,0) = 1.

T(n,0) = T(n-1,n-1) + 1.

T(n,n) = 2*T(n,n-1) + 2.

T(n,k) = T(n-1,k) + T(n,k-1) + 2, for 0 < k < n.

Example

Triangle begins:
        k = 0      1      2      3      4      5       6        7
  n=0:      1;
  n=1:      2,     6;
  n=2:      7,    15,    32;
  n=3:     33,    50,    84,   170;
  n=4:    171,   223,   309,   481,   964;
  n=5:    965,  1190,  1501,  1984,  2950,  5902;
  n=6:   5903,  7095,  8598, 10584, 13536, 19440,  38882;
  n=7:  38883, 45980, 54580, 65166, 78704, 98146, 137030, 274062;
  ...
For n=2 and k=1, the construction steps are as follows (with multiple steps applied together on separate f parts):
  f(2,1)                                 +1
  f(f(1,1),f(2,0))                       +2
  f(f(f(0,1),f(1,0)),f(1,1))             +3
  f(f(f(0,0),f(0,0)),f(f(0,1),f(1,0)))   +4
  f(f(0,0),f(f(0,0),f(0,0)))             +3
  f(0,f(0,0))                            +1
  f(0,0)                                 +1
  0
                          T(2,1) = Sum = 15.
Each line in the following tree diagram is an edge and is a step, with T(2,1) = 15 altogether:
.
          f(2,1)
           /   \
          /     \
         /       \
        /         \
       /           \
      /             \
     /               \
    f(1,1)            f(2,0)
     /   \              |
    /     \             |
   /       \            |
  f(0,1)    f(1,0)      f(1,1)
      |       |          /   \
      |       |         /     \
      |       |        /       \
      f(0,0)  f(0,0)  f(0,1)    f(1,0)
         |       |        |       |
         0       0        f(0,0)  f(0,0)
                             |       |
                             0       0

Prog

(C++)
#include <iostream>
int counter;
int f(int a, int b) {
    counter++;
    if (a>0 && b>0) {
        return f(f(a-1, b), f(a, b-1));
    } else if (a>0) {
        return f(a-1, a-1);
    } else if (b>0) {
        return f(b-1, b-1);
    }
     return 0;
}
int main() {
    for(int i=0; i<10; i++){
        for(int j=0; j<i; j++){
            counter=0;
            int result = f(i, j);
            std::cout << "f("<<i<<", "<<j<<") = " << counter << std::endl;
        }
    }
    return 0;
}
(PARI)
T(n)={my(v=vector(n+1), u=[1]); v[1]=u; for(i=2, #v, u=vector(i); u[1]=1+v[i-1][i-1]; for(j=2, i-1, u[j]=2+u[j-1]+v[i-1][j]); u[i]=2*(1+u[i-1]); v[i]=u); v}
{ my(A=T(7)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Feb 04 2024

Crossrefs

Sequence in context: A078113 A286054 A340376 * A030607 A330476 A177353

Adjacent sequences: A369789 A369790 A369791 * A369793 A369794 A369795

Keyword

tabl,nonn

Author

Eser Camlibel, Feb 01 2024

Status

approved