1
$\begingroup$

How many ways are there of sum $\frac{n(n+1)}{2}$ with $n$ addends? Knowing than $i$ appears at most $n+1-i$ times.

I really haven't had any important ideas. When speaking of a fixed number of addends, we leave out the partitions of a number. How can I proceed; any suggestions?

$\endgroup$
2
$\begingroup$

Let $N=\frac{n(n+1)}{2}$. We know that $$N=\sum_{i=1}^{N}1=1+1+...+1$$

Notice that in this expression there are $N$ "ones" and $(N-1)$ "plus signs". Then we can choose $n-1$ "plus signs" to keep fixed, and collapse the rest by computing the sums (see at bottom for an example). The number of ways to do this is $${ N-1\choose n-1}={ \frac{n(n+1)}{2} - 1\choose n-1}$$ Note this does not adjust for repetition.. so for example $1+2$ and $2+1$ would be distinct

To adjust for repetition you can build off this answer.


Example: Say we want to write 4 as a sum of 2 numbers. Then $$4=1+1+1+1$$ which has 3 "plus signs". we can fix the first, second or third plus sign, and collapse the non-fixed ones like so: $$(1)\underline{+}(1+1+1) =1+3$$ $$(1+1)\underline{+}(1+1) =2+2$$ $$(1+1+1)\underline{+}(1) = 3+1$$

$\endgroup$
1
$\begingroup$

HINT

It is not clear whether you are considering the Partitions or Compositions of $s=\binom{n+1}{2}$.
In the first case we have the $n$ addenda ordered non-decreasingly (or non-increasingly).
The corresponding generating function is clearly $$ \eqalign{ & P(x,n) = \cr & = \left( {1 + x} \right)^n \left( {1 + x^{\,2} } \right)^{n - 1} \cdots \left( {1 + x^{\,n - 1} } \right)^2 \left( {1 + x^{\,n} } \right)^1 = \cr & \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)^{n + 1 - k} } \cr} $$

In the second case the addenda are $n$-tuples (vectors), where the order matters. The generating function is then $$ \eqalign{ & Q(x,n) = \cr & = \left( {x + x^{\,2} + \cdots + x^{\,n} } \right)\left( {x + x^{\,2} + \cdots + x^{\,n - 1} } \right)\; \cdots \;x \cr & = x^{\,n} \prod\limits_{k = 1}^n {\left( {{{1 - x^{\,k} } \over {1 - x}}} \right)} = \left( {{x \over {1 - x}}} \right)^{\,n} \prod\limits_{k = 1}^n {\left( {1 - x^{\,k} } \right)} \cr} $$

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