3
$\begingroup$

Let $S=\{1,2,3,...,n\}$ be the set of integers up to $n$ and $p_k(a_1,...,a_k)=a_1\cdots a_k$ the product of $k$ distinct integers $a_1,...,a_k \in S$. There are $\binom{n}{k}$ possibilities to construct such a product $p_k$. I was wondering if it is anyhow possible to estimate the sum of all such $k$-products $p_k$ or similarly the mean value as $n$ is large. Any idea? Thanks

$\endgroup$
1
  • $\begingroup$ Try induction over $n$. $\endgroup$
    – Max Horn
    Nov 21, 2019 at 8:53

1 Answer 1

10
$\begingroup$

The sum of all $k$-products of numbers in the interval $\{1,2,\ldots,n\}$, it is, the number you are referring to, is known as the Stirling number of the first kind: ${n+1 \brack {n+1-k}}$. There are plenty of articles that face the problem of giving estimations of these numbers out there.

$\endgroup$
4
  • 1
    $\begingroup$ Do you mean ${n+1 \brack {n-k+1}}$ ? $\endgroup$
    – Diger
    Nov 21, 2019 at 11:48
  • $\begingroup$ I'm pretty sure it is what I said above.. $\endgroup$ Nov 21, 2019 at 13:52
  • 1
    $\begingroup$ Hm, but $(x+1)\cdots(x+n)=\sum_{k=0}^n {n+1 \brack {k+1}} \, x^k$ and the coefficient of $x^k$ is the sum of all products of $n-k$ distinct integers in $\{1,...,n\}$. Therefore the coefficient of $x^{n-k}$ is the sum of all products of $k$ distinct integers which is ${n+1 \brack {n-k+1}}$. $\endgroup$
    – Diger
    Nov 21, 2019 at 13:58
  • $\begingroup$ Yes, you're right. I edit and fix the typo now. $\endgroup$ Nov 21, 2019 at 14:34

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