Ask Your Question
0

Checking identity of two combinatorial expressions

asked 2019-08-20 22:42:42 +0200

joakim_uhlin gravatar image

updated 2019-08-20 23:36:55 +0200

I have a reason to believe that a certain combinatorial identity holds for even integers $n, k$ that satisfies $2 \leq k \leq n/2$ and $n\geq 4$. To test it in Sage, I denote the expression on the right- and lefthandside as the functions RHS$(n,k)$ and LHS$(n,k)$ respectively and check if they agree for a variety of values $n$ and $k$.

def t(n,k):
    sum=0
    for i in range(n-2*k+1):
        sum+=binomial(n-2*k,i)
    return n/k*sum*binomial(n-4,2*k-4)*catalan_number(k-2)

def LHS(n,k):
    return n/2*((n/2+1-k)/(n/2+1)*t(n/2+1,k/2)+2*(k/2+1)/(n/2+1)*t(n/2+1,k/2+1))

def RHS(n,k):
    return (n/k)*(2**(n/2-k))*binomial(n/2-2,k-2)*binomial(k-2,k/2-1)

But when run the following code

for n in range(6,12,2):
    for k in range(2,floor(n/2)+1,2):
        print("n="+str(n)+", k="+str(k))
        print(bool(LHS(n,k)==RHS(n,k)))

I get the output

n=6, k=2
True
n=8, k=2
True
n=8, k=4
True
n=10, k=2
True
n=10, k=4
False

which would indicate that the identity does not hold for $n=10$, $k=4$. However, when I write

print(bool(LHS(10,4)==RHS(10,4)))

I get the output TRUE (I also double checked this by hand, and both sides agree and are equal to $30$ in this case).

  1. Why does the code in the double loop yield the wrong answer? EDIT: answered by rburing

  2. Is there a better way to check equalities similar to this in Sage?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2019-08-20 23:10:24 +0200

rburing gravatar image

The difference is that in the for loop you use range so you get Python int objects, and when you type 10 you get a SageMath Integer (thanks to the preparser). For int objects in Python 2, / is floor division, so you get 10/4 == 2. Use srange if you want a range of SageMath Integers.

edit flag offensive delete link more

Comments

Thank you for your answer. I am still interested in the second question but if I get no other replies, I will accept your answer.

joakim_uhlin gravatar imagejoakim_uhlin ( 2019-08-20 23:38:35 +0200 )edit
1

The way you are testing seems fine to me. The explicit bool() looks unnecessary. Division of ints in Python 3 is different, and that explains Emmanuel's answer.

rburing gravatar imagerburing ( 2019-08-21 00:49:01 +0200 )edit
1

answered 2019-08-20 23:05:51 +0200

Emmanuel Charpentier gravatar image

Your example WorksForMe(TM):

Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:for n in range(6,12,2):
:    for k in range(2,floor(n/2)+1,2):
:        print("n="+str(n)+", k="+str(k))
:        print(bool(LHS(n,k)==RHS(n,k)))
:
:--
n=6, k=2
True
n=8, k=2
True
n=8, k=4
True
n=10, k=2
True
n=10, k=4
True

This is on 8.9.beta7 with Python 3. What version of Sage are you using ?

edit flag offensive delete link more

Comments

I am currently using 8.3, using the notebook if that is of any relevance.

joakim_uhlin gravatar imagejoakim_uhlin ( 2019-08-20 23:36:07 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-08-20 22:42:42 +0200

Seen: 234 times

Last updated: Aug 20 '19