4
$\begingroup$

I'm trying to compute the number of ways to sum the first $n$ unique positive integers to a number $k$. This is not a partition of $n$ since we can't repeat numbers.

Any hints on how I can derive a generating function for this?

I encountered this in trying to compute the variance of the sum of $k$ balls randomly drawn from an urn of $n$ balls (where each ball is labeled with a unique positive integer from $1...n$). Letting $S$ be the random variable which is this sum, computing the variance using the definition of expectation directly uses $P(S = k) = \frac{N_{n,k}}{{n\choose k}}$, where $N_{n,k}$ denotes the desired quantity above. I can compute the variance by writing $S$ as a sum of indicators and expanding the expression inside of the expectation, but I was wondering if there was a nice expression for the above quantity.

Thank you!

$\endgroup$
  • $\begingroup$ Now I know what you are asking. $\endgroup$ – Laz Oct 4 '18 at 20:37
  • 1
    $\begingroup$ @Laz Ok! Just a hint to point me in the right direction would be appreciated :) $\endgroup$ – TheProofisTrivium Oct 4 '18 at 20:38
  • 1
    $\begingroup$ I believe this math.stackexchange.com/questions/421909/… is asking the same thing, but I'm not sure how the asker came up with that GF. $\endgroup$ – TheProofisTrivium Oct 4 '18 at 20:42
  • $\begingroup$ You can try to use some kind of induction to construct a formula, using something like this. If you have a formula for any $k\leq m$, then any subset $S_{m+1}$ whose sum is $m+1$ can be partitioned into two subsets, the subset ${1}$ (if $1\in S_{m+1}$) and a subset $S_m$ whose sum is $m$. Of course, you have to garantee that $1\notin S_m$. If $1\notin S_{m+1}$, now you try with $2$, and so on ... In how many ways can you do that? I don't know if it'll work, but you can twist that idea as much as you want. $\endgroup$ – Laz Oct 4 '18 at 21:01
  • 1
    $\begingroup$ The answer to the question is the number of solutions for $$1\cdot x_1+2\cdot x_2+3\cdot x_3+...+n\cdot x_n =k$$ where $x_i \in \{0,1\}$. It's generating function is $$(1+x)(1+x^2)(1+x^3)...(1+x^n)$$ and the coefficient of $x^k$ is the answer. But this doesn't make the problem easier. $\endgroup$ – rtybase Oct 4 '18 at 21:02
1
$\begingroup$

Edit: this answer was written for a previous version of the question, which asked how to compute the variance.


The distribution is not needed to compute the variance. Let $X_i \in {1,2 \cdots n}$, for $i\in {1,2 \cdots k}$, be the result of the $i-$th extraction. CLearly $X_i$ are identically distributed, but not independent.

Let $S=\sum_{i=1}^k X_i$

We have $E[S]=k E[X_1] = k \frac{n+1}{2}$

And $E[S^2] = k E[X_1^2 ]+ k(k-1)E[X_1 X_2]$

For the last term you can use $E[X_1 X_2]=E[X_1E[X_2 \mid X_1]]$

Can you go on from here?

I got $$Var(n,k) = \frac{k\,\left( n+1\right) \,\left( n-k\right) }{12}$$

At least it sounds consistent : $Var(n,n)=0$,$Var(n,1)=Var(X_1)$ and $Var(n,k)\to k n^2/12 $ for $n\gg k$


Edit: here goes some detail.

$$E[X_1^2 ]=\frac{2{{n}^{2}}+3n+1}{6}$$

$$E[X_1 | X_2 =j] =\frac{1}{n-1}\left( -j + \sum_{i=1}^n i \right)=\frac{1}{2n-2}\left( n^2 +n -2j \right)$$

$$E[X_1 X_2 ] =\frac{1}{2n-2}\left( (n^2+n)E[X] -2 E[X^2] \right)=\frac{3{{n}^{2}}+5n+2}{12}$$

$$E[S^2] = \frac{k\,\left( n+1\right) \,\left( 3kn+n+2k\right) }{12}$$

$$\sigma_S^2(n,k)=E[S^2] -E[S]^2= \frac{k\,\left( n+1\right) \,\left( n-k\right) }{12}$$

$\endgroup$
0
$\begingroup$

With regards to the number of subsets, the answer to the question is the number of solutions for $$1\cdot x_1+2\cdot x_2+3\cdot x_3+...+n\cdot x_n =k$$ where $x_i \in \{0,1\}$. It's generating function is $$P_n(x)=(1+x)(1+x^2)(1+x^3)...(1+x^n)$$ and the coefficient of $x^k$ is the answer $N_{n,k}$ (more reading here). It can be computed from $$N_{n,k}=\frac{P_n^{(k)}(0)}{k!} \tag{1}$$ or, given $P_n(x)=P_{n-1}(x)(1+x^n)$, using recurrence: $$N_{n,k}=N_{n-1,k}+N_{n-1,k-n} \tag{2}$$ where $N_{n,0}=1$ and $N_{n,k}=0, k >\frac{n(n+1)}{2}$, $\forall n\in\mathbb{N}$. According to the same article, this is NP-complete problem.

$\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.