What Is the Behavior of Symbolic nchoosek With n < 0 ?

According to nchoosek:Algorithms

"If k < 0 or n – k < 0, nchoosek(n,k) returns 0."

syms n k
f(n,k) = nchoosek(n,k)

f(n, k) = 

Using the example at Binomial Coefficients for Numeric and Symbolic Arguments

nn = sym(-7); kk = sym(2);
isAlways(nn - kk < 0)

ans = logical
   1

f(nn,kk)

ans = 

28

The result should be 0 according to the algorithms section.

But given that it's not zero, where did it come from?

Not a simple factorial expression

try
    factorial(nn)/factorial(kk)/factorial(nn-kk);
catch ME
    ME.message
end

ans = 'Nonnegative integer or symbolic variable expected.'

Try an expanded version of f

f(n,k) = expand(f)

f(n, k) = 

The above expression does not match (to the eye) More About.

It also doesn't yield the original result

f(nn,kk)

ans = 

NaN

Nor does the simplified form (which also doesn't visually match More About)

f = simplify(f)

f(n, k) = 

f(nn,kk)

ans = 

NaN

Is the doc wrong and symbolic nchoosek(-7,2) should return 28? If so, where does 28 come from?

FWIW, nchoosek is not using abs(n)

f(abs(nn),kk)

ans = 

21

[dpb]

nchoosek

L=readlines('/MATLAB/toolbox/symbolic/symbolic/@sym/nchoosek.m');
L

L = 61×1 string array
    "function c = nchoosek(n,k)"
    "%NCHOOSEK Binomial coefficient or all combinations."
    "%    NCHOOSEK(N,K) where N and K are scalars returns N!/K!(N-K)!."
    "%"
    "%    NCHOOSEK(V,K) returns a matrix containing all possible combinations"
    "%    of the elements of vector V taken K at a time. K must be a"
    "%    non-negative integer."
    "%    The result has K columns and NCHOOSEK(N, K) rows, where N is length(V)."
    ""
    "%   Copyright 2011-2023 The MathWorks, Inc."
    ""
    "if ~isa(n, 'sym') && ~isscalar(n)"
    "    c = nchoosek(n, double(k));"
    "    return;"
    "end"
    ""
    "N = formula(sym(n));"
    "K = formula(sym(k));"
    ""
    "if isscalar(N)"
    "    args = privResolveArgs(n, k);"
    "    if ~isscalar(K)"
    "        error(message('symbolic:sym:nchoosek:SecondArgumentMustBeScalar'));"
    "    end"
    "    cSym = binomial(N, K);"
    "else"
    "    args = privResolveArgs(n);"
    "    if ~isPositiveInteger(K) && ~isequal(K, sym(0))"
    "        error(message('symbolic:sym:nchoosek:SecondArgumentMustBeNonNegInt'));"
    "    end"

N = sym(-7); K = sym(2);
cSym = binomial(N, K)

Unrecognized function or variable 'binomial'.

I don't have the Symbolic TB so not easy to delve into the bowels, but exploring what the private symbolic function binomial does should uncover at least what it is doing.

That there is a disconnect between result and doc is clear, however; certainly unclear what it may be doing internally.

[Paul]

Good idea!

binomial is actually a local function in sym/nchoosek.m. It leads to a call to nchoosek in the symbolic engine, which as best I can tell for the case at hand resolves to:

n = -7; k = 2;
((-1)^k*nchoosek(k - n - 1, k))

ans = 28

So I guess that explains the result so obtained, but I'm not sure how to interpret what that result actually means. 28 ways to choose 2 elements from a set of -7 elements?

If we make k odd, we get

nchoosek(sym(n),sym(3))

ans = 

which is again consistent with the formula above

k = 3;
((-1)^k*nchoosek(k - n - 1, k))

ans = -84

though again I have no idea how to interpret that result.

[Torsten]

n = -7;
k = 2;
n*(n-1)/(1*2)

ans = 28

n = -7;
k = 3;
n*(n-1)*(n-2)/(1*2*3)

ans = -84

Answer 1

[Stephen23]

It seems to use Newton's generalized binomial theorem:

https://en.wikipedia.org/wiki/Binomial_theorem#Newton's_generalized_binomial_theorem

which comes down to this:

nn = -7;
kk = 2;
prod(nn:-1:nn-kk+1) / factorial(kk)

ans = 28

The documentation is wrong.

[Paul]

"The documentation is wrong."

Here's another case directly from the examples on the doc page nchoosek that contradicts the statement in the Algorithms section regarding the k < 0 case.

n = sym(-5); k = sym(-5);
nchoosek(n,k)  % should be 0 because k < 0, according to Algorithms

ans = 

1

I think the logic is in this case (with n and k both integers)

if k < 0 & n < 0 & n - k >= 0, then

nchoosek(n, n - k)

ans = 

1

k = sym(-8); % another example
[nchoosek(n,k),nchoosek(n,n-k)]

ans = 

which are not the same as

% prod(nn:-1:nn-kk+1) / factorial(kk)

which will error due to the factorial(kk) with kk < 0.

But, if k < 0 & n < 0 and n - k < 0, then we do get 0

k = sym(-3); 
nchoosek(n,k)  % n - k = -2

ans = 

0

Maybe the statement on the doc page was meant to say:

"If k < 0 AND n – k < 0, nchoosek(n,k) returns 0."

at least for integer values of k and n. Though that doesn't explain what should happen in other cases of interest.

[dpb]

Reinforces prior discussion of how difficult it is to write totally accurate documentation and that having the developers also review the documentation guarantees neither accuracy nor completeness.

Lacking a published reference back to the formal requirements, when things get complicated documentation by narrative and example is almost inevitably going to fail at some level of detail.

[Paul]

Yes, I agree that writing good documentation is hard. But I don't think hard is the issue here.

I hope we agree that, as a minimum, a doc page shouldn't contain statements that are factually incorrect regarding how the function operates.

As to the rest of the page, it seems like the basic approach should be to just state that sym/nchoosek is a generalization of the standard binomial coefficient and then explain how it works for whatever numerical inputs (or expressions) the function will allow (or provide a reference thereto).

From reading the page, the only clue (unless I missed something) that nchoosek allows n to be a real, non-integer is that nchoosek can be differentiated wrt to n (which kind of sounds odd because the symbol n typically implies an integer value)

nchoosek(sym(5.1),sym(2)) % uses Newton's generalization

ans = 

Interestingly enough, non-integer k returns the input unevaluated (as opposed to throwing an error?)

nchoosek(sym(5),sym(2.1))

ans = 

Is that a feature that was just too hard to document? Or a bug? Or just undefined behavior?

Obviously I can only speak for myself, but it really seems like there is a lot more to sym/nchoosek than the average user would infer from its documentation (nevermind the issue that expanding/simplifying nchoosek can lead to expressions that evaluate to a different result than nchoosek itself).

[Stephen23]

"Is that a feature that was just too hard to document?"

That is a highly pertinent point: if not structured well, documenting absolutely everything can easily lead to the most commonly-required information being hidden in amongst a forest of mostly irrelevant factoids. It is a tricky balance to achieve (perhaps the help could utilise the digital medium better and act less like a static page).

"...it really seems like there is a lot more to sym/nchoosek than the average user would infer from its documentation"

I guess that is generally the case for most functions.

[Paul]

"(perhaps the help could utilise the digital medium better and act less like a static page)."

Can you expand on this thought (perhaps better suited to Discussions) ?

[dpb]

Since nchoosek goes back to MATLAB's early days, it's quite possible the documentation was correct initially and negative arguments weren't introduced until the Symbolic Toolbox was added (ca 1993, R?) and the specific prior documentation wasn't changed; just added some examples using sym. I don't still have the printed MATLAB Release 3.1 manual, unfortunately; although it also may have predated nchoosek to check. It's unfortunate Mathworks doesn't have a public repository of all prior documentation versions.

[Steven Lord]

Since nchoosek goes back to MATLAB's early days, it's quite possible the documentation was correct initially and negative arguments weren't introduced until the Symbolic Toolbox was added (ca 1993, R?) and the specific prior documentation wasn't changed; just added some examples using sym.

Note that there are (at least) two documentation pages for the nchoosek function. The document linked in this discussion is to the nchoosek method for sym objects, which requires at least one of the inputs be a sym object. The nchoosek function for numeric inputs (which is in MATLAB not Symbolic Math Toolbox) does not explicitly state what happens for negative inputs. What if the first is negative?

x = nchoosek(-7, 2)

x =

  0×2 empty double matrix

No, this is not a bug. There are two different syntaxes listed on the nchoosek documentation page, nchoosek(n, k) and nchoosek(v, k). The first returns the binomial coefficient, the second returns a matrix containing the combinations of the elements of the vector v chosen k at a time. In this particular case, it's ambiguous which syntax you're trying to call.

The description of the first syntax states "n and k must be nonnegative integers." So in this case, because the first input doesn't satisfy the requirement to be n, MATLAB decides that it must be v and you're calling the second syntax. How many ways can you choose 2 different elements out of a 1 element vector?

If the input were a non-negative scalar, we break the ambiguity by preferring the first syntax.

x = nchoosek(7, 2)

x = 21

If the second input is negative, neither syntax supports that so MATLAB throws an error.

x = nchoosek(7, -2)

Error using nchoosek (line 29)
The second input has to be a non-negative integer.

Perhaps the documentation page for the MATLAB function should be more explicit about this case. If you feel that way, please share your feedback on that documentation page using the star rating section at the end of the doc page and provide prose feedback after you rate it.

[Paul]

Getting a bit off topic from the original question, which was about sym inputs to sym/nchoosek, but ...

Both flavors of nchoosek support the (v,k) input. Suppose a user is writing code with

C = nchoosek(v,k)

with the intent that v is always a vector, though not known until execution time. The I suppose that code would have to look something like this

if numel(v) < k
    C = zeros(0,k); % probabaly also need to ensure correct class of C
else
    C = nchoosek(v,k);
end

to guard against a scalar input v that would then be interpreted as the (n,k) syntax.

[dpb]

"Note that there are (at least) two documentation pages for the nchoosek function. The document linked in this discussion is to the nchoosek method for sym objects, ..."

If one goes and compares, it's easy to see the sym objects page was derived starting with the base product doc; much of the verbiage is identical or only a very minor recast of it. Then, the symbolic stuff was tried to be addressed as edits(*).

I think the whole page for symbolic inputs other than positive integers needs a major revisiting given the expanded scope of inputs now allowed and the expanded results.

Describing the inputs for n and k as "Number of possible choices, ..." and "Number of selected choices, ..." is nonsensical for n, k <0 whether they're symbolic variables or not.

I think the Algorithms and/or a Tips section should be much more amplified; MATLAB documentation is generally pretty good in including references to the literature about where stuff comes from and in use/interpretation of results for the user who more than likely is not a mathematician but this particular page seems pretty weak.

I have noted before that much of the TB documentation isn't really up to the level of the main MATLAB core, however.

(*) At which point I'm always back to the Q? of how Mathworks actually writes/documents the official requirements for such functions -- is there an actual formal definition that does specify the result for all combinations of inputs or is the developer given the general description of what the function is supposed to do and it's then up to him/her/them to invent a solution and the resulting specification is then the implemented behavior after whatever internal review is done?