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.
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
KEYWORD
tabl,nonn
AUTHOR
Eser Camlibel, Feb 01 2024
STATUS
approved