Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I came across the following combinatorial question and lost my way, wonder if you can assist ??? I think it might be a sub case of a multi-binomial theorem, maybe more related to set/multiset theorem.

I have 2 variables for example assume {a,b}

I have n parentheses and r locations in each parentheses - inside each parentheses variables are summed and the parentheses are are multiplied with each other.

example of n = 3 , r = 3 - ( _ + _ + _ ) * (_ + _ + _ ) * (_ + _ + _ )

since {a.b} are just 2 variables, this mean it can be repeated many times within the parentheses.

I made some progress that you might be able to see in this example - I will spread here all options for r=2, n=2 :
{a+a} * {a+a} * 1 +
{b+b} * {b+b} * 1 +
{a+b} * {a+a} * 4 + ( 4 due to {a+b} * {a+a} = {b+a} * {a+a} = {a+a} * {b+a} = {a+a} * {a+b} )
{a+b} * {b+b} * 4 +
{a+b} * {a+b} * 4 +
{a+a} * {b+b} * 2

for any n, r variable a variable b - I would like to find a formula that generate the sum of all possible options.

Some progress I made is the following -
$ \sum_{x1=0}^r(x1*a+(r-x1)*b)$ stands for all possible sums within a single parentheses.
if I would like to add to it the number of occurrences it will be as follows $ \sum_{x1=0}^r(x1*a+(r-x1)*b) * {r \choose x1} $
This now should be multiplied n times based on the number of repetitions, I feel I am getting closer...

Thanks for the corrections, hope now it will be clearer. I am not a native English speaker, and would appreciate further corrections if needed. Thanks, Ran.

share|cite|improve this question
"variable a variable a": you probably mean "variable a variable b". Also, when you say "I can just spread ... save", maybe it is just me, but I don't understand. Maybe you could try to reformulate? – gnometorule Jan 28 '13 at 21:14
Further suggestion: By "are multiple of one another", do you mean "are multiplied with each other"? That's what the formula seems to say. Apart from correcting the formulations, the main thing that you don't seem to have addressed at all is what you consider repetitions and what you consider inequivalent expressions that you're trying to count. For instance, can the same variable occur twice within a parenthesis? Does the order of the summands in a parenthesis matter? Does the order of the parentheses matter? – joriki Jan 28 '13 at 21:16
Thanks for your comments, I edited my question, hope it is clearer now. – Ran Jan 29 '13 at 16:57
Permission to use this to tortu^Wenlighten my students? – vonbrand Feb 1 '13 at 19:23
Sure. feel free. – Ran Feb 3 '13 at 10:25

Let there be $r$ summands in each factor, and $s$ factors in all. If the operators are all conmutative and associative, then there are exactly $r + 1$ possible values for each factor (0 times $a$, 1 time $a$, ..., $r$ times $a$). Now we have $r + 1$ possible factors, and we want to know how many integer solutions the equation $x_1 + x_2 + \ldots x_{r + 1} = s$ has, where $0 \le x_i$. Representing each $x_i$ as a sequence of $*$, this means splitting a string of $s$ times $*$ by placing $|$ in it $r$ times . This is distributing $r$ bars over $r + s$ places, and that can be done in $\binom{r + s}{r}$ ways.

share|cite|improve this answer
I'm sorry, renamed $n$ as $s$ (for companionship to $r$). – vonbrand Feb 3 '13 at 15:48

Denote the requested sum by $S(n,r)$, with a tacit dependence on $a$ and $b$. I claim that $$S(n,r)=\bigl( r 2^{r-1}(a+b)\bigr)^n\qquad(n\geq0,\ r\geq1)\ .\tag{1}$$ Proof. $\ S(0,r)$ is the empty product and has the value $1$. Therefore assume that $(1)$ is true for $n$. The sum $S(n,r)$ is a sum of a great many terms $T_\iota$ (in fact $2^{nr}$ of them, see below). Each $T_\iota$ consists of $n$ factors, each of the latter being an $r$-nom. Each such $T_\iota$ now gets an additional factor of the form $$(x_1+x_2+\ldots x_r),\qquad x_k\in\{a,b\}\quad(1\leq k\leq r)$$ to the right.

Such factors can be set up in the following way: Choose a $j$ with $0\leq j\leq r$, then choose $j$ places in $[r]$ with $x_k=a$, and at the remaining $r-j$ places take $x_k=b$. The factor built in this way has value $ja+(r-j)b$. For given $j$ this can be done in ${r\choose j}$ ways. It follows that the sum of all the factors so generated is $$\sum_{j=0}^r{r\choose j}\bigl(ja+(r-j)b\bigr)=(a+b)\sum_{j=0}^r{r\choose j} j= r2^{r-1}(a+b)\ .$$ From this we conclude that each term $T_\iota$ in $S(n,r)$ gives rise to $2^r$ terms in $S(n+1,r)$, and that the sum of these terms is $r2^{r-1}(a+b)\cdot T_\iota\ $. Altogether we obtain $(1)$ with $n+1$ in place of $n$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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