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
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Try induction over $n$. $\endgroup$– Max HornCommented Nov 21, 2019 at 8:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Nov 21, 2019 at 0:30
-
1$\begingroup$ Do you mean ${n+1 \brack {n-k+1}}$ ? $\endgroup$– DigerCommented Nov 21, 2019 at 11:48
-
$\begingroup$ I'm pretty sure it is what I said above.. $\endgroup$ Commented 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$– DigerCommented Nov 21, 2019 at 13:58
-
$\begingroup$ Yes, you're right. I edit and fix the typo now. $\endgroup$ Commented Nov 21, 2019 at 14:34