Can Stars and bars method be used with constraints on the number of Stars?

1.2k Views Asked by At

Question : I wanted to find out the number of ways all the 7 numbers below could be assigned positive integers which can sum up to 42.$$x_1+x_2+x_3+x_4+x_5+x_6+x_7=42$$

the catch in this problem is the constraint $$ 1\le x_i\le26$$ The Stars and bars method happen to only provide solution for, if the $x_i$ should be non-negative or only positive.

My Approach : Since i need only positive integers to be used here for $x_i$, so i have to use $${n - 1\choose k-1}.$$ but in using the formulae directly, definitely it would also count the ways where a certain $x_i>26$, so i thought i should use it this way, as $k=7=1+6=2+5=...=6+1$ and $n=42=26+16$, so i can select a few stars from 26 stars as well as 16 stars at the same time : $$({26-1\choose 1-1} + {16-1\choose 6-1}) + ({26-1\choose 2-1} + {26-1\choose 5-1}) + .......+ ({26-1\choose 6-1} + {16-1\choose 1-1})$$ so that highest value $x_i$ can achieve is 26.

My problem : I actually don't know if my way is correct or if any other such method exists to use stars and bars method where also constraints on number of stars are included. Thank you.

1

There are 1 best solutions below

0
On BEST ANSWER

Well, it is not difficult to tweak the idea behind the analytic-combinatorics formulation of the stars and bars method. By denoting through $[x^n]\,f(x)$ the coefficient of $x^n$ in the Taylor series at the origin of $f(x)$, stars and bars tells us that the cardinality of the set $$E=\{(x_1,\ldots,x_7)\in\mathbb{N}^*\times\ldots\times\mathbb{N}^+: x_1+\ldots+x_7=42\}$$ equals $\binom{41}{6}$, which is $$[x^{42}]\left(x+x^2+x^3+\ldots\right)^{7} = [x^{42}]\frac{x^7}{(1-x)^7} = [x^{35}]\frac{1}{(1-x)^7}.$$ In a similar way, the cardinality of the set $$F=\{(x_1,\ldots,x_7)\in[1,26]^7: x_1+\ldots+x_7=42\}$$ equals $$[x^{42}](x+x^2+\ldots+x^{25}+x^{26})^7 = [x^{35}]\frac{(1-x^{26})^7}{(1-x)^7}$$ and by applying the binomial theorem to $(1-x^{26})^7$ we get that the RHS is $$ [x^{35}]\frac{1}{(1-x^7)}-7\cdot[x^9]\frac{1}{(1-x)^7}=\color{red}{\binom{41}{6}-7\cdot\binom{15}{6}}.$$ A combinatorial interpretation is simple: if an element belongs to $E$ but not to $F$, at most one of its coordinates is $\geq 27$.