Skip to main content
added 90 characters in body
Source Link
David Harris
  • 3.5k
  • 1
  • 26
  • 38

Suppose $d$ is a constant $< n^2$, and $m > n$. I have a kind of factorial function where I subtract $d$ from each pair of terms.

Is there any simple upper bound on $$ P = ( m (m-1) - d) \times ( (m-2) (m-3) - d ) \times \cdots \times \times ((n+1) n - d) $$

I only need an exponentiallypolynomially tight upper bound. If it makes it easier, you can assume $m = cn$ for $c$ close to 2.

The best I can come up with is $$ P \leq \Bigl( \frac{m (m-1) - d}{m (m-1)} \Bigr)^{(m-n)/2} m!/n! $$ but I don't think this is tight.

Thanks!

EDIT: Previous version incorrectly stated "exponentially tight" vs "polynomially tight"

Suppose $d$ is a constant $< n^2$, and $m > n$. I have a kind of factorial function where I subtract $d$ from each pair of terms.

Is there any simple upper bound on $$ P = ( m (m-1) - d) \times ( (m-2) (m-3) - d ) \times \cdots \times \times ((n+1) n - d) $$

I only need an exponentially tight upper bound. If it makes it easier, you can assume $m = cn$ for $c$ close to 2.

The best I can come up with is $$ P \leq \Bigl( \frac{m (m-1) - d}{m (m-1)} \Bigr)^{(m-n)/2} m!/n! $$ but I don't think this is tight.

Thanks!

Suppose $d$ is a constant $< n^2$, and $m > n$. I have a kind of factorial function where I subtract $d$ from each pair of terms.

Is there any simple upper bound on $$ P = ( m (m-1) - d) \times ( (m-2) (m-3) - d ) \times \cdots \times \times ((n+1) n - d) $$

I only need an polynomially tight upper bound. If it makes it easier, you can assume $m = cn$ for $c$ close to 2.

The best I can come up with is $$ P \leq \Bigl( \frac{m (m-1) - d}{m (m-1)} \Bigr)^{(m-n)/2} m!/n! $$ but I don't think this is tight.

Thanks!

EDIT: Previous version incorrectly stated "exponentially tight" vs "polynomially tight"

Source Link
David Harris
  • 3.5k
  • 1
  • 26
  • 38

Simple variation on factorial --- upper bound

Suppose $d$ is a constant $< n^2$, and $m > n$. I have a kind of factorial function where I subtract $d$ from each pair of terms.

Is there any simple upper bound on $$ P = ( m (m-1) - d) \times ( (m-2) (m-3) - d ) \times \cdots \times \times ((n+1) n - d) $$

I only need an exponentially tight upper bound. If it makes it easier, you can assume $m = cn$ for $c$ close to 2.

The best I can come up with is $$ P \leq \Bigl( \frac{m (m-1) - d}{m (m-1)} \Bigr)^{(m-n)/2} m!/n! $$ but I don't think this is tight.

Thanks!