power sum of a choice

A really nice problem occured in ABC 471, if I was smarter I would’ve been able to solve it faster but I did get to a solution and was satisfied with just that too; but to get better must distill it.

Problem

There are $N$ balls numbered $1$ to $N$ . Ball $i$ has an integer $A_{i}$ written on it.

For a way of choosing some $K$ balls from the $N$ balls, define the score of that choice as $(\sum_{i \in K ba ll s} A_{i})^{p}$

Try to solve this problem for different $p$ .

$p = 1$

I am familiar with the idea of counting contributions and this is just a simplified application of it.

For each $A_{i}$ you can ask, how many choice sets will this be part of? Since one is fixed, you can just choose $K - 1$ from the remaining $N - 1$ , so contribution for “this” $A_{i}$ is $(k - 1 n - 1) A_{i}$ , sum it over and you have your solution

$$\sum_i \binom{n-1}{k-1} A_i$$$

$p = 2$

This was the original problem from the contest. The solution that I arrived at followed a recursive logic and I wouldn’t call it as clean as the intended solution which leans closes to the general solution to the problem as well.

Solution 1 : decompose to terms and count contribution individually

Same as the $p = 1$ case for contribution counting but we’re applying it here.

In the expansion of the square, you would have $A_{i}^{2}$ terms as well as $A_{i} A_{j}$ terms. It’s important to be precise here otherwise we run the risk of over/under counting based on arrangements.

In the expansion of $(\sum A_{i})^{2}$ , coefficients of $A_{i}$ would be $1$ , so it’s contribution would be “how many choices will this $A_{i}$ be included in, and from each we’ll have one $A_{i}^{2}$ term. This gets you to

$$\sum_i \binom{n-1}{k-1} A_i^2$$$

via a similar argument as $p = 1$ .

Now about the $A_{i} A_{j}$ case, well, what is it’s coefficient in the expansion above? it’ll be $2 A_{i} A_{j}$ . This $2$ is simply because I get one of $A_{i} A_{j}$ and one of $A_{j} A_{i}$ , so depending on how I count; using $i < j$ or $i \neq = j$ , you get get a different contribution count and it’s essential to not mix it up.

For a “set” as ${i, j}$ , how many times will this be in the $K$ choices? Well, you fix two and pick the rest in $(k - 2 n - 2)$ ways, note that since what I fixed was “set” I am working on the $i < j$ case. Put simply, if you ask is this $(k - 2 n - 2)$ to be counted separately for $A_{i} A_{j}$ or $A_{j} A_{i}$ and you would know it. I cannot write it better and those are the limits of my own writing. I think I understand it but this inability perhaps hints as something still left to be desired.

The contribution then is $(k - 2 n - 2) \sum_{i, j s . t . i \neq = j} A_{i} A_{j}$ or $2 (k - 2 n - 2) \sum_{i, j s . t . i < j} A_{i} A_{j}$

Both are obviously identical of course.

Focus on computing the pair product now. For this case, it’ll simply be $(\sum A_{i})^{2} - \sum A_{i}^{2} = 2 A_{1} A_{2} + 2 A_{1} A_{3} + ...$

I deliberaly did not write the RHS rigorously since this was the source of my error, which one of the above do I choose? Depening on what I choose, I may or may not get a factor of two.

Given that I’ve done the groundwork of highlight a possble gap, it’s obvious we choose the first one, since this is what you get as the pair product naturally.

Thus the whole solution, written in a way that’s computationally obvious to be $O (n)$ is

$(k - 1 n - 1) \sum_{i} A_{i}^{2} + (k - 2 n - 2) {(\sum A_{i})^{2} - \sum A_{i}^{2}}$

Solution 2 : choose one and recurse into $p = 1$

This is what I did, somewhat incorrectly too, but also leads to the same solution.

Difference only lies in the pair product contribution argument.

Say you choose an $A_{i}$ and fix it, then you can decompose $A_{i} A_{j}$ as $A_{i} \sum_{j \neq = i} A_{j}$

how many times would a certain $A_{j}$ occur in the inner sum? That’s $(k - 2 n - 2)$ . Where I made a mistake was also counting $A_{i}$ , missing the obvious sanity check that perhaps the terms are exploding too much with the double binomial product. When I write it this way, it’s clear that for each $A_{i}$ , I’ve applied the contribution handling inside od the summation.

Define

B_{i} S = (k - 2 n - 2) A_{i} = \sum B_{i}

then contribution of product terms for a give $A_{i}$ is $S - B_{i}$ . No need of additioanl coefficients as the $j$ s are all $\neq = i$ , for every $A_{i}$ , every product is handled too. The solution then is

$(k - 1 n - 1) \sum_{i} A_{i}^{2} + \sum_{i} A_{i} (S - B_{i})$

this cleverly skips the pair product but the first one is more straighforward to reach to.

$p = 3$

This is where I realise that what we’re working with are “partitions”. I’ll try not to repeat myself, just the new stuff.

Contribution of $A_{i}^{3}$ term is $(K - 1 N - 1) \sum_{i} A_{i}^{3}$ .

Contribution of $A_{i} A_{j} A_{k}$ term is $6 (K - 3 N - 3) \sum_{i < j < k} A_{i} A_{j} A_{k}$ Note that $6$ here is $3!$ , as by choosing we do not arrange, but the product will have that term repeated — see the parallels to multinomial.

$A_{i}^{2} A_{j}$ is where it starts to get tricky. Do we need a $A_{i} A_{j}^{2}$ ? No, if you are under $i \neq = j$ .

Notice that here the terms for $(i, j) \neq = (j, i)$ , the equation is not symmetric. It’s easier to work with an example.

$(a + b)^{3} = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3}$

it’s simply that we are doing it differently for THIS case by working under a $\neq =$ regime for the second term.

For calulating those products now, define $P_{1} = \sum_{i} A_{i}, P_{2} = \sum_{i} A_{i}^{2}, P_{3} = \sum_{i} A_{i}^{3}$

Now if you go via a similar way as I did in my solution $2$ , for case $2$ . $\sum_{i \neq = j} A_{i}^{2} A_{j} = \sum_{i} A_{i}^{2} (P_{1} - A_{i}) = P_{1} \sum_{i} A_{i}^{2} - \sum_{i} A_{i}^{3} = P_{1} P_{2} - P_{3}$

$6 \sum_{i < j < k} A_{i} A_{j} A_{k} = P_{1}^{3} - 3 (P_{1} P_{2} - P_{3}) - P_{3} = P_{1}^{3} - 3 P_{1} P_{2} + 2 P_{3}$

these above are also known as Newton’s identities as well where he tried to relate power sums to such $P_{i}$

Combining it all, you get to.

(K - 1 N - 1) P_{3} + 3 (K - 2 N - 2) (P_{1} P_{2} - P_{3}) + (K - 3 N - 3) (P_{1}^{3} - 3 P_{1} P_{2} + 2 P_{3})

$p = P$

There is a pattern here, and it’s possble to generalise.

Multinomial theorem for $(\sum A_{i})^{P}$ gives you this for a single monomial.

\frac{P !}{e _{1} ! e _{2} ! \dots e _{r} !} A_{i_{1}}^{e_{1}} A_{i_{2}}^{e_{2}} \dots A_{i_{r}}^{e_{r}}, e_{1} + \dots + e_{r} = P .

Note that even though the maths works out for the monomial above, to find out how many of such terms exist we contrain to $e_{r} > 0$ and work out solutions of $e_{1} + \dots + e_{r} = P$ .

First the binomial coefficient, for an $A_{i}$ to be chosen it means it’s multiplicitiy is $> 0$ i.e. $e_{r} > 0$ For a term where some set of balls are already chosen, and we wish to find how many times this set will occur, exclude $r = co u n t o fd i s t in c t c h ose n$ ( reusng r here ) and get to

(K - r N - r)

Arranging them for the number of times that product occurs ( it’s coeffiecient in the multinomial ) gives you

\frac{P !}{e _{1} ! e _{2} ! \dots e _{r} !}

One such term would be adding this to the score

A_{i_{1}}^{e_{1}} A_{i_{2}}^{e_{2}} \dots A_{i_{r}}^{e_{r}}

And we want all such terms where

e_{1} + \dots + e_{r} = P, e_{i} > 0

Combining all this gets you to

e_{1} + \dots + e_{N} = P e_{i} \geq 0 \sum (K - r ( e ) N - r ( e )) \frac{P !}{e _{1} ! e _{2} ! \dots e _{N} !} i = 1 \prod N A_{i}^{e_{i}}

where $r (e) = ∣ {i : e_{i} > 0} ∣$

Appendix: relation to Sterling numbers

P distinct balls into r identical boxes, with no box empty is ${r P}$ .

In my case, the boxes are not identical so need to arrange by $r!$ , both these are same

e_{1} + \dots + e_{r} = P e_{j} > 0 \sum \frac{P !}{e _{1} ! \dots e _{r} !} = r! {P r} .

Well, I mean this relation and it’s mention here does not bring much to the table here.

Lest I Forget