3
$\begingroup$

I was playing with my Python implementation of some combinatorial functions, specifically those that return the number of combinations of $r$ elements from a set of cardinality $n$:

Without repetition: $\frac{n!}{r!(n-r)!}$
With repetition: $\frac{(n+r-1)!}{r!(n-1)!}$

For convenience, I will refer to the former function as $C(n, r)$, and the latter as $Cr(n, r)$.

While doing this, I found something fascinating:

$$\lim_{a\to\infty} {Cr(a^2, a) \over C(a^2, a)} = e$$

Those who know Python can verify the correctness of my implementation of the functions:

def permutation_count(n, r, repetitions=False):
    """Returns the number of permutations of 'r' elements from a set of
    cardinality 'n'."""
    if repetitions:
        return n**r
    else:
        return reduce(lambda x, y: x * y, range(n, n - r, -1))

def combination_count(n, r, repetitions=False):
    """Returns the number of combinations of 'r' elements from a set of
    cardinality 'n'."""
    if repetitions:
        n = n + r - 1
    return permutation_count(n, r) // factorial(r)

# My function:
def f(a):
    return combination_count(a**2, a, True) / combination_count(a**2, a, False)

I observed the above result by simply evaluating this function for increasingly large integer values. I will send any who request it a text file containing the results of the function for said values.

I posted this here for these reasons:
1. There's the possibility, however small, that I am the first to discover this equation.
2. I enjoy math and I'm fairly knowledgeable regarding it, but I'm definitely not an expert, and I have no idea what the significance of this discovery is. Someone more knowledgeable than myself might consider it trivial, as it may logically proceed from some known mathematical property.
3. If this discovery is in fact significant, it could be useful to those more knowledgeable than myself. I would also like to understand why it is significant, in that case.

$\endgroup$
1
  • 1
    $\begingroup$ My guess would be that perhaps it can be derived from Stirling's formula. $\endgroup$ Jun 24, 2017 at 5:00

1 Answer 1

4
$\begingroup$

As Lord Shark the Unknown commented, when factorials appear in limits, Stirling approximation is more than convenient.

For your case, $${Cr(a^2, a) \over C(a^2, a)}=\frac{\left(a^2-a\right)! \left(a^2+a-1\right)!}{a^2! \left(a^2-1\right)!}$$ Take logarithms and use Stirling approximation for $\log(p!)$. This will lead you to $$\log\left({Cr(a^2, a) \over C(a^2, a)} \right)=1-\frac{1}{a}+\frac{1}{6 a^2}-\frac{1}{3 a^3}+O\left(\frac{1}{a^4}\right)$$ Using Taylor again with $x=e^{\log(x)}$, this leads to $${Cr(a^2, a) \over C(a^2, a)}=e\left(1-\frac{1}{a}+\frac{2}{3 a^2}-\frac{2}{3 a^3}+O\left(\frac{1}{a^4}\right)\right)$$ Using $a=10$, we have $${Cr(100,10) \over C(100, 10)}=\frac{327955500867}{133156226588}\approx 2.46294 $$ while the above expansion would give $$\frac{453}{500}e \approx 2.46276$$ These numbers differ by $0.007$%.

Edit

In fact, using the same approach, we could show that $${Cr(a^{2k}, a^k) \over C(a^{2k}, a^k)}=e\left(1-\frac{1}{a^k}+\frac{2}{3 a^{2k}}-\frac{2}{3 a^{3k}}+O\left(\frac{1}{a^{3k+1}}\right)\right)$$

In the same spirit $${Cr(a^3, a) \over C(a^3, a)}=1+\frac{1}{a}-\frac{1}{2 a^2}-\frac{5}{6 a^3}+O\left(\frac{1}{a^4}\right)$$

$\endgroup$
1
  • $\begingroup$ I'm familiar with the gamma function but I'd never heard of Stirling approximations. The reason I relied on a brute force algorithm rather than a mathematical proof is because I had no idea what to do with the factorials. I couldn't simplify them, nor could I use L'Hopital's Rule because the factorial function is not differentiable (just because the gamma function is does not mean that I can substitute it). I figured I would have to use a Taylor series, but I couldn't figure out a good way to create one for it. So thank you, this will be very helpful to me. $\endgroup$ Jun 24, 2017 at 6:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .