Does Stars and Bars or the binomial coefficient represent binary sequences?

318 Views Asked by At

Does Stars and Bars or the binomial coefficient represent binary sequences?

With the binomial coefficient we can calculate all the paths on a grid with moving up or right, that's like defining up to be $1$ and right to be $0$, so the binomial coefficient gives the amount of binary sequences of size $nk$ (?)

With Stars and Bars, by defining the stars to be zeros and bars to be ones, does it tell anything about a binary sequence?

3

There are 3 best solutions below

0
On BEST ANSWER

If a binary sequence is a sequence of digits selected from $\{0,1\}$, then the binomial coefficient $\binom nk$ is the number of binary sequences of exactly $n$ digits that contain exactly $k$ zeros.

"Stars and bars" is generally applied when we want to put a number of indistinguishable items into a number of identified bins, or in problems equivalent to that. The digits of a binary sequence are distinguishable, but of only two kinds, so it's hard to see a good application of stars and bars there.

Of course "stars and bars" itself evaluates to a binomial coefficient, which one could apply to binary sequence as already shown, but it's not clear why one would call this "stars and bars".

1
On

The binomial coefficient gives the number of lattice paths to a fixed point, not those of a fixed length. There are $2^n$ lattice paths or binary sequences of length $n$; there's no need for either binomial coefficients or stars and bars.

0
On

The coefficient ${n \choose k}$ counts the number of binary sequences of length $n$ with exactly $k$ $0$'s (or, exactly $k$ $1$'s, if you prefer).

I can't see stars and bars being inherently useful for binary sequences, but I could be wrong. They're binomial coefficients as well, but why the number of (non-negative integer) solutions to $x_1 + x_2 + x_3 = 5$ should count the number of sequences of length $7$ with exactly $2$ zeros seems less obvious to me.