2
$\begingroup$

Recall: typically, for integers $n\ge r$, we define

$$P(n,r) = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}$$

which gives the number of ways for us to take $r$ objects from a set of $n$ distinct ones (without repetition) and form arrangements of them. (I don't know what to call these, and thus refer to them as "permutation coefficients", thus the title.) Similarly, where we don't care about order in these arrangements, we have instead the binomial coefficient

$$C(n,r) = \binom n r = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}$$

to give us the number of such selections.

Now, in my combinatorics class this semester, we found it useful, particularly when dealing with stuff involving generating functions, to define a "generalized" binomial coefficient, generalized in the sense that now we only require $r\in\Bbb Z^+$. Then, relying on the relation between the binomial and permutation coefficients, $C(n,r)=P(n,r)/r!$ and using the falling factorial form for $P(n,r)$ (the product), we define the generalized binomial coefficient to be

$$C(n,r) = \frac{n(n-1)\cdots (n-r+1)}{r!}$$

(Note, again, that now $n$ may not be an integer or positive or any of that. It may even be a complex number!)


My questions being, can we define such a generalization for these so-called "permutation coefficients"? Is it meaningful to do so? And, to touch on a later point, how do we handle $n\in \Bbb Z^-$?

Based on how the generalized binomial coefficient comes about, I imagine the definition would rely on the falling factorial form for $P(n,r)$. Thus, we would have, for $n\in\Bbb C,r\in\Bbb Z^+$,

$$P(n,r) = n(n-1)(n-2)\cdots(n-r+1)$$

Or, arguably more succinctly, $P(n,r) = r!\cdot C(n,r)$. Of course, this is where the question of "meaningfulness" comes in since if we can define these generalized "permutation coefficients" in terms of the generalized binomial ones, it feels like unless there's a particularly useful application of them there wouldn't be much "point" to doing so.

But I feel more curiously is how we might expect to handle an $n$ which is a negative integer.

For the generalized binomial coefficients, this isn't an issue since Wolfram can even give us $C(i,4)$ for example (link). Wolfram will give us results, in the permutation case, for $n \in \Bbb C \setminus \Bbb Z^-$ - for example, $P(5+2i,4)$ (link) and $P(-0.5,4)$ (link).

Yet, on the other hand, $P(-1,4)$ and other such $P(n,r)$'s with $n$ a negative integer return a result of "undefined"! (example link). It certainly seems like if we can do most omplex numbers, we should be able to do negative integers - what is the problem? I doubt it's unintentional or tied to Wolfram, if we can get the complex cases, and all the cases in the generalized binomial coefficients - and it certainly isn't any more difficult a calculation - so what is the issue with $n \in \Bbb Z^-$?


So, in short, my questions:

  • Is this how we might define a "generalized permutation coefficient"? If nothing else, Wolfram seems to use the same definition I felt fit. I'm having trouble Googling around for this though.

  • Is there any meaningful reason to bother defining this? It certainly seems trivial enough especially in light of the generalized binomial coefficients. And I guess my inability to find something with a cursory Google search is indicative that it's probably uninteresting.

  • Perhaps my biggest question, is there a reason $P(n,r)$ is undefined for $n\in\Bbb Z^-$, at least on Wolfram Alpha? Working by hand would suggest that, for example, $P(-2,5)$ should be $-720$, yet Wolfram returns an undefined result. Yet when we use any other complex number, it works, so I feel there's an intent behind this, or perhaps a mathematical reason I'm overlooking.

$\endgroup$
  • 1
    $\begingroup$ I'd guess that Wolfram uses the Gamma function in computing $P(n,r)$ (I don't know why it's done differently than $C(n,r)$ in Wolfram) and the Gamma function is not defined at non-positive integers. See math.stackexchange.com/questions/705103/… $\endgroup$ – Ned May 1 at 14:54
1
$\begingroup$

To your first question, yes, it does make sense to define $P(n,r)=\prod_{i=0}^{r-1}(n-i)$, thus extending domain of $n$ to all of $\mathbb C$ (or really any commutative ring with identity). Then $P(n,r)$ is also called the falling factorial, sometimes denoted $n^{\underline r}\,$.

Just like $C(n,k)$ counts sets of size $k$ for $n>0$, there is a nice combinatorial interpretation $|C(-n,k)|$; it counts multisets of size $k$. There is a similar duality for $P(n,k)$. Whereas $P(n,k)$ counts ordered lists without repetition, $|P(-n,k)|$ counts the number of ways to place $k$ distinct flags on $n$ distinct flagpoles, where the order of the stack of flags on each pole matters. Note that $|P(-n,k)|=n(n+1)\cdots (n+k-1)$ is the rising factorial, denoted $n^{\overline k}$. This is sort of like an ordered version of a multiset. You can think of the flagpoles as the objects being chosen, and putting a flag on it an object represents choosing it. You can put multiple flags on a pole, so you can choose an object multiple times. Since the flags are distinct, order matters.

Finally, the reason that Wolfram Alpha cannot compute $P(n,r)$ when $n$ is a negative integer is because $(-n)!$ is undefined. Specifically, the Gamma function has a simple pole at each nonnegative integer. However, we can still calculate $P(n,r)$ using $n!/(n-r)!=\Gamma(n+1)/\Gamma(n-r+1)$. Since we have a simple pole in the numerator and denominator, they effectively cancel. The ratio now has a removable singularity at each nonnegative integer, and we can define $P(n,r)$ as the limit for $n$ in the neighborhood of the negative integer. In this case, we recover the expected $P(n,r)=\prod_{i=0}^{r-1}(n-i)$ result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.