Talk:Binomial coefficient

Multiplicative formula

Made an edit from (n-(k-1)) to (n-(k+1)) which should be the correct falling factorial. If I'm wrong revert me please. 2601:640:4100:4C70:81FA:2C7B:8F13:A0D4 (talk) 22:17, 5 September 2019 (UTC)

You're wrong so I have reverted you. Maybe you missed that n-(k-1) = n-k+1. PrimeHunter (talk) 23:29, 5 September 2019 (UTC)

Doh, completely spaced. It just felt weird at first glance. Thanks. 2601:640:4100:4C70:81FA:2C7B:8F13:A0D4 (talk) 00:42, 6 September 2019 (UTC)

Binomial Coefficient definition should precede discussion of Binomial Theorem and Pascal's Triangle

The definition of the binomial coefficient in terms of what it means numerically should precede discussion of binomial theorem. Reader quite possibly may only want to know what it means and have no interest in binomial theorem or Pascal Triangle.RHB100 (talk) 21:31, 11 August 2012 (UTC)

This is not a difficult article to navigate: a person interested in formulas for binomial coefficients need only look at the table of contents for the well-labeled sections with the word "formula" in their titles. Please see Wikipedia:Manual of Style/Lead section to read about what a lead section is supposed to accomplish; notably, "The lead should be able to stand alone as a concise overview. It should define the topic, establish context, explain why the topic is notable, and summarize the most important points." Your sentence is detrimental to almost all of these goals, and distracts emphasis from the important definitions to less-important formulas. --JBL (talk) 02:24, 11 August 2012 (UTC)

The article at present is either deliberately designed to confuse readers or it is so poorly written that it confuses the reader as much as if it had been deliberate. The statement above implying that the definition of the binomial coefficient , ${\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\mbox{for }}\ 0\leq k\leq n$, where the notation, $n!$, called n factorial is defined by $n!=n(n-1)(n-2)...1$ with $0!=1$, is of less importance than Pascal's triangle and such is a very ignorant and stupid statement. RHB100 (talk) 21:31, 11 August 2012 (UTC)

Go have a read of WP:Civility and perhaps we can talk. It seems to me possible that a formula (or a pointer to the section on formulas) could be worked into the introduction somewhere, but you're very much going about it the wrong way. --JBL (talk) 18:11, 13 August 2012 (UTC)

I fully agree with that —specially about the civility issue. The factorial expression could i.m.o. be easily incorporated in the lead — not the way RHB100 has in mind though, as that would indeed be 100% orthogonal to Wikipedia:Manual of Style/Lead section. I have made an attempt at doing so. I think this can work. - DVdm (talk) 18:43, 13 August 2012 (UTC)

OK, I think it is somewhat better now. However, I think it should be kept in mind that some people may not be familiar with the factorial operator. Therefore I think a definition of the factorial operator for the simplest case of positive integers and zero before getting into the more advanced part of the article would be desirable. RHB100 (talk) 19:15, 13 August 2012 (UTC)

Mentioning factorials would i.m.o. clutter up the lead. The reader is explicitly pointed to factorials in all their glory in the section Binomial coefficient#Factorial formula. Remember the guidelines about the lead: the keywords to go with are concise overview and summarize. - DVdm (talk) 20:00, 13 August 2012 (UTC)

I think the current phrasing (while obviously better than the original) is somewhat cluttered -- that sentence is now doing an awful lot of work. Better would be to make it its own sentence (a little later in the paragraph). In fact, though, I think it would be even better to replace the formula with a sentence like the following: "There are several simple formulas (both recursive and explicit) for computing binomial coefficients -- see the section below for details." This serves the purpose of mentioning and pointing to the formulas without cluttering the lead or detracting from the more important definitions (namely, that these are the coefficients that appear in the binomial theorem, and their combinatorial interpretation). --JBL (talk) 20:09, 13 August 2012 (UTC)

Hm, I wouldn't opt for a see-below-like-kind-of-easteregg like you suggested. But yes, I see your point. Indeed, the sentence is doing too much work now, so I have moved the calculation into its own sentence — let's have the work done by two sentences, right? There are indeed several simple formulas, but I dare assume, so to speak, that we can all agree that the factorial expression is the most common and most notable... so how about this? - DVdm (talk) 21:29, 13 August 2012 (UTC)

Would you object to replacing "Under suitable circumstances" with "When n and k are nonnegative integers"? Should there be a remark about the fact that they can be defined more generally? Or is this too much for the lead? Edit: ok, the remark about generalizing comes later, is fine there, and shouldn't be repeated. The first question stands. --JBL (talk) 21:43, 13 August 2012 (UTC)

Re the first question: I wouldn't mind —provided n-k is required to be a nonnegint as well, which would add slightly more clutter again— but I don't think we really need that in this lead. - DVdm (talk) 22:05, 13 August 2012 (UTC)

Good point. --JBL (talk) 22:06, 13 August 2012 (UTC)

(In english please. It's hard to know what is just jibber jabber and what is solid useful math language!)

Pronunciation?

How is ${\binom {n}{k}}$ usually pronounced? Shouldn't this be in the article? 84.29.139.151 (talk) 09:43, 9 June 2014 (UTC)

Try reading the second paragraph of the lead section ;). JBL (talk) 13:19, 9 June 2014 (UTC)

Since this part of the text has changed since the above comment was written 7 years ago, I'll quote the relevant sentence from that point in time: ${\tbinom {n}{k}}$ is often read as "n choose k". 194.39.218.10 (talk) 13:45, 2 July 2021 (UTC)

I've added this sentence back to the main article. 194.39.218.10 (talk) 13:58, 2 July 2021 (UTC)

You are mistaken that it has changed -- I mean, perhaps the location is different now than it was, but it's still in the lead, following "The binomial coefficients occur in many areas of mathematics, and especially in combinatorics." So I have reverted your redundant addition. --JBL (talk) 14:10, 2 July 2021 (UTC)

Another identity

You have (under 'Identities involving binomial coefficients') everything but the basis for the recursive formula that appears in 'Computing the value of binomial coefficients':

nCk = (n-1)C(k-1) + (n-1)Ck

when I copy/paste I get: \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \text{for all integers }n,k : 1\le k\le n-1

The second identity down is similar looking, but the recursive formula seems more direct.

It just seems like the 'recursive identity' should be included. 71.139.161.9 (talk) 05:12, 28 August 2014 (UTC)

Equation numbering

Although I approve of equation numbering (as found in this article) and certainly use it in my own publications, I am finding it a hinderance to editing this article. I am considering numbering an equation early in the article which doesn't have a number now. This will require a wholesale renumbering of all the equations below it and their reference tags. Unwillingness to do this may explain why a blatant but minor error has not been corrected for years. When I do this I will remove all equation numbers that are not referred to (I know that many authors put them in, "just in case", they need to refer to the equations, or for the possibility that they might want to do this in the future ... but it creates more work for editors) and I will move to a numbering within section scheme (equations numbered 2.1, 2.2, ..., 2.k in section 2 and 3.1, 3.2 ... in section 3, and this can be extended to subsections as well). This will mean that fewer changes are needed when additions and deletions are made to numbered equations. Comments? Bill Cherowitzo (talk) 06:55, 4 December 2014 (UTC)

I certainly approve of not numbering equations that we don't refer to. And in some cases, like (3), there is an actual name we can refer to ("Pascal's relation") that might make the text clearer as well as avoiding the need for numbers. As for the section-based numbering, I wonder if it really will make for fewer changes? Then we'd have to change all the numbers every time we change the section heading organization rather than every time we add or remove a numbered equation; both seem likely to be infrequent, but still often enough to be annoying. I just added my own first WP "numbered" equation a couple of days ago (in Euclid–Euler theorem‎) but in that case there was only one so I just used (*). —David Eppstein (talk) 07:07, 4 December 2014 (UTC)

I realized the problem with section reorganization shortly after I wrote the above. Perhaps using a letter scheme (A.1, A.2, etc. for section 3; B.1, B.2, etc. for section 5 (with no numbered equations in section 4)) and not going any deeper than main section levels would be about the best one could hope for given the fluid nature of our articles. I think that stars and names are to be preferred whenever they make sense. Bill Cherowitzo (talk) 18:03, 4 December 2014 (UTC)

Approximation

Hi, I explicitely checked the formula in the subsection APPROXIMATION, with Mathematica 10.0 and it is clearly wrong since the ratio of the two members goes to zero instead of 1. Could please someone tell me where to find the derivation of such a formula? — Preceding unsigned comment added by 163.1.241.224 (talk) 18:43, 11 May 2015 (UTC)

I think it's implicit in the section that $k=\Theta (n)$, though of course this isn't stated explicitly. (And why is this section not part of the preceding section, anyhow? Sigh.) --JBL (talk) 21:10, 11 May 2015 (UTC)

I'd rather say that implicitly $k-(n/2)=o(n)$; worth to mention this. 192.54.190.20 (talk) 16:37, 3 July 2015 (UTC)

Omar Khayyam triangle and Yang Hui triangle

User:Joel B. Lewis, you removed information about Yang Hui's triangle, with the argument this is a redirection, this is not the case, this was as now a link to the author of the triangle, I also added a link to Omar Khayyam, as it also created this triangle in Iran. It is interesting to have history of this triangle. I don't understand why you want to remove it.Popolon (talk) 01:36, 18 October 2016 (UTC)

Popolon, the purpose of the lead section of an article is to summarize the body of the article. If you would like to include historical information, you should put it in the section titled "History," along with an appropriate source. --JBL (talk) 02:11, 18 October 2016 (UTC)

The way I see it, this article is about binomial coefficients and there is lots to say about binomial coefficients. One part of what is important is the relationship of binomial coefficients to the Hui/Khayyam/Pascal triangle. That relationship deserves a mention, which is already present in the article using the most commonly accepted name Pascal's triangle. That the triangle itself has a long history is useful information for the article about the triangle, but, I am thinking that it is not sufficiently relevant to this article about binomial coefficients. 𝕃eegrc (talk) 13:32, 18 October 2016 (UTC)

Result of Singmaster

I removed the following:

A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, fix an integer d and let f(N) denote the number of binomial coefficients ${\tbinom {n}{k}}$ with n < N such that d divides ${\tbinom {n}{k}}$. Then

$\lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.$

Since the number of binomial coefficients ${\tbinom {n}{k}}$ with n < N is N(N + 1) / 2, this implies that the density of binomial coefficients divisible by d goes to 1.

The apparent reference (which I also removed, not given inline, but probably should have been) is here

The statement (as I'm interpreting it) appears to be false. For example, for d = 2, take N = 2^M, and then f(N) is exactly 3^M. So the expression inside the limit can be made arbitrarily small, certainly not something approaching 1.

Unfortunately, I can only view the first page of the Singmaster article, so if anyone else has access to it and can correct the statement, that would be great. Or maybe I'm just being dense, in which case, please revert me with extreme prejudice. --Deacon Vorbis (talk) 22:10, 2 May 2017 (UTC)

References

The number of even binomial coefficients up to 2^M is certainly not 3^M. It is the number of odd binomial coefficients that equals 3^M. —David Eppstein (talk) 22:17, 2 May 2017 (UTC)

Yeah, sorry; I had a bad feeling it had to be something stupid on my part. Thanks. --Deacon Vorbis (talk) 00:16, 3 May 2017 (UTC)

WP:OR?

§ Divisibility properties concludes with an interesting result (namely, that primality is equivalent to dividing all the intermediate binomial coefficients), but those statements look suspiciously like WP:OR. (Note, for example, that the paragraph is unsourced and includes a proof.) I couldn't find a source with a cursory Google search; does anyone else recognize the result as being published somewhere? 128.135.98.14 (talk) 18:03, 15 February 2019 (UTC)

There's a somewhat similar (but different) primality test based on looking at non-horizontal lines through Pascal's triangle in Mann, Henry B.; Shanks, Daniel (1972), "A necessary and sufficient condition for primality, and its source", Journal of Combinatorial Theory, Series A, 13: 131–134, doi:10.1016/0097-3165(72)90016-7, MR 0306098. This test itself is called "well-known" and is the starting point for the main results in a more recent paper, Dilcher, Karl; Stolarsky, Kenneth B. (2005), "A Pascal-type triangle characterizing twin primes", American Mathematical Monthly, 112 (8): 673–681, doi:10.2307/30037570, MR 2167768 —David Eppstein (talk) 22:32, 15 February 2019 (UTC)

Preamble

^{This section is about these changes (rev 883485190)}

@Deacon Vorbis: Let's continue here.

DIFF:883799926> giving a reason in an edit summary is better, but far better still, there's a reason= parameter that you're leaving blank It is not mandatory to specify reason in cases of obvious uncertainty. The word indexing is out of place and has very vague meaning. It probably means that indexing is expected to be done by using pascal's triangle but it is never meant anywhere and appropriate formula is given to calculate necessary number instead so it must be clarified for those clueless.

DIFF:883800488> still grammar problems, but more importantly, "In mathematics..." or "In biology..." or whatever are standard article openings in Wikipedia. Here, "term" is redundant, as a coefficient means the number sitting in front of a term. Again, if you still disagree, best to take to the talk page and discuss) The article is obviously mathematical so words "in mathematics" are redundant here. The "term" cannot be redundant cause binomial coefficient is inseparable from the term. It is like to say that referring to binomial expansion theorem is redundant here. Completely wrong. Those who are unfamiliar with theorem won't understand anything unless hinted by definitions so it must be left.

To reinforce my position I would like you to see what MOS:INTRO says about article accessibility. DAVRONOVA.A. ✉ ⚑ 20:02, 17 February 2019 (UTC)

I find this "grousing" to be totally unconvincing. The concern about indexing can be simply handled with a link to Index notation. We use expressions like "In mathematics ..." to set the context of an article. Redundancy is not an issue, this is only redundant if you already know what the article is about from its title, an assumption that flies in the face of accessibility. The reason that "binomial theorem" is so popular an expression is because "binomial expansion theorem" is so overly pedantic, a charge that can be leveled against most of these comments.--Bill Cherowitzo (talk) 21:47, 17 February 2019 (UTC)

@Bill Cherowitzo: I find this "grousing" to be totally unconvincing.[...] Well, I'm not surprised. After reading the last intro (rev 883485190) several times I found it difficult to understand anything until I referred to more friendly resources. Currently it seems to me that it is dedicated for hard-core mathematicians and not ordinary readers. Wikipedia was never meant to be that hard-core scientific reference of anything. Checkout WP:NOTJOURNAL #7 For more info. It is advised that the introduction is understandable without any advanced knowledge. It's pretty clear and that's why I request to clarify terms and give details by myself if I can.

The concern about indexing can be simply handled with a link to Index notation.[...] Yeah, thanks for your explanation, it's much better now but it doesn't solve the main problem yet: there is still nothing that the indexing is related to.

We use expressions like "In mathematics ..." to set the context of an article.[...] There is no way to infer context from a title unless you know the subject in a advance or it is explicitly mentioned. The context of this article is more algebraic rather than of merely broad math. Why not to add this instead of "In mathematics ..."? I'm not insisting on deleting the expression though. I'm mostly concerned about primary definition currently.

because "binomial expansion theorem" is so overly pedantic[...] I hardly can disagree with this but it is unrelated to this topic I believe. DAVRONOVA.A. ✉ ⚑ 10:15, 18 February 2019 (UTC)

Just a side note, but if you want to quote other editors, please use {{tq}} (for inline quotes), or {{talkquote}}/{{tq2}} (for set-apart). This avoids a bunch of span tags all over the place, and it uses a standard color that's less jarring and more accessible. In any case, I'm just not really sure what the issues here are. As the article even points out, binomial coefficients crop up in very widely different branches of math, so "In mathematics..." seems to be reasonably appropriate. As far as the bit about indexing, you said "It is not mandatory to specify reason in cases of obvious uncertainty". Except it's not obvious here (and it's almost never obvious anywhere) because it makes perfect sense to me and I don't know why someone would find it confusing. I mean, we could say something like "parameterized by" instead, but that's a bit more MOS:JARGONy. "Indexed by" means the same thing and is less technical, so I'm not sure what we could do here. — Preceding unsigned comment added by Deacon Vorbis (talk • contribs) 15:53, 18 February 2019 (UTC)

edit to "generating functions"

I edited the first equation under "generating functions" => "Ordinary generating functions" Previously read

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

now reads

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

Summing k above n is mildly confusing at best. — Preceding unsigned comment added by Affine.function (talk • contribs)

It would not be confusing to you if you read the article, where this is discussed at least twice: Binomial_coefficient#Generalization_and_connection_to_the_binomial_series and Binomial_coefficient#Binomial_coefficients_as_polynomials. --JBL (talk) 12:31, 15 December 2020 (UTC)

Largest currently known positive integer n such that binomial(n,k) has exactly k prime factors, counted with multiplicity

There are some results.

My results are:

k=1, n=2^82589933–1=148894445742...325217902591 (24862048 digits; elipsis omits 24862024 digits) (see largest known prime);

k=2, n=2618163402417 * 2^1290001 - 1 (388342 digits) (see Cunningham chain).

Can you extend my results for k>2? — Preceding unsigned comment added by 109.106.227.160 (talk • contribs) 18:01, 25 August 2021 (UTC)

Unless you are basing this on reliable publications rather than your own original research, it is off-topic here. This page is for discussions on improvements to the article, which can only be based on sources. —David Eppstein (talk) 18:27, 25 August 2021 (UTC)

Can you find the rsults for k from 3 to 32, please? I can only find results for n=1 or n=2. I know that, e.g., binomial(799,15) has exactly 15 prime factors, counting multiplicity, but I don't know that 799 is the currently largest known n such that binomial(n,15) has exactly 15 prime factors, counting multiplicity. Joakjovan21 (talk) 15:19, 27 August 2021 (UTC)

If you want people to assist with calculations, this is not the place. Try the WP:HELPDESK. —David Eppstein (talk) 16:50, 27 August 2021 (UTC)

Some proposed changes in the article on Binomial Coefficients - section Congruences

• Specific text to be added:

If $n$ is a positive integer and $p$ is a prime number, then

$\sum _{j=1}^{\lfloor \log _{p}{n}\rfloor }{\binom {n-1}{p^{j}-1}}\equiv \nu _{p}(n)\mod p,$ (11)

where $\nu _{p}(n)$ is the p-adic order or p-adic valuation of an integer n, being the exponent of the highest power of the prime number p that divides n. Equation (11) follows from a more elementary fact. If $j$ is a positive integer,

$${\binom {n-1}{p^{j}-1}}\equiv {\begin{cases}1\mod p&{\text{if }}\ p^{j}|n\\0\mod p&{\text{if }}\ p^{j}\nmid n.\end{cases}}$$

• Reason for the change: I humbly think this result is a valid addition to the body of knowledge on this topic. Additionally, I believe that there is no review article in which the result I demonstrated is stated.
• References supporting change: http://math.colgate.edu/~integers/w61/w61.pdf

Dario T. de Castro (talk) 10:32, 1 September 2022 (UTC) Dario T. de Castro (talk) 10:32, 1 September 2022 (UTC)

Hey there, which article do you want to add this to? Thanks, --Ferien (talk) 19:05, 1 September 2022 (UTC)

Dear Ferien, the addition was intended for the article on 'Binomial Coefficients', in the 'Congruences' section.Dario T. de Castro (talk) 23:59, 1 September 2022 (UTC)

See my comment below for the other requested addition. My reaction here is the same. —David Eppstein (talk) 13:52, 26 September 2022 (UTC)

Proposed changes in the article on Binomial Coefficients - section Divisibility properties

• Specific text to be added:

Let $\nu _{p}(n)$ be the p-adic valuation of a positive integer n, being the exponent of the highest power of the prime number p that divides n. Then

$\nu _{p}(n)=p\sum _{j=1}^{\lfloor \log _{p}{n}\rfloor }\left\{{\binom {n}{p^{j}}}{\frac {p^{j-1}}{n}}\right\},$

where $\{x\}$ denotes the fractional part of $x$.

• Reason for the change: I humbly think this result is a valid addition to the body of knowledge on this topic and in this section. Additionally, I believe that there is no review article in which the result I demonstrated is stated.
• References supporting change: http://math.colgate.edu/~integers/w61/w61.pdf

Dario T. de Castro (talk) 06:40, 8 September 2022 (UTC) Dario T. de Castro (talk) 06:40, 8 September 2022 (UTC)

References

Moved this and the preceding section from Dario's talk page. Rusalkii (talk) 04:37, 24 September 2022 (UTC)

This article is already a mass of way too many big intimidating equations and way too little explanatory text. Both the previous change and this one would add to that problem, not improve it. —David Eppstein (talk) 04:54, 24 September 2022 (UTC)

agreed 24.52.219.172 (talk) 06:25, 26 September 2022 (UTC)

I don't think that this has demonstrated the impact that suggests it should go in the article. The other identities in the article are generally well-covered by textbooks in the field. Russ Woodroofe (talk) 13:13, 27 September 2022 (UTC)

Dear David, Russ and other contributors

I am reading the comments made in this article on Binomial Coefficient (sec. Congruences and sec. Divisibility Properties). I agree with Dr. Eppstein in that the article as a whole needs improvement. I am also aware that the editions I propose involve conflict of interest. So, it seems to me that I should choose not to express myself in this debate and hope that you and your collaborators decide on the best way to edit this material. Perhaps I should say that I proposed these changes with the intention of disseminating knowledge about a somewhat new connection between binomial coefficients and the prime factorization of integers. With kind regards,Dario T. de Castro (talk) 20:00, 27 September 2022 (UTC)

Name for an identity

Hi, in french the formula $k{n \choose k}=n{n-1 \choose {k-1}}$ is named "pawn formula" : https://fr.wikipedia.org/wiki/Formule_du_pion. Is there a name in English ? Robert FERREOL (talk) 11:39, 25 November 2022 (UTC)

FWIW, Concrete Mathematics calls the identity (or a slightly rearranged form of it) "absorption/extraction". A casual search finds some other uses of the term absorption, although I'm not certain it is widespread; I didn't find the term extraction. Russ Woodroofe (talk) 11:50, 25 November 2022 (UTC)

Thank you. I added this reference on https://fr.wikipedia.org/wiki/Formule_du_pion. Robert FERREOL (talk) 09:31, 27 November 2022 (UTC)

I have never felt that this identity had a standard English name. --JBL (talk) 17:38, 27 November 2022 (UTC)

Blank section on programming languages?

Can the section on programming languages be blanked? It adds nothing at all to the article; it reads like a homework assignment for high-school seniors. There are interesting things to say about algorithmic identities for binomials, but those algorithms customarily appear first in basic hypergeometric series (and date back to the 19th century, so pre-computer algorithms. I think Kummer gave some of the first ones.) So, yes, there could be a section on those algorithms, but this is not it. 67.198.37.16 (talk) 22:45, 5 January 2024 (UTC)

I was bold and just blanked. Looking at the page history, this section was an accretion of original research that was added over the years by anon authors making a case for their favorite programming languages. 67.198.37.16 (talk) 22:55, 5 January 2024 (UTC)

"NCk" listed at Redirects for discussion

The redirect NCk has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2024 February 6 § NCk until a consensus is reached. Shhhnotsoloud (talk) 18:47, 6 February 2024 (UTC)