Wednesday, October 13, 2010

Why do we need integrals in Computer Science?

A comment on previous post asked why we need integrals for computer science. One reason is that combinatorial expressions often have representation in terms of integrals. Consider binomial coefficients. We have the following

$${n \choose \frac{n+d}{2}}=\frac{1}{2 \pi} \int_{-\pi}^\pi e^{-\mathbb{i} q d} (2\cos q)^n dq$$


To see where this comes from, consider that $2 \cos x=e^{-\mathbb{i}\pi}+e^{\mathbb{i}\pi}$ is the generating function for number of one step walks starting at 0. Coefficients give number of those walks ending at 1 and -1. Raise it to $n$ and apply inverse Fourier transform to get number of $n$ step walks ending at at $d$, which has an alternative representation in terms of binomial coefficient.

Here's what the result looks like for arbitrary $d$ with $n=10$




Another way to get binomial coefficients is to note that they form coefficients of power of $x$ in expansion of $(1+x)^n$. Use Cauchy's integral formula to recover the coefficient.

We get the following

$${n \choose k} = \frac{1}{2\pi \mathbb{i}}\oint_c \frac{(1+x)^n}{x^{k+1}}$$

Contour integral is counter-clockwise around some contour that encircles the origin.
For instance, you can use the following contour.



Mathematica notebook

13 comments:

Aamir said...

nice article, for more visit my blog : http://www.mycodingland.com/

Arthur Mendoza said...

There has some transcription companies so that they can give you service as you might need to transcription in some of unknown languages. http://www.sopformat.com/best-internship-statement-of-purpose-format/ that is very helpful for the academic papers writing.

Charles Kee said...

Education is really an important matter and you need to do your study purposes beyond your limited as there has a word and it is as much as you know, it always help. follow the link that is good and you'll be get and helpful ideas on the subject of academic papers writing.

Navya paithara said...

I have read your blog its very attractive and impressive. I like your blog machine learning online training

poni said...

These integral in your computer let you know about the math side and help you out on program http://www.mbacapstoneproject.com/capstone-project-topics-for-mba-marketing/
capstone-project-topics-for-mba-marketing/ to know about the marketing side mba courses.

linda said...

We do need those integral in order to do the program things perfectly. When you go to this site
you will know about their dissertation writing service and all of those qualities.

jgg said...

Gracefully written information on this blog are going to support me for my coming assignments. Every point was very clear and taught me few new parameters. I would like to use this information in coming future.
therapeut haarlem

jgg said...

Me and my team was in search of a rarely found platform which can help us for our new assignment. We are writers and its been a long time we are in this writing field. So we would appreciate help of this blog.
excel cursus amsterdam

lira remme said...

Your post is providing some really good information. I liked its essence and enjoyed reading it. Keep sharing such important posts about this blog and its much more helpful for us .
Cisco WAP121

lira remme said...

Story of this blog is well written. The writer kept in consideration the grammar very well. Level of English also very well. Lot many new words has been used while writing content of this blog.
เรียน ged

Unknown said...

This blog aware me about different programs which can become very useful for our friends and kids. Few websites provide combined courses and few of the are separately for single subject. Glad to get this information.
ตลาด forex

polly hexan said...

Most of the blogs pretend themselves as most usable and updated blogs with new information but sometime truth might different. I want to share some facts related to this subject which will help people to enhance their skills.
เรียน a level

polly hexan said...

Sometime few educational blogs become very helpful while getting relevant and new information related to your targeted area. As I found this blog and appreciate the information delivered to my database.
วิธีการเล่น blackjack