https://oeis.org/A000108
Normally I use "bc" tool for arbitrary precision calculations, but realized that MicroPython allows for that as well. And I wanted to learn on (Micro)Python's lambda functions. Since functools module seems not available for MicroPython, I created my own "apply(range,func)" function (concatenation of tuples):C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009
Code: Select all
def apply(r,f):
R=()
for i in r:
R += f(i),
return R
These are the basic "bin(n,k)" and "C(n)" functions I used:
Code: Select all
def bin(n,k):
return 1 if k<=0 else bin(n-1,k-1) * n // k
def C(n):
return bin(2*n,n) // (n+1)
This code computed part of above identity the imperative way:
Code: Select all
def sigma(p,q):
s=0
for i in range(p):
for j in range(q):
s+=C(i)*C(j)*C(p+q-i-j-1)
return s
print(sigma(11,11))
It took me a while to correctly uise lamda and sum functions to compute same value -- the "sum(apply(..." looks more like mathematical "Sum_{...}...":
Code: Select all
def siglam(p,q):
return sum(apply(range(p),
lambda i: sum(apply(range(q),
lambda j: C(i)*C(j)*C(p+q-i-j-1)
)
)
)
)
print(siglam(11,11))
Finally I wanted to check that identity is valid, but stack size limited what is possible. Anyway the "tst()" function allows for nice way to pass lambda functions with two arguments. Boolean values False/True are converted to 0/1 by "sum()" function. So overall sum returning 0 means that all (negative) identities tested are valid:
Code: Select all
def tst(n, f):
return sum(apply(range(n+1),
lambda p: sum(apply(range(p+1),
lambda q: f(p,q)
)
)
)
)
print(tst(8, lambda p,q: siglam(p,q) != sigma(p,q)))
print(tst(8, lambda p,q: C(p+q)-C(p)*C(q) != sigma(p,q)))
print("[bin(9+1,2)="+str(tst(8, lambda p,q: 1))+"]")
The last line tells the number of tests done in total:
Code: Select all
>>>
MPY: soft reboot
MicroPython v1.14 on 2021-04-13; Raspberry Pi Pico with RP2040
Type "help()" for more information.
>>> import catalan
88026769844
88026769844
0
0
[bin(9+1,2)=45]
>>>
Finaly this is complete "catalan.py":
Code: Select all
def bin(n,k):
return 1 if k<=0 else bin(n-1,k-1) * n // k
def C(n):
return bin(2*n,n) // (n+1)
def apply(r,f):
R=()
for i in r:
R += f(i),
return R
def sigma(p,q):
s=0
for i in range(p):
for j in range(q):
s+=C(i)*C(j)*C(p+q-i-j-1)
return s
print(sigma(11,11))
def siglam(p,q):
return sum(apply(range(p),
lambda i: sum(apply(range(q),
lambda j: C(i)*C(j)*C(p+q-i-j-1)
)
)
)
)
print(siglam(11,11))
def tst(n, f):
return sum(apply(range(n+1),
lambda p: sum(apply(range(p+1),
lambda q: f(p,q)
)
)
)
)
print(tst(8, lambda p,q: siglam(p,q) != sigma(p,q)))
print(tst(8, lambda p,q: C(p+q)-C(p)*C(q) != sigma(p,q)))
print("[bin(9+1,2)="+str(tst(8, lambda p,q: 1))+"]")