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

44 comments:

Aamir said...

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

Unknown 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.

Unknown 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

Unknown 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

Unknown 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...

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

lettyharry said...

Share great information about your blog , Blog really helpful for us . We read your blog , share most useful information in blog . Thanks for share your blog here .
ระบบ เทรด forex

lettyharry 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 trading demo

lettyharry 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.
ใช้ MACD Forex ทำกำไร

Unknown 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 .
เกมปาจิงโกะ

lettyharry 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.
Forex Bitcoin คือ

lettyharry said...

It is really a helpful blog to find some different source to add my knowledge. I came into aware of new professional blog and I am impressed with suggestions of author.
ระบบเทรด

Unknown said...

I came to this blog and it helped me to add few new points to my knowledge. Actually, I am trying to learn new thing wherever I find. Impressive written blog and valuable information shared here.
เล่น exness ให้รวย

Unknown said...

Share great information about your blog , Blog really helpful for us . We read your blog , share most useful information in blog . Thanks for share your blog here .
Gap คืออะไร

Unknown 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.
กติกา poker

millisemmy said...

Wow! This is the perfect blog I am looking this type of blog its awesome blog here , share great information about this topic. This informative blog helps many readers with their decision-making regarding the situation. Great articles and will look forward for more!
หุ้น forex คือ

millisemmy said...

Sometimes is becomes very hard to take appreciation for your hard work. But sometime only few technical point makes your work worthwhile. Suggestion under this blog is quite good.
รับผลิตถุงผ้า ลดโลกร้อน

sollyseny said...

A writer should always try to keep its writing very simple and clear. Always use facts which are easily acceptable by general people because they are very close to their assumptions and they welcome such kind of facts.?
กติกาการเล่นบาคาร่า

sollyseny said...

A blog must be connected to the person in need. It is really important to understand the actual feel of such necessity and the essence of objective behind it. Author must give proper time to understand every topic before writing it.
เล่นพนันให้รวย

sollyseny said...

Hey, It really is incredibly fantastic and informative website. Good to discover your site Very well article! I’m simply in love with it.
forex ข่าว

Unknown said...

No one can stop you writing a perfect blog or article if you are passionate to your job. Your aim is to satisfy your readers with a well written blog and your passion is always behind your every successful assignment. Impressive writing skills can be observed over here.
กฎ poker

lisysomna said...

No one can stop you writing a perfect blog or article if you are passionate to your job. Your aim is to satisfy your readers with a well written blog and your passion is always behind your every successful assignment. Impressive writing skills can be observed over here.
โฟ เร็ ก

Wheel-shark said...

Detailed and descriptive articles written in this blog is really very helpful for me as well as for other who seeking such kind of knowledge. It is definitely going to become useful in coming future.
วิธีเล่นไพ่นกกระจอก

Wheel-shark said...

Now day, everything is going to find a new but well settled and successful stream for their career. When I came to this blog, I really impressed by all the knowledge points mentioned here. Thank you for this assistance.
Ablerex UPS EVO RT SERIES

quickserv.co.th said...

Surprising background experienced in everything sentence of this article. I made a decent attempt to get hint about how I could demonstrate substance of this blog. I must say, not much powerful but rather I surrendered every one of my weapons soon after understanding it.
ส่วนลด ais

quickserv.co.th said...

I gained new knowledge from well written content of this blog. It is showing some different kind of strategy to keep work better and improve with every new assignment. Gracefully written blog
ged thailand

lisysomna said...

Sometimes is becomes very hard to take appreciation for your hard work. But sometime only few technical point makes your work worthwhile. Suggestion under this blog is quite good.
t shirt printing new york

gibsonherry said...

I am thankful to this blog for assisting me. I added some specified clues which are really important for me to use them in my writing skill. Really helpful stuff made by this blog.
Dell PowerEdge T640

gibsonherry said...

our enthusiasm leads you beyond the limits. When you feel yourself enthusiastic that’s the time you can cross any limit. You seek to get perfection by using the ability of work. Read such motivational article and definitely it will help you to know new facts.
โรงเรียน ged

mrkdvsn said...

Happy to found this blog. I have some facts related to this blog and I would like to share with all its readers. Definitely it is going to help everyone and aware people with some more knowledgeable points.
ged 2014

mrkdvsn said...

Nice to read this publication on this blog. As far as I can see, this is a very basic question for everyone indeed. Its my personal opinion and I am completely agreed with the subject used here
Breakaway Gap คือ

mrkdvsn said...

Obviously, the collection of a writer must be a bundle of creativity. New ideas of writing become the reason of success. It makes your work worthwhile. Everyone wants to praise your writing because they bound by creativity.
การ เทรด ค่า เงิน

mrkdvsn 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.
opleiding eigen bedrijf

farnandazax said...

This is the first time I came to this blog and I found some relevant stuff here. Basically I keen to know new parameters of writing every-time and sometime it become really very hard to find such kind of platform.
massage amsterdam

Unknown said...

This blog is really helpful regarding all educational knowledge I earned. It covered a great area of subject which can assist a lot of needy people. Everything mentioned here is clear and very useful.ติว igcse international mathematics 

gibsonherry said...

our enthusiasm leads you beyond the limits. When you feel yourself enthusiastic that’s the time you can cross any limit. You seek to get perfection by using the ability of work. Read such motivational article and definitely it will help you to know new facts.
วิธี เลือก ซื้อ โน๊ ต บุ๊ค

remo said...

THANKS FOR THE INFORMATION...
<a href="http://www.chloros.in/digital-marketing-internship.htmlhttp://www.chloros.in/digital-marketing-internship.html>Digital Marketing Internship Program in Bangalore</a>

draj said...



Excellent machine learning blog,thanks for sharing...
Seo Internship in Bangalore
Smo Internship in Bangalore
Digital Marketing Internship Program in Bangalore

minhpv2910 Blog said...

Oh my goodness! Awesome article dude! Thanks, However I am having issues with your RSS. I don?t know the reason why I can't subscribe to it. Is there anybody else having the same RSS problems? Anyone who knows the answer will you kindly respond? Thanx!!
bàn gỗ giá rẻ

Halloween Costume said...

Grateful to you, I've actually been looking for data about this subject for quite a while and yours is the best I have found till now. Halloween Costume