How to get the bar and star formula?

HINT: Bars are identical. So they cannot switch places among themselves.


A less complicated method would be to consider that the number of solutions to $$x_1+x_2+...+x_k=n$$ in positive integers is the same as the number of solutions to $$(x_1+1)+(x_2+1)+...+(x_k+1)=n$$ in non-negative integers That's just solving $$x_1+x_2+...+x_k=n-k$$ using the normal stars and bars method.

Also, I'd like to suggest a different way of thinking about the combination operation that can make your arguments much easier to understand. $\binom{n}{k}$ represents the number of $k$-element subsets from a set of $n$ elements. Let me apply that reasoning to this problem to show you how much easier it is to solve.

In this case, we need to find the number of ways to sort $n-k$ stars and $k-1$ bars into $n-1$ slots. So all we're doing is choosing which $n-1$ slots to put the $k-1$ bars into. Rather than do that one at a time, we can just say, bang, that number is $\binom{n-1}{k-1}$ by what the definition of the binomial coefficient. Avoiding juggling factorials is a great strategy for improving your day!

Tags:

Combinatorics

Related

Show that $\left\vert\frac{\pi}{4} - \left(1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9}\right)\right\vert < 0.1$ Computing $(A\otimes I + I \otimes A)^{-1} \text{vec}B$ Prove that $A= \left\lbrace f \in X: \int_0^1f(x) dx>1 \right\rbrace$ is an open set in $(X,d)$. Limits and Continuity in Multi variable calculus. Proof verification: if $W_1 \subseteq W_2$ then $\dim(W_1) \le \dim(W_2)$ Providing divisibility condition given fraction identity Minimising expression with absolute values tangent inequality in triangle Show that the only endomorphism $\phi$ of $\mathbb{Z}_7 \times \mathbb{Z}_7$ satisfying $\phi^5 = \text{id}$ is the identity. Solving $e^{ix}=i$ What is the general solution of this equation :$2^x 3^y+1=7^z$ with $x, y , z$ are integers? Necessary condition of changing signs of a divergent series $\sum_{n=1}^{\infty}p_{n}$ to make it convergent,$p_{n}$ decreases and tends to $0$.

Recent Posts