Talk:Binomial coefficient/Archive 1

Archive 1

use a header

Does anyone want to add the general binomial theorem (for all n). Also I have some weird alternative formulas for C(n,r) with n a non-negative integer, but I'd have to set up the pictures on a stable server or something.—The preceding unsigned comment was added by 69.22.195.18 (talk • contribs) .

Definition of binomial coefficients for n < 0

To Maxal and whoever else is willing to comment:

I would say that the recently inserted equation

$(1+x)^{n}={n \choose 0}+{n \choose 1}x+{n \choose 2}x^{2}+\dots =\sum _{k}{n \choose k}x^{k}.$

is redundant, because of

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}y^{n-k}\qquad (2)$

which shows up below.

The latter formula makes sense only for integer $n\geq 0$. While the former one is true for any n. --Maxal 22:47, 13 Apr 2005 (UTC)

The point is, everywhere in this article it is assumed that n ≥ 0. Just read through it. The Pascal triangle for example, does not hold for n < 0. I find your addition not in the right place. I think it rather belongs in a generalization section at the end of the article. What do you think? Oleg Alexandrov 23:03, 13 Apr 2005 (UTC)

Disagree. It's the only complete definition for now. And it should come first. I think Pascal triangle and other middle-school-level stuff should form a separate section. --Maxal 23:07, 13 Apr 2005 (UTC)

Please notice that the generalization to n < 0, actually, for any n complex, is at already in the article, see several sections below in there. Oleg Alexandrov 23:10, 13 Apr 2005 (UTC)

First of all, there is a bad mixture of notations. $C_{n}^{k}$ or C(n,k) is the number of combinations and it's defined only for non-negative integer n,k (Pascal's triangle is actually defined for C(n,k)). The binomial coefficient ${n \choose k}$ is a generalization of $C_{n}^{k}$ which is defined for integer k and arbitrary n. As of generalization of ${n \choose k}$ to complex n, it's ok except for notation. C(n,k) is inappropriate.

Second, the article makes accent on combinatorics where complex n have no (or very limited) application. Hence, it's ok to keep the generalization to complex n at the end. --Maxal 23:26, 13 Apr 2005 (UTC)

So, what are the applications of negative n to combinatorics? Oleg Alexandrov 23:28, 13 Apr 2005 (UTC)

Say, they often appear in expansions of generating functions. And there many self-reverse relations including them. --Maxal 23:37, 13 Apr 2005 (UTC)

So, if you want to really make some changes to this article, you should read it all, then see how to make things look nice overall. What do you think?

I've read it all, and there was no correct definition for binomial coefficients for n<0. Moreover, in the discussion you can see a request for the definition "general" binomial coefficient. I've provided a general definition of binomial coefficients (most popular in combinatorics). From this very same expansion binomial coefficients can be also defined for non-integer n but that's mainly related to analysis. --Maxal 22:47, 13 Apr 2005 (UTC)

Also, please see the sentence:

This is generalized by the binomial theorem, which allows the exponent n to be negative or a non-integer.

in the article. Did you notice it? Oleg Alexandrov 22:42, 13 Apr 2005 (UTC)

Yes but that article should not prevent for providing correct and complete definition of the binomial coefficients. --Maxal 22:47, 13 Apr 2005 (UTC)

Rewriting the first section in this article?

I am a bit unahappy about the first section in this article. There, one starts with the expansion of

$(1+x)^{n}$

only to switch later in the same section to

$(x+y)^{n}.$

One starts with an arbitrary integer n, only to continue with natural n in the next sections, and come back with arbitrary complex n a while below.

I would suggest to make the first paragraph talk only about the case of the natural number n. That is, start with the most elementary case. This will be followed naturally by the Pascal triangle, in the next section. One can expand and generalize on this later. This is consistent with Wikipedia:How to write a Wikipedia article on Mathematics. Any comments? Oleg Alexandrov 23:50, 22 Apr 2005 (UTC)

There was way too many changes to revert them at once. Reverting back. If you don't like the way it is currently presented, add/change just the first section instead of reverting the whole thing. --Maxal 23:56, 30 Apr 2005 (UTC)

As you noticed, I reverted not right away, but waited a while, then wrote the above, then waited more. I reverted all of it, because I did not want to do lots of work then you come back and revert again.

Now, I still believe the first section is better off the way it was before your changes. You made things more general at the expense of damaging the logical flow of the article.

Once we agree on that, I will put back the first section the way it was before you changed, and keep your other modifications. Oleg Alexandrov 00:06, 1 May 2005 (UTC)

There should be a clear distinction between C(n,k) and ${n \choose k}$. What is currently defined at the top is actually C(n,k), not ${n \choose k}$. So in the first two sections C(n,k) should be used while ${n \choose k}$ should appear later with complete definition as a generalization of C(n,k). --Maxal 11:46, 3 May 2005 (UTC)

I have no problems with that. However, one should mention on top that ${n \choose k}$ is an alternative notation. Oleg Alexandrov 15:46, 3 May 2005 (UTC)

Question: what is this thing?

Anyone ever see something that looks like this:

$\sum _{k=0}^{n}{n \choose k}y^{k}{\frac {1}{k!}}{\frac {d^{k}}{dx^{k}}}f(x)$

Any identities, relations, etc. for such a thing? Does it have a name? Its painfully suggestive of something but I can't put my finger on it ... (its not discussed in sheffer sequence or in binomial type or in hypergeometric series).

Other than the binomial coefficients, it looks like a Taylor expansion if y=x-a.

Alternately, how about a non-integer generalization:

$\sum _{k=0}^{\infty }{k-s-1 \choose k}(-y)^{k}{\frac {1}{k!}}{\frac {d^{k}}{dx^{k}}}f(x)$

for s not an integer? How about the special cases y=1 or y=1/2? ... linas 05:00, 19 August 2005 (UTC)

Derivation from binomial expansion

I wonder what people think of the recent section Binomial coefficient#Derivation from binomial expansion. I copy the material below from KSmrq's talk page. Oleg Alexandrov 00:48, 7 September 2005 (UTC)

Hi KSmrq. Do you really think we need that lenghy derivation at Binomial coefficient? I think it gets the reader bogged down into unnecessary detail. I would think the reader needs to know how the coefficient is defined (the binomial expansion), how it is calcuated (Pascal's triangle), how it is used (combinatorics, etc). The derivation you put in the very first section, in my view, does not really help. Maybe we could put it in another article, or at the bottom of this article, what do you think?

Also, if you feel like working on this article, the section Binomial coefficient#Formulas involving binomial coefficients should probably make you mad. There, in many places they use sentences made up of only formulas (that is, x or so is the subject, the equal sign is the verb, etc :).

Let me know what you think (on this page). Oleg Alexandrov 17:28, 5 September 2005 (UTC)

I've got a guilty conscience for other articles left hanging, so I don't want to get sucked into working a lot on this one until I've done right by the others. By making an extra section, I hoped to support any decision by those of you who are heavily involved, either to keep it, toss it, move it, or fold it in.

As for why I wrote that section and placed it there: Yes, I felt the need, for the material if not the length. The article begins with formulae, then shows Pascal's triangle and mentions combinatorics, all with no intuitive connection or motivation. What I wrote is what works for me to understand the connections. The formula n?k = n! / (n−k)! k! does derive from the expansion, which was stated but nowhere shown. And the way it is derived, as I try to show, intimately relates to both Pascal's triangle and to the combinatoric connection.

If you and the other collaborators would prefer to state a string of definitions, facts, and formulae early and push intuition, derivation, and connection later, do what you think best. I would not make that choice, because of my understanding of how my mind (as most, I think) absorbs and retains material. On the other hand, if all I want is a quick reference putting essential facts at my fingertips, then the pedagogical material might be entirely superfluous.

I'm going to clean up my contribution a little, then abandon it to its fate. Chances are I'll visit again in the future to see how things have evolved. I hope the effort goes well, because I've actually done some research work that draws on multinomial coefficients, and it would be nice if WP has a good article. --KSmrq^T 19:38, 2005 September 5 (UTC)

You have good points. However, the first section might not be the right place to state the derivation, as it is too complicated. I would prefer to have the reader first accept that formula (by faith if you wish), then understand the Pascal triangle (which is in my opinion more significant than all that induction and factorial thing). Later, when the reader also sees the applications, he/she might be tempted to understand why that is true, then your explanation kicks in. How about that? (BTW, that article is indeed in sorry state, so I'd rather have you not abandon it for a while but instead work on it :) Oleg Alexandrov 20:06, 5 September 2005 (UTC)

Analogy to Vandermondes formula

Take a sample of $n$ items from a population of $N$ items. Get $i$ special items in the sample from $I$ special items in the population. This can be done in the following number of ways:

${I \choose i}{N-I \choose n-i}$

Vandermondes formula is

$\sum _{i=0}^{n}{I \choose i}{N-I \choose n-i}={N \choose n}$

A dual formula is

$\sum _{I=0}^{N}{I \choose i}{N-I \choose n-i}={N+1 \choose n+1}$

Example: N=4, n=2
    i=0 i=1 i=2
I=0  6   0   0
I=1  3   3   0
I=2  1   4   1
I=3  0   3   3
I=4  0   0   6

From the rows you deduce $i$ knowing $I$. The row sum is ${4 \choose 2}=6$. From the columns you induce $I$ knowing $i$. The column sum is ${4+1 \choose 2+1}=10$

See the article on inferential statistics.

Bo Jacoby 07:09, 8 September 2005 (UTC)

See Vandermonde's identity. Michael Hardy 22:50, 8 September 2005 (UTC)

Uniform definitions

The last edit of the article made the notation "uniform," but I think in the wrong way. What do people prefer? ${n \choose k}$ or $\mathrm {C} (n,k)$. From my experience, the first form is used more. I also think it is easier to read when used in summation equations, much like the section "Formulas involving binomial coefficients" uses extensively. Stolee 08:10, 16 November 2005 (UTC)

Yeah, ${\rm {C}}(n,k)$ is a bad choice. ${}_{n}{\rm {C}}_{k}$ is better, but definitely the most widely used notation is $n \choose k$. Apparently the reason ${\rm {C}}(n,k)$ was chosen was for "compactness", but if you need it to be more compact, try ${\big (}{}_{k}^{n}{\big )}$, produced by <math>\big({}^{n}_{k}\big)</math>, which looks very similar to what should be produced by <math>\textstyle n\choose k</math> if the <math> tag supported \textstyle. I'm not sure why it doesn't; I should investigate that. —Bkell 01:30, 17 November 2005 (UTC)

Okay, \textstyle has been requested over at MediaZilla. It's bug 4000, which is a nice number. —Bkell 02:08, 17 November 2005 (UTC)

It was me who made the notation "uniform". C(n, k) also has the advantage that it can be written in plain text in the same font, which would not work with ${\big (}{}_{k}^{n}{\big )}$. The notation $n \choose k$ is just too huge to fit anywhere inline, one's got to use it only in displayed formulas, on separate lines.

And my primary aim was indeed to make the notation uniform, as at least three notations coexisted. I don't mind ${\big (}{}_{k}^{n}{\big )}$, but I don't see a big need for it, and again PNG images inline are not desirable, as they look of size different than text, see also the math style manual. Oleg Alexandrov (talk) 02:36, 17 November 2005 (UTC)

I am going to change most of the C(n,k) notation in displaystyle formulas to the ${\big (}{}_{k}^{n}{\big )}$ notation. Being the more widely used notation (which I don't have hard evidence for but I don't think anyone disagrees), it would make the article more readable and easier to search. But I agree that we should keep C(n,k) for inline use, just because ${\big (}{}_{k}^{n}{\big )}$ would mess up the line spacing. 09:21, 9 June 2006 (UTC)

The reason I prefer ${\big (}{}_{k}^{n}{\big )}$ over C(n, k) is mostly due to the fact that I don't see C(n, k) in use very often; it seems to be used as a fall-back if ${\big (}{}_{k}^{n}{\big )}$ is impossible, and I find it more difficult to read and work with. But you have some very good points, so I guess I'll be content with whatever is used, as long as it's consistent. [If you're going to write C(n, k) as text, though, be sure to write it as C(''n'',&nbsp;''k'').] —Bkell 04:19, 17 November 2005 (UTC)

The case of complex z

I partially undid Bo Jacoby's recent changes to this article. I don't think it is a good idea to start with a discussion of the binomial coefficient as a polynomial C(z, n) in a complex variable z. Most uses of the binomial coefficient is for C(m, n) with m and n positive integers, and most material in this article is devoted to that.

Per the math style manual, an article should start as elementary as possible, and the way binomial coefficents are first taught to people, high school or college, is using combinations (m choose n). That C(m, n) can be generalized to complex numbers shows up only when dealing with Taylor series of $(1+x)^{z}.$ I belive this can be best stated as a generalization of binomial coefficient, rather than a definition of that coefficient. Oleg Alexandrov (talk) 22:56, 23 November 2005 (UTC)

PS I agree that the article needs work. Help is appreciated. Oleg Alexandrov (talk) 22:58, 23 November 2005 (UTC)

Answer to Oleg

Compare formula A:

${n \choose k}=\prod _{j=1}^{k}{n-k+j \over j}$

with formula B:

${n \choose k}={\frac {n!}{k!(n-k)!}}$

1. Formula A does not assume that the reader knows the factorial function, as does formula B.

2. Evaluation of formula A is easier because the intermediate results are smaller numbers.

3. The definition

$n!=\prod _{k=1}^{n}k$

needs the pi-notation of the product anyway.

4. Formula A applies also to negative, fractional, real and complex values of n, where formula B is undefined for negative values of n.

So formula A is better than formula B in every respect.

I agree that the concept of complex (or even real) numbers is not needed (nor wanted) here, but there is no need to have another definition in the special case (natural n) than in the general case (complex n). Bo Jacoby 18:22, 24 November 2005 (UTC)

Your formula uses the product notation too. But I agree with you that it is easier, I added it to the article. Oleg Alexandrov (talk) 21:39, 24 November 2005 (UTC)

Recent cleanup

I saw this page on the math project list for cleanup, so I made a couple changes, revising the induction paragraph (which had some nonsense before) and moving the multinomial stuff out of the way, in particular directing to multinomial theorem. I'm not planning on spending more time on this page, so feel free to accept/reject the changes as you see fit.--Luke Gustafson 06:44, 1 January 2006 (UTC)

I reintroduced the efficient calculation of binomial coefficients in the example. It is important. Bo Jacoby 20:01, 21 January 2006 (UTC)

Proposed MERGE with Combination

This page looks like it is about the exact same topic, and I think the pages should be merged. Any takers? Fresheneesz 23:14, 4 February 2006 (UTC)

Well observed. Go ahead and merge ! Bo Jacoby 12:46, 5 February 2006 (UTC)

• JA: Keep Separate For Now. There is a signficant distinction between a combinatorial species, like a combination, and the enumerator thereof, like a binomial coefficient. One needs to think carefully, not just about the current state of the WP articles, which may be sparse, but about the literatures on the subjects, and also about the likely future developments of the two concepts, before merging the discussions of them. Jon Awbrey 13:48, 5 February 2006 (UTC)

• Don't merge. These are distinct topics. The article on "combination" could use a major cleanup, however. linas 06:07, 6 February 2006 (UTC)

I cleaned the combination article. Bo Jacoby 07:53, 6 February 2006 (UTC)

Thanks, looks better now. Oleg Alexandrov (talk) 21:07, 6 February 2006 (UTC)

I am pleased that you approve. Bo Jacoby 04:54, 8 February 2006 (UTC)

Choose function

Looking on the google for '"choose function" combinatorics', I found a bunch of different references to people calling it the choose function. I also found a bunch of more reliable references calling it the choose function (not just choose). One even explained that the reason it got that name is because it is used so often as a function of other variables. We talked about the "choose function" alot in my CS40 class. Among others, I found these references:

reference 1

reference 2

reference 3

reference 4

I'll leave it up to you Oleg, if you think they're sufficient references for puting my edit back : P Fresheneesz 03:34, 8 February 2006 (UTC)

• JA: Well, aside from being grammtically barbaric, it seems likely to cause confusion with "choice functions" in set theory. For example Constructive Mathematics. Google on <Troelstra "choice function"> for more. Jon Awbrey 05:08, 8 February 2006 (UTC)

Well, whether or not its confusing, its the way I, and many others, are taught it. I had never heard of "Binomial coefficient" before visiting this pace, even though I had learned all about it already. I think that if you're worried about confusion, a due note could be made about that in the article. Fresheneesz 08:02, 8 February 2006 (UTC)

• JA: It never ceases to e-maze me that people who would actually say out loud "I never heard of X" would think themselves qualified to write e-cyclicals about X. Jon Awbrey 14:48, 8 February 2006 (UTC)

Hmm, that not very many Google hits, but undeniably there are some people calling it the "choose function". So I agree with Fresheneesz that it should be mentioned. Because of its rare use, I didn't put it in the first line though.

Jon, a more collegial attitude would be much appreciated. The nice thing about collaboration is that everybody can contribute what they know. -- Jitse Niesen (talk) 17:07, 8 February 2006 (UTC)

Thanks Jitse, you saved me the work I was supposed to do. Oleg Alexandrov (talk) 17:44, 8 February 2006 (UTC)

• JA: That sounds real nice, Jitse. And, yes, a more collegial attitude would be appreciated. I'll be sure to quote you the next time somebody reverts a month's worth of my contributions based on a lack of what they've heard of. Jon Awbrey 17:50, 8 February 2006 (UTC)

I don't think that such a vague statement is appropriate, Jon. Whatever you may be referring to, it does not help in solving disputes. Oleg Alexandrov (talk) 20:55, 8 February 2006 (UTC)

Ok it looks great. Thanks you guys! Fresheneesz 21:12, 8 February 2006 (UTC)

Divisors of binomial coefficients

"A somewhat surprising result by David Singmaster (1974) is that any non-zero integer divides all but finitely many binomial coefficients." Gauge 'clarified' David Singmasters result about almost all to be all but finitely many. The number 1 occurs an infinite number of times in the pascal triangle, so he cannot mean that for only a finite number of pairs (n,k) is the binomial coefficient C(n,k) not divisible by the integer in consideration. What does almost all binomial coefficients mean? If that question cannot be answered the reference to David Singmaster's result must be omitted. Bo Jacoby 10:52, 9 March 2006 (UTC)

I hope my edit is a better clarification. For instance, the binomial coefficients that are odd form the Sierpinski triangle, which has area zero, so "almost all" binomial coefficients are even. -- Jitse Niesen (talk) 11:15, 9 March 2006 (UTC)

Jitse's clarification makes sense to me. Let's hope that it is also true. Thank you. Bo Jacoby 14:10, 9 March 2006 (UTC)

I inserted the original Singmaster reference, and Jitse's clarification makes sense to me also. Pgc512 20:12, 9 March 2006 (UTC)

Whoops. Sorry about that. I obviously didn't think that edit through; I'm glad that it's all cleared up now. - Gauge 05:07, 28 June 2006 (UTC)

1 to 37 numberscalled jueteng

How we can compute numbers involving 1 to 37 numbers

practical calculation of the binomial coefficient

((((5/1)×6)/2)×7)/3 is there any reason not to clean this up? E.g. (5/1)×(6/2)×(7/3). Am I missing something?

You won't get integer byproducts in this way, meaning that the calculation will be more difficult.195.113.31.79 18:15, 12 March 2007 (UTC)

yes, and round-off errors are introduced, because 7/3 cannot be represented exactly as a decimal fraction or as a dyadic fraction. Bo Jacoby 16:21, 15 March 2007 (UTC).

Formula syntax corrections

Many of the formulas do not display. Instead their TEX contents are shown. Now that I have made them human-readable through IE6, could someone verify these for accuracy? (I did not change the content -- only the syntax used to properly display content). Also, not being familiar with generating functions, could someone who knows something about these make them human-readable? Vonkje 23:00, 15 March 2007 (UTC)

Pizza

The article talks about pizza in the first sentence, then jumps into a formula. An encyclopedic summary lead is necessary if this article is to become GA. --Cronholm144 02:26, 22 May 2007 (UTC)

The pizza stuff is nice, but maybe better in the body rather than the lead? Geometry guy 20:19, 9 June 2007 (UTC)

First sentence

I see that the first sentence was changed to give the algebraic definition (coefficients in the binomial expansion) instead of the combinatorial one (number of ways to choose k objects out of n). No reason was given. I think the latter definition is more accessible and hence that one should be mentioned in the first sentence. -- Jitse Niesen (talk) 01:11, 28 August 2007 (UTC)

As the name 'binomial coefficient' relates to the concept of a binomial, it seems pedagogical to begin with the binomial expansion, even if the combinatorial interpretation is the more accessible. See Multiset#Polynomial_notation for a unification of the two approaches. Bo Jacoby 06:59, 28 August 2007 (UTC).

10:05, 3 November 2007 Lantonov (clean up using AWB)

What is the use of this 'cleanup'? The exponents 2 and 3 now have another style than other exponents, and they are harder to read. Bo Jacoby 16:13, 3 November 2007 (UTC).

Proofs

Many cases with a formula, I see statements like "Using (3) and induction, one can show that...," but may we actually see the proof written out, or at least have the proof be sourced? One thing about this article is that at least the online sources given do not provide proofs for a lot of the formulas present in this article and the article itself doesn't do it. Is it possible that either the proofs could be written in the article or links to online articles or resources be given showing the proofs?

I for one would really like to see proofs for (as of this revision) formulas (6) and (11) written out, as they don't have names and as such it is difficult to search the web for such proofs as resources discussing binomial coefficients don't always talk about everything.

Also, 2 formulas are labelled as (12). Cornince (talk) 23:25, 22 November 2007 (UTC)

Here's a good source here:

http://binomial.csueastbay.edu/Pascal1.html

http://binomial.csueastbay.edu/Identities.html

This mentions (5), which is called Pascal's 5th Identity, among others. Perhaps we can start inserting the names of at least some of the identities next to them? Cornince (talk) 00:48, 25 November 2007 (UTC)

Thanks for catching the double-labelling. The first (12) defines multinomial coefficients, so I moved it straight to that section and removed its label. My response to your comment on proofs is on your talk page.

Regarding the name issue, there are too many binomial identities for each one to have a name (and most of them are "trivial", in any case; see WZ theory for details, if the article is ever written). Only a few of them (Pascal's rule, the Vandermonde identity) really have names, and those are already named in the article. Michael Slone (talk) 08:44, 25 November 2007 (UTC)

C-code

The code of the article computes intermediate fractional numbers:

long double accum = 1;  for (int i = 0; i < k; ++i) accum = accum / (k-i) * (n-i);

It is better to use integer arithmetic all along such that for instance

choose(8,4) = ((((((5/1)*6)/2)*7)/3)*8)/4

Bo Jacoby (talk) 02:38, 21 January 2008 (UTC).

The intent was to provide simple code that avoids overflow (as the arguments get large) and works well in the typical desktop environment (which has fast floating-point hardware). Bo's algorithm, which might be worth mentioning as requiring only integer operations, seems more susceptible to overflow. — DAGwyn (talk) 00:06, 23 January 2008 (UTC)

While we're on the subject, a Pascal triangle based method would avoid all multiplication and division operations, using just addition, but is limited in many practical cases by recursion depth (as many levels as the larger of k or n-k). The double recursion could perhaps be changed to iteration, but then the bookkeeping would need an inordinate amount of storage. I wish I had my copy of Knuth's TAOCP vol. 1 nearby; I'm sure there must be bin.coef. algorithms in there. — DAGwyn (talk) 00:20, 23 January 2008 (UTC)

Just reverse the order of operations such that all intermediate results get exact integer values, even if stored in floating point format. ('i' is supposed to take values from 1 thru 'k'. Please check the code. I did not test it).

long double accum = 1;  for (int i = 1; i < k+1; ++i) accum = (accum * (n-k+i))/i;

Bo Jacoby (talk) 15:57, 23 January 2008 (UTC). PS. Hi DAGwyn. 'accum' means accumulator, which usually indicates a result of additions, not of multiplications and divisions. So the variable name 'accum' is not well chosen. Also there is no fear of overflow, so there is no reason for converting to floating point numbers for intermediate results and converting back to integer format. Try

long long t = 1;  for (int i = 1; i < k+1; ++i) t = (t*(n-k+i))/i;

I am not sure if integer division is called / or something else in C, so please improve, but the present code is not suited for publication. Bo Jacoby (talk) 08:46, 28 January 2008 (UTC).

It is an accumulator; the result is accumulated factor by factor. Think logarithmically if you have a need to tie it to addition. I appreciate improvements to the code, so long as they meet all the requirements (avoiding premature overflow, etc.) — DAGwyn (talk) 16:39, 15 February 2008 (UTC)

Also note that k+1 doesn't work if k and n havee the maximum representable value. — DAGwyn (talk) 17:14, 15 February 2008 (UTC)

[copied from User talk:DAGwyn] Hi, Doug. In the code you provide you use a long double to accumulate and you then mess with rounding error. If you rearranged your computation, you could make use of the fact that $n(n-1)...(n-m)$ is always divisible by $m!$ and be assured that your calculation will always remain integer. So "9 choose 3" would be computed $(((((9/1)*8)/2)*7)/3)$. Perhaps you chose to do your arithmetic in long double precision in case the value of "n choose m" will fit as an unsigned long long but the last multiplication would have overflowed before the last division had a chance to tame it? Similarly, do you do add the .5 because we're stuck with finite precision? Remember, I'm a theoretical computer scientist, so when I say integer I usually think the mathematician's meaning, not some element of {$-k,...,0,1,2,...,k$} for a very finite $k$. Regards... PaulTanenbaum (talk) 02:28, 15 February 2008 (UTC)

There were three reasons for my choice:

• to avoid unnecessary overflow such as you mentioned,
• to directly implement a formula exhibited earlier in the article, and
• to keep the code simple and transparent.

The +.5 is needed in any event when converting a (positive) floating-point representation to integer, since otherwise the approximate (or even exact) integer value could truncate downward by nearly 1; this is allowed by the C standard and actually occurs in practice (sometimes). For the code I originally presented, there are also accumulated rounding errors due to intermediate values that are not exactly representable in floating-point format, resulting from some of the divisions. See above suggestions for ways to ensure that all intermediate values are (theoretically) exact integers.

It is possible for a standard-conforming C implementation to have more significant bits in the representation of type "long long" than in type "long double", alas. It might be useful for a similar function to return type long double, considering that many applications involve floating-point anyway.

I'll consider revising the code, but whatever formula it directly implements will need to be established in the article text. — DAGwyn (talk) 16:39, 15 February 2008 (UTC)

Okay, the code has been revised to take into account the above discussion. — DAGwyn (talk) 17:14, 15 February 2008 (UTC)

Is this really correct:

if (n <= 0 || k < 0 || k > n)
    return 0;

This also means that:

if (n == 0)
    return 0;

Which seems wrong to me. Because, ${0 \choose 0}=1$. --Joctee (talk) 00:53, 16 February 2008 (UTC)

Thanks for pointing that out. I fixed it in the article. — DAGwyn (talk) 22:36, 27 March 2008 (UTC)

I came across a very elegant implementation on this page: http://blog.plover.com/math/choose.html

       unsigned choose(unsigned m, unsigned n) {
         unsigned r = 1;
         unsigned d;
         if (n > m) return 0;
         for (d=1; d <= n; d++) {
           r *= m--;
           r /= d;
         }
         return r;
       }

Advantages are that is clear to the layman (at least to me) and it actually works. —Preceding unsigned comment added by Kieckerjan (talk • contribs) 16:25, 20 February 2008 (UTC)

Unfortunately that can overflow, and when it does C's rules for unsigned arithmetic practically guarantee that you get a wrong answer, silently. The code that was in the article can "unnecessarily" overflow only when int and long long have the same width, which is quite unusual, and then only for numbers near the top of the representable range. I have just updated the code to remove even that possibility and to simplify it. — DAGwyn (talk) 22:36, 27 March 2008 (UTC)

I don't understand the considerations of "near the top of the representable range". As you should be aware, binomial coefficients grow quite large down Pascal's triangle, especially near the center. For instance ${\tbinom {68}{31}}=21912870037044995008$, which cannot be stored in an unsigned 64-bit integer, while 68 is not near the top of the representable range in any sense. So none of the functions considered could return such a value. Quality code should explicitly test for overflow on all possible occasions. The context where computing binomial coefficients by a procedure make sense seem to be limited to

• all floating-point computations (for statistical applications for instance), or
• all unlimited-size integer computations (for symbolic algebra for instance).

In both cases it is best to develop numerator and denominator in an interleaved fashion. When only those coefficients that certainly will not overflow machine integers are needed (in other words very few of them) using a precomputed (additively) table should be best. Marc van Leeuwen (talk) 15:10, 9 June 2008 (UTC)

The code as it exists doesn't work correctly for large numbers. I don't see how this code, then, is any better than all the rest mentioned here that also don't work correctly. As an example, Choose(100,80) returns 9223372036854775808, but the correct answer is 535983370403809682970. That's a 98% error. 72.175.133.227 (talk) 19:15, 2 October 2008 (UTC)

A lot of the discussions above is about overflows but there are solutions for that, for example in F#:

 #light
 open Microsoft.FSharp.Math
 let rec accum (n :BigInt) (k :BigInt) =
   match k with
   | 0I -> 1I
   | _ -> ((n - k + 1I) * accum n (k-1I)) / k
 let rec choose (n :BigInt) (k :BigInt) =
   match k with
       | k when (k > n) -> 0I
       | k when (k > n/2I) -> choose n (n-k) 
       | _ -> accum n k

In this case, an overflow will never happen because BigInt can handle arbitrarily long integers. For example

 choose 100I 80I;;

gives as result:

 val it : bigint = 535983370403809682970I

As user 72.175.133.227 describes. If you agree, I can put this in the main article. Xenan (talk) 20:51, 8 February 2009 (UTC)

Suggestions for improvement

I've only just come across this article, and I see that it has a long history, so I hesitate to correct without discussion things I think can be improved. Here is what I think needs changing, in order of importance

• The section Binomial coefficient#Generalization to negative integers given an extension to values $k<0$ that is completely unmotivated and conflicts with conventional use. Convention is that binomial coefficients are identically 0 when the second coefficient is a negative integer (see equation (5.1) in (Graham, Knuth, Patashnik; 1989), which book is extremely careful about validity of identities for non-natural number parameters. The given formula (actually two overlapping formulas for the cases $k\leq n<0$ which fortunately coincide there) seems to be inspired by aesthetics only: the pattern around the origin looks pretty, but fails Pascal's identity ${\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}={\tbinom {n}{k}}$ exactly at the origin (in spite of its obvious aesthetic qualities, the equation $1+1=1$ is false), which I consider particularly insidious. In my opinion there should at most be a side remark that this is a possible definition, explaining that this preserves equation (4) (by design), but also explaining all the things that are broken by it.

• Under Binomial coefficient#Definition, the first sentence "the binomial coefficient is defined to be the natural number ..." is followed by the symbol for the binomial coefficient and two different formulas. In my opinion this should be "the binomial coefficient, written ${\tbinom {n}{k}}$ is defined as the coefficient of x^ky^n−k in the expansion of the polynomial $(x+y)^{n}$. This number can be seen to be the number of distinct k-element subsets of some n-element set, and can be computed by the formulas ...". It could also be the coefficient of x^k in $(1+x)^{n}$, or one could take the combinatorial description as first definition, that is not my point here; the point is that is seems silly that binomial coefficients should be defined by two different complicated formulas; nobody would care about such expressions if they did not have a combinatorial/algebraic interpretation. These formulas are only convenient for computing binomial coefficients, they belong to implementation, not specification, in computer science speak.

• The article postpones an extension of binomial coefficients to non-natural number parameters, which is good in view of the increasing level of complication. However, I think that one could indicate that such an extension exists, and already tag identities with conditions on the (extended) parameters for their validity, so that readers have a way to know about this. For instance equation (4) (${\tbinom {n}{k}}={\tbinom {n}{n-k}}$) could be tagged "integer $n\geq 0$, integer k", since it fails (while at least one member is still defined) when n is not a positive integer. One might omit the condition "integer k" since it is required for either member to be defined, given the condition on n. The cited book (Graham, Knuth, Patashnik; 1989) meticulously provides such tags, which is quite valuable in practice (and it makes it easy to tag the equations in this article).

• The section Binomial coefficient#Generalization to real and complex argument gives the usual extension to arbitrary first parameter (it could also proclaim the convention that negative integer second parameter makes the binomial coefficient identically zero, so that ${\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}={\tbinom {n}{k}}$ makes sense (and holds) everywhere). However I find the reference to real and complex numbers laughable, even though I know many authors make it. This has nothing to do with properties of real or complex numbers (the latter apparently being considered the summum of sophistication), it can also be used for any polynomial in Q[X], or for any quaternion for that matter (the expressions can always be evaluated in a commutative subring). So in fact, not only is "$f(z)=\textstyle {z \choose k}$ is a polynomial (function) in z of degree k with rational coefficients", it is actually true that that ${\tbinom {X}{k}}$ is a polynomial (of degree k if $k\geq 0$), in Q[X]. The point of the generalisation is that the first parameter can be treated as formal symbol, and all that matters is that multiplication and division by nonzero integers is defined (whence one cannot work in Z/pZ or Z[X]). If one really wants the general setting where the definition makes sense, I would say any Q-algebra. On the other hand the cases where I have seen practical uses of non-integer numerical values of the first parameter are limited to rational values.

Marc van Leeuwen (talk) 14:37, 9 June 2008 (UTC)

Are you sure that the definition in Graham et al. is the conventional one? Maple (software) uses the definition in the article. I remember though I was rather surprised when I discovered this for the same reason as you (it fails Pascal's identity).

I agree with point 3, though I'm not so sure that it is that useful if there is no agreement on how to define the binomial coefficients for negative k. I also agree with point 2, and I simply do not know about point 4. -- Jitse Niesen (talk) 15:50, 9 June 2008 (UTC)

I agree with Marc. The definition of the binomial coefficient ${\tbinom {n}{k}}$ should be that

$(1+x)^{n}=\sum _{k=0}^{\infty }{\tbinom {n}{k}}\cdot x^{k}.$

From this it follows that ${\tbinom {n}{k}}$ = 0 when k is negative or noninteger, and that ${\tbinom {n}{0}}$ = 1. Substituting into

$(1+x)^{n}=(1+x)^{n-1}+x\cdot (1+x)^{n-1}$

gives right away the additive recursion formula

${\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}.$

Substituting into the derivative of the definition

$n\cdot (1+x)^{n-1}=\sum _{k=1}^{\infty }k\cdot {\tbinom {n}{k}}\cdot x^{k-1}$

gives the multiplicative recursion formula

$n\cdot {\tbinom {n-1}{k-1}}=k\cdot {\tbinom {n}{k}}.$

Bo Jacoby (talk) 09:12, 14 August 2008 (UTC).

No, nothing about the values ${\binom {n}{k}}$ for negative k can be inferred from $(1+x)^{n}=\sum _{k=0}^{\infty }{\tbinom {n}{k}}\cdot x^{k}$. ;) But I understand what you mean - it is much better to have $(1+x)^{n}=\sum _{k\in \mathbb {Z} }{\tbinom {n}{k}}\cdot x^{k}$, because this allows us to do substitutions such as $k\mapsto a-k$ without caring for bounds. This is one of the reasons I prefer the "all-zero" convention for binomial coefficients ${\tbinom {n}{k}}$ with $k<0$. Another reason is, of course, the recurrence equation; in my opinion, it is one of the most important properties of binomial coefficients, more important than the symmetry of Pascal's triangle (for instance), so one should think twice before breaking it. Yet another reason is Vandermonde's convolution identity: neither ${\binom {n+m}{u}}=\sum _{k\in \mathbb {Z} }{\binom {n}{k}}{\binom {m}{u-k}}$ nor ${\binom {n+m}{u}}=\sum _{k\geq 0}{\binom {n}{k}}{\binom {m}{u-k}}$ would hold if we define binomial coefficients such as currently done in the article (that is, by ${n \choose k}={\begin{cases}(-1)^{n-k}{-k-1 \choose n-k}\quad {\mbox{if }}n\geq k,\\(-1)^{n-k}{-k-1 \choose -n-1}\quad {\mbox{if }}n\leq -1.\end{cases}}$) - instead, both sums would make no sense (they would be infinite sums with infinitely many nonzero integer terms). How would one formulate Vandermonde's convolution then? Of course, for nonnegative u, one could write ${\binom {n+m}{u}}=\sum _{k=0}^{u}{\binom {n}{k}}{\binom {m}{u-k}}$, but what should we do with our "big" negative u which make ${\binom {n+m}{u}}$ nonzero? A symmetric Pascal's hexagon (or windmill, or radiation sign, or whatever - none of these notions yields any reasonable matches in Google besides this not particularly serious HTML article) is fun to look at, but without Vandermonde and similar identities, one is pretty much 0wn3d when it comes to proving things. Computer algebra systems such as Maple are known for their, let's say, liberal handling of mathematical notation; I don't think we should base our definitions entirely on them. The only thing that currently keeps me from editing the article and putting the "${n \choose k}=0$ for all $k<0$, regardless of n" convention into the article is a lack of authoritative sources that use this notation (namely, the only one I can find is Graham/Knuth/Patashnik, which was already mentioned above) - but this doesn't mean I have ever seen a serious source advocating the other convention. Apparently, most combinatorics texts don't use binomial coefficients with negative k at all, or at least weasel around the definition. Darij (talk) 20:55, 29 April 2009 (UTC)

I wanted to voice my support for the four changes proposed by Mark van Leeuwen; they should have been implemented long ago.

1) Graham, Knuth, Patashnik is a reliable reference (it would be hard to imagine a more reliable one) for the fact that ${\binom {n}{k}}$ should be 0 when k is negative. As Mark states, many things would break under any other definition. In addition, if one defines the binomial coefficient for two complex arguments in terms of gamma functions, as a meromorphic function, then if k is a negative integer, then on any line approaching (n,k) on which the function is not everywhere undefined, the limit as one approaches (n,k) is 0.

2) In Binomial coefficient#Definition, the first definition of binomial coefficient should be as the coefficient of (1+x)^n or (x+y)^n, or possibly as the number of k-element subsets of an n-element set. The factorial formula and descending product formula should be consequences: as Mark says, no one would care about them if it were not for the simple interpretations of what they are computing. (Happily, the lede is following this approach already, but why should the definition in the body of the article do anything different?)

3) and 4) Here is a suggestion for a clean way to implement his last two suggestions. Before the identities section, add a section "Binomial coefficients as polynomials" in which ${\binom {t}{k}}$ is introduced as a polynomial in t with rational coefficients. (Such a section could also mention in passing that every integer-valued polynomial is an integer linear combination of these.) Then at the top of the identities section, say that n and k are nonnegative integers, and that formulas involving t are to be interpreted as polynomial identities in Q[t]. Then simply replace n by t in the identities that can be interpreted this way.

Ebony Jackson (talk) 07:00, 11 August 2009 (UTC)

I just implemented the 4th suggestion, but have not yet updated the identities section to reflect this (which to me is one of the main purposes for rewriting things in this way). There is probably also some further editing needed in the generalizations section to clean things up. Ebony Jackson (talk) 20:10, 17 August 2009 (UTC)

stirling numbers

The formulas involving stirling numbers contain an undefined z₀. So the formulas are incomprehensible and should be clarified or removed. Bo Jacoby (talk) 04:11, 15 March 2009 (UTC).

Continuous identities

Can someone provide a reference to a reputable source containing the derivations in the "continuous identities" section and explaining why they are notable enough to merit spending so much space on them? (The first person to add this material wrote that it was "possibly useless but interesting", which makes me wonder whether it is original research.) Ebony Jackson (talk) 22:51, 12 August 2009 (UTC)

If there was a reference, then there would be no need to derive them here. You might argue that these identities are "original research" by wikipedia's standards, but the mathematical tools used to arrive at these conclusions are well documented here and elsewhere. These mainly include the binomial theorem and the orthogonal basis. The identities may appear in an integral problem, differential equations, Fourier analysis but are ultimately of no use to anyone who simply wish to apply the binomial theorem. Then again, most of the specialized material in this article is arguably useless to the casual reader anyways. Even so, amidst an article that largely defines and describes the binomial coefficient as a discrete object, it sure is neat that you can arrive at them through integration. If you feel that a reader with advanced mathematical knowledge cannot easily understand and verify the derivation, that it serves no practical use for this audience, or that it is a violation of wikipedia's no-original-research policy, then I invite you to remove the section entirely. —Preceding unsigned comment added by 69.244.210.117 (talk) 03:41, 13 August 2009 (UTC)

If it helps, I added lots of links to the well documented and understood mathematical tools that were used in the derivation. Other than that, the closest you'll get to what's written is a reference from CRC on these integrals

$\int _{0}^{\frac {\pi }{2}}\cos ^{n}x\ dx$

$\int _{0}^{\frac {\pi }{2}}\sin ^{n}x\ dx$

Though I can't remember exactly what they give (some double factorial expression). They're not nearly as interesting as what was derived here. Though, the derivations here are actually very plain. They wouldn't constitute as "original" in academia other than possibly the bizarre use of the Fourier basis. —Preceding unsigned comment added by 69.244.210.117 (talk) 05:09, 13 August 2009 (UTC)

Dear 69.244.210.117,

The calculation is straightforward; converting trigonometric functions to complex exponentials to evaluate such integrals is not "bizarre" at all. I agree with you fully that the techniques are well known. In fact, your two integrals from CRC are susceptible to the same method and give an answer expressible in terms of binomial coefficients for even n.

What I was actually questioning was whether there was a reference to show that these identities are of sufficient interest to merit devoting a few screenfuls to, or at least a few sentences to, in Wikipedia. You write

"If there was a reference, then there would be no need to derive them here"

but this runs contrary to the goals of Wikipedia: it is not to serve as a forum for presenting calculations that someone has worked out and considers to be neat (that is what I meant by "original research"), but rather to document what reputable sources consider to be worth saying about the topic at hand.

Perhaps you could consider creating your own blog at wordpress.com and publishing your calculations there instead? Best wishes, Ebony Jackson (talk) 20:51, 13 August 2009 (UTC)

Wikipedia is clear about subjective conclusions about subjective material and naturally requires citation from reputable sources, but its article on "verification" is vague when it comes to objective systems like those of logic and mathematics. It obviously permits the use of these without citation to some unknown extent. Though, I can understand that applying concepts like "orthogonality" can fall out of the scope of what is vaguely permitted. Sufficient interest? There are portions written in this article dedicated to the binomial coefficient generalized to negative integers, real, and complex arguments. Indeed there is literature covering these topics, but from what I can tell, its not often encountered in practice. Most people who read this article will only really care to use the binomial coefficient with the binomial theorem itself. This essentially renders many portions of this article as a curiosity as opposed to what is really practical. But you are right, if its to do with continuous topics like integrals, differential equations, or Fourier analysis, nobody would naturally think to look here. —Preceding unsigned comment added by 144.174.6.42 (talk) 22:26, 13 August 2009 (UTC)

OK. In response to one of your remarks: I do feel that the literature shows that binomial coefficients with non-integer arguments are more than just a curiosity. They appear in the binomial series for (1+x)^{1/2}, for example, which is important when one wants to obtain a polynomial approximation to square roots, as is required often in science. Even binomial coefficients with indeterminate upper arguments arise: they give a Z-basis for the integer-valued polynomials, which is important when studying Hilbert series in algebraic geometry (see Hartshorne's book, for instance). And in higher mathematics one shows that every p-adic continuous function on Z_p can be expressed as an infinite linear combination of these polynomial binomial coefficients (Mahler expansion), and so on. --Ebony Jackson (talk) 23:16, 13 August 2009 (UTC)

Well, you've certainly got me on algebraic geometry. I envy your knowledge in pure mathematics. As for approximating square roots as a polynomial, surely a scientist would use Taylor series or an interpolation scheme (if its over a specific domain). Though, the Taylor series could become the binomial series without the scientist necessarily realizing. I tried to remove the section from the points mentioned earlier but it has found itself back in the article. And I do consider using the Fourier basis to extract an integral definition of the binomial coefficient as a bit "bizarre." This is in contrast to using them to simplify evaluating trigonometric integrals. Thanks for the book references. Take care. —Preceding unsigned comment added by 69.244.210.117 (talk) 04:32, 14 August 2009 (UTC)

It's strange that the person who reinstated the removed material did so without giving any reason, and labelled it a "minor edit"! Hopefully that person will explain his or her reasoning. Anyway, based on our discussion above, let me as a compromise suggest that we keep your identities, but replace the detailed proofs by a sentence or two, to be in line with what is done with the other identities. --Ebony Jackson (talk) 08:09, 14 August 2009 (UTC)

I think thats a fair compromise. Although you are right to question its significance in the academic community and I did anticipate this. Its presence here should not go in vain as I added generalized versions of these integrals to table of integrals and links that refer back to this article. So long as the content presented here is within Wikipedia's policies ... Now I'm really curious about using these integrals to form "power" Fourier series. Like ones of the form:

${\begin{aligned}f(x)&=\sum _{k=0}^{\infty }a_{k}\sin ^{k}x+b_{k}\cos ^{k}x\\f(x)&=\sum _{k=0}^{\infty }a_{k}\sin ^{n}(kx)+b_{k}\cos ^{m}(kx)\\\end{aligned}}$

Maybe approximations of these series will behave better with discontinuities. I've also been looking at the binomial series as a means to generalize the integrals to $\textstyle m,n\in \mathbb {R}$ but the binomial series convergence criteria does not permit it. Wolfram describes the Binomial Identity so there may be a $\textstyle p_{n}(x)\neq x^{n}$ where another basis function can be used to extract a generalized binomial coefficient. In its prototypical form, only the Fourier basis can be used.

And ultimately, I'm really curious if an efficient and accurate quadrature can be used to approximate these integrals. None of the Gauss Quadratures work very well since both the $\textstyle 2^{n}$ factor and high order derivatives of the integrand dominate even Chebyshev-Gauss Qaudrature's asymptotic error $\textstyle O\left({\frac {2\pi }{2^{2n}(2n)!}}f^{(2n)}(\xi )\right)$. But some Newton-Cotes formulas are extremely accurate or exact on periodic functions.

But don't worry, I won't post these results on wikipedia ... —Preceding unsigned comment added by 144.174.6.42 (talk) 21:20, 14 August 2009 (UTC)

Greatest coefficient

shouldn't we have a derivation of the formula(e) that find the greatest coefficient? —Preceding unsigned comment added by Welcome to the dark side. (talk • contribs) 04:55, 17 August 2009 (UTC)

Do you mean the largest binomial coefficient in each row of Pascal's triangle? The formula for the ratio of two successive binomial coefficients in a row immediately implies that the largest one is in the middle (or just on either side of the middle if n is odd), but I'm not sure if this deserves a special mention. Best, Ebony Jackson (talk) 06:35, 17 August 2009 (UTC)

Dubious

Where that statement is, don't they mean "the latter"? Wouldn't be nice if they could actually link to a source that states that these identities are true and gives an actual proof of it? Because especially where that k^2 is, I have been unable to find a proof of that written on the Internet, only vague statements to it. 199.191.74.20 (talk) 20:24, 28 October 2009 (UTC)

Here is a proof: $\sum _{k=1}^{n}k^{2}{\binom {n}{k}}$ $=\sum _{k=1}^{n}(k(k-1)+k){\binom {n}{k}}$ $=\sum _{k=1}^{n}k(k-1){\binom {n}{k}}+\sum _{k=1}^{n}k{\binom {n}{k}}$ $=\sum _{k=2}^{n}k(k-1){\binom {n}{k}}+\sum _{k=1}^{n}k{\binom {n}{k}}$ $=\sum _{k=2}^{n}n(n-1){\binom {n-2}{k-2}}+\sum _{k=1}^{n}n{\binom {n-1}{k-1}}$ $=n(n-1)\sum _{k=2}^{n}{\binom {n-2}{k-2}}+n\sum _{k=1}^{n}{\binom {n-1}{k-1}}$ $=n(n-1)\sum _{k=0}^{n-2}{\binom {n-2}{k}}+n\sum _{k=0}^{n-1}{\binom {n-1}{k}}$ $=n(n-1)2^{n-2}+n2^{n-1}\,$ $=(n+n^{2})2^{n-2}\,$ Q.E.D.

Bo Jacoby (talk) 01:08, 29 October 2009 (UTC).

It is indeed the latter, so have changed the wording. Cornince (talk) 05:28, 30 October 2009 (UTC)

Equation 13c

Where is the proof for 13c? 199.191.74.20 (talk) 15:11, 30 October 2009 (UTC)

I've added a short explanation (though I still wonder what's the use of this formula there). If you need further clarification for this or other points, remember that it's quicker to ask the Wikipedia:Reference desk/Mathematics. --pma (talk) 23:11, 9 November 2009 (UTC)

defined/undefined

There is a tradition in the history of this article, about the binomial coefficients not being defined for k>n and k<0. The first limitation is certainly not justified; for k>n the binomial(n,k) is perfectly well defined, and 0, both in the combinatorial and in the polymonial coefficient definition. Every source agree on this, of course. As for k<0 I agree with what Darij said above; the most natural choice would be 0, a good reason being the recursive formula and another good reason being the form the binomial coefficients appear in discrete (Vandermonde) convolution as Darij observes (though, as to the latter it should be said that there exists an obvious notion of one-side convolution of sequences, corresponding precisely to the Cauchy product of power series, that does not require a sequence to be defined for k<0, so after all one could just do not consider the case k<0). In any case, writing that the binomial coefficient "is defined as

${n \choose k}=Undefined\quad {\mbox{if }}k<0{\mbox{ or }}k>n,$ "

is a bit ridiculous (then why not to remark that "it's undefined aldso if k is a hen or if k is my uncle Mario" ). --pma (talk) 13:29, 21 November 2009 (UTC)

C_n^k or C^n_k ?

A recent change of C^n_k to C_n^k as alternative notation for binomial coefficients was undone with the comment "in English literature, it's C^n_k not C_n^k". I have never seen either of these notations in the English literature; as far as I know it is a typically French convention and (t)here it is definitely C_n^k (you can check on the French equivalent of this article, or search Google for C^n_k and C_n^k to check these claims). So unless there is definite evidence that C^n_k is used (more than marginally) in English literature, I think it should mention (only) C_n^k, with a comment that this is mostly in French texts; For now I'll put in a "citation needed" tag. Marc van Leeuwen (talk) 08:04, 1 December 2009 (UTC)

C^n_k was standard in textbooks and exams when I was taught at school (Australia, 1990s). I will find a recent textbook and cite it. Xanthoxyl ^< 11:18, 1 December 2009 (UTC)

A southern hemisphere convention, isn't it? :-) pma (talk) 12:37, 1 December 2009 (UTC)

Not quite, it is popular in North America as well. Here is an example that may be used for citation. Maxal (talk) 22:08, 1 December 2009 (UTC)

Another example. Maxal (talk) 22:16, 1 December 2009 (UTC)

OK, I'm convinced. By the way here is an amusing other example, of the C_n^k convention this time, on a Korean postage stamp, although the accompanying text says it is both historically and notationally incorrect. Still I think the article might warn readers that the position of the indices are opposite in the French literature, in particular since one is far more likely to come across the notation there, where it appears to be much slower to be replaced with the (much better) notation ${\tbinom {n}{k}}$ (where fortunately the positioning of the indices seems to be universally agreed upon). Marc van Leeuwen (talk) 15:34, 2 December 2009 (UTC)

Maybe simply include both C_n^k and C^n_k notations? Btw, there is also yet another popular notation ${}^{n}C_{k}$ - for example. Maxal (talk) 16:56, 2 December 2009 (UTC)

Hey! Readers need the most common used variant of $\scriptstyle C_{k}^{n}$ and $\scriptstyle C_{n}^{k}$. Please, add description to the all versions. `a5b (talk) 18:15, 21 December 2009 (UTC)

Newton's gravestone

The statement, "The formula for the binomial series was etched onto Newton's gravestone in Westminster Abbey in 1727", is contradicted at http://en.wikipedia.org/wiki/Binomial_theorem#The_binomial_theorem_in_popular_culture —Preceding unsigned comment added by 129.89.14.247 (talk) 21:19, 28 December 2009 (UTC)

Equation numbering

Someone should go through the article and fix the equation numbering. There's no equation (1) or (2), yet equation (2) is referred to in some sections. Also, there's an equation (3.5), apparently inserted between (3) and (4). It just makes the article look unpolished. —Preceding unsigned comment added by 75.51.164.205 (talk) 23:50, 13 June 2010 (UTC)

Exponential generating functions

This section needs a reference to the book/article where D. Knuth justifies his choice of bracket notation for Stirling numbers by analogy with binomial coefficients. If no such reference can be found, the section should probably removed. -Zahlentheorie (talk) 12:56, 8 July 2010 (UTC)

Questions re new image

Hi guys. I still have some questions about the new image of the 1000th row. Here they are in order of increasing importance:

1.I think the caption should say, beside the word grayscale, "darkest =9, lightest =0" or vice versa.

2.Which digit is right justified -- the last digit in the number, or the first? Maybe you could say "with the last digit of the coefficient right aligned".

3.The image gives me the impression that log(combinations of 1000 things k at a time) is approximately a semi-circular function of k -- something like log²(combinations of 1000 things k at a time) + (k-500)^2 = 500^2.</math> Is that intended?

4.Is this graph (or its implication about the semi-circle) WP:Original Research? If it hasn't been vetted by a refereed journal, I wonder whether it should be here. Thoughts? Duoduoduo (talk) 15:19, 13 March 2011 (UTC)

To answer in the same order

1. The caption could say that, but it is already pretty long, and this is fairly obvious, as the initial and final coefficients are 0000...001, and the first and last lines are almost entirely white.
2. I'd say right alignment (or right-justification) of strings or lines is by definition on their rightmost character or symbol, which I guess in western scripts is also called the last one. In case of decimal integers it is also the least significant digit, and the most natural one to align numbers on.
3. The image does not intend anything, it is just a list of binomial coefficients represented graphically. If one would just write down those coefficients in decimal notation aligned on their rightmost digit, the result would look similar, from sufficiently far away. I doubt that the graph of the logarithm of binomial coefficients really looks like that of a circle, but it certainly is a concave function, since binomial coefficients are known to be log concave.
4. I don't see how a refereed journal could possibly accept a mere graph for publication. If you can prove that this graph is semi-circular, and if nobody else has done so before, then you could try to publish that in a refereed journal. Not on Wikipedia, since that would be Original Research on your part.

Hope this helps. Marc van Leeuwen (talk) 20:40, 13 March 2011 (UTC)

Okay, have it your way. But when you restored the graph you said it's interesting. I fail to see what's interesting, insightful, or informative about it, unless the seeming semicircular feature is supposed to be interesting. Since you say it's not known to be semicircular, I don't see the point of it. Duoduoduo (talk) 22:30, 13 March 2011 (UTC)

Most illustrations serve just to make a page more attractive, and maybe to transmit certain information that is harder to express in words. In this case I'm pretty sure the log-concavity of binomial coefficients is pretty well conveyed by this image, even to people who have no idea what log-concavity is. I'll add a word to the caption about this anyway. Just for the record, the image is not mine, I just found this image quite interesting once I found out what it was. Marc van Leeuwen (talk) 09:11, 14 March 2011 (UTC)

An application of the Central limit theorem to the Bernoulli process would seem to imply that the binomial coefficients are log parabolic, not log semi-circular. Of course, the central limit theorem breaks down on the tails of the distribution, which is where the difference between a parabola and a circle are most evident, so maybe I've added zero to this conversation.  :-) —Quantling (talk | contribs) 19:39, 14 March 2011 (UTC)

There is no need for such a blunt instrument as the central limit theorem, as the ratio between successive binomial coefficients is perfectly easy to calculate. The slope of the logarithm of the coefficient at ${\tbinom {n}{k}}$ is about $\log(n-k-{\tfrac {1}{2}})-\log(k+{\tfrac {1}{2}})$, which is a rather flat (around k = n/2) but not a linear function. So the graph is not a parabola, and not a circle segment either. Marc van Leeuwen (talk) 16:10, 15 March 2011 (UTC)

multisection identity

There are literally thousands of identities involving binomial coefficients, so we have to be choosy. I think the multisection identity does not make the grade. If anyone else agrees, please remove it. McKay (talk) 06:27, 2 August 2011 (UTC)

I do not understand this argument. The multisection identity is quite general to be mentioned in Wikipedia, and itself can generate "thousands of identities" such as

$\sum _{k=0}^{n}{\binom {3n}{3k}}={\frac {8^{n}+2\cdot (-1)^{n}}{3}}.$

Maxal (talk) 15:16, 3 August 2011 (UTC)

Comment on readability

I came to this article hoping for a clear explanation of binomial coefficients and how they work. Sadly, I was disappointed to encounter a wall of equations, impenetrable to any non-mathematicians. Compare with {http://www.mathsisfun.com/combinatorics/combinations-permutations.html} or {http://www.themathpage.com/aprecalc/permutations-combinations.htm} where one finds fairly clear cut explanations. Editors of this page might like to consider that this is an encyclopaedia and things need to be explained clearly for non-specialists. I would also point out that phrases such as Finally there is a formula using factorials that is easy to remember: represent a point of view, and should be rewritten more neutrally. Jezhotwells (talk) 10:21, 6 December 2011 (UTC)

Incorrect python code (bug)

The optimized python code contains a bug. With python 2.7.2 for example binomialCoefficient(2,1) returns 1 when it should be 2. This is confirmed with the slow recursive version above it, that returns 2 correctly. In fact, I believe it is incorrect for all even n. — Preceding unsigned comment added by 109.65.31.224 (talk) 13:02, 16 December 2011 (UTC)