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

45 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

lettyharry said...

This is really nice to read content of this blog. A is very extensive and vast knowledgeable platform has been given by this blog. I really appreciate this blog to has such kind of educational knowledge.
HPE ProLiant DL80 Gen9

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 ทำกำไร

kate technologies said...

Nice blog..! I really loved reading through this article. Thanks for sharing such a amazing post with us and keep blogging...
free internship programs
computer science internships
engineering internships in hyderabad

polly hexan 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.
ระบบเทรด

polly hexan 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 ให้รวย

polly hexan 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 คืออะไร

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.
กติกา 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 ข่าว

lisa Merry 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

Baker Axton said...

I constantly like to read a top quality content having accurate info pertaining to the subject and the exact same thing I found in this article. Nice job.
สอน เล่น forex

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

Dicosta Sherry 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

Dicosta Sherry 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

fernanda zax11 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

fernanda zax11 said...

creativity of writer is purely impressive. It has touched to the level of expertise with his writing. Everything is up to the mark. Written perfectly and I can use such information for my coming assignment.vve beheer amsterdam