# How many ways are there to arrange a number $n$ on a binary abacus?

In a binary abacus, each column holds a number of beads equivalent to the place-value of that column. So, assuming you have a four-bit abacus, the leftmost column would hold 8 beads, and the rightmost column would hold 1 bead. Here is a quick video for further explanation: https://www.youtube.com/watch?v=okF9_LzkMi4. Given the number of bits, or columns, in such a system, is there a way to find the number of ways $$n$$ beads could be placed among the columns. For example, if you have 1 bead (representing the number 1), there would be 4 ways to place it among the 4 columns in the 4-bit abacus. I found a way to represent the constraints of the system:

$$1 \le n \le 15$$

$$0 \le x \le 8$$

$$0 \le y \le 4$$

$$0 \le z \le 2$$

$$0 \le w \le 1$$

$$x + y + z + w =$$n

where $$n$$, $$x$$, $$y$$, $$z$$, $$w$$ are integers and $$x$$, $$y$$, $$z$$, $$w$$ represent the number of beads in each column from left to right.

Is there a concrete formula that can solve such a problem?

• That's an... interesting device to call an "abacus" - what kind of arithmetic can you do on it? It's more of a converter than an abacus. Pretty neat idea though, but a true binary abacus looks something like this. Those actually pair really well together though! If you're trying to teach someone to do math on a binary abacus, converting decimal numbers to and from binary isn't really obvious until after you're at least a little fluent in binary, so this converter would be a great teaching aid! Commented May 25, 2022 at 6:45

It's the coefficient of $$x^n$$ in \begin{align} &(1+x)(1+x+x^2)(1+x+\cdots+ x^4)(1+x+\cdots+ x^8)\\&=\frac{1-x^2}{1-x}\frac{1-x^3}{1-x}\frac{1-x^5}{1-x}\frac{1-x^9}{1-x}\\ &=(1-x^2)(1-x^3)(1-x^5)(1-x^9)(1-x)^{-4} \end{align}

Now you can multiply out the first four terms, and expand the fifth term up through $$x^{15}$$ term and you'll have an effective formula, though it will still be tedious to compute by hand.

EDIT

Just for grins, I wrote a python script to do the calculations described above:

from sympy import poly, binomial
from sympy.abc import x

p = poly((1-x**2)*(1-x**3)*(1-x**5)*(1-x**9))
q= poly(sum(binomial(n+3,3)*x**n for n in range(16)))
r = p*q
c = r.all_coeffs()[-16:]
print(c)


This printed

[1, 4, 9, 15, 21, 26, 29, 30, 30, 29, 26, 21, 15, 9, 4, 1]


I might explain that all_coeffs returns a list of the coefficients, with the most significant first, so we want the last $$16$$ in the list.

• This appears to be the formula for finding the coefficients in the pyramid above. Thank you! Commented Mar 29, 2020 at 1:23
• Yes, and I'm sure if you multiplied the polynomials out, you'd get the formula in joriki's answer. Commented Mar 29, 2020 at 1:34

You can do this using balls in bins with limited capacity, but it’s a bit cumbersome due to the different capacities.

You have $$4$$ columns with capacities $$c_j=2^j$$ for $$0\le j\le3$$. The general expression for the number of ways to put $$n$$ beads on $$m$$ columns with capacities $$c_j$$ is, by inclusion–exclusion,

$$\sum_{S\subseteq B}(-1)^{|S|}\binom{m+n-1-\sum_{j\in S}(c_j+1)}{m-1}\;,$$

where $$B$$ is the set of columns and $$S$$ runs over all its subsets. Here, contrary to the usual convention, the binomial coefficient is taken to be zero if the upper index is negative.

In the present case, we can associate the subsets $$S_\ell$$ of the set of columns with the numbers $$\ell$$ whose binary representations they correspond to. Denote the number of $$1$$s in the binary representation of $$\ell$$ by $$e(\ell)$$. Then

$$\sum_{j\in S_\ell}(c_j+1)=\ell+e(\ell)\;,$$

so the sum becomes (with $$m=4$$):

$$\sum_{\ell=0}^{15}(-1)^{e(\ell)}\binom{n-\ell-e(\ell)+3}{3}\;.$$

(Note that while under the usual convention this would be a polynomial of degree $$3$$ in $$n$$, that’s not the case here because of the above zero convention; which terms are cut off by this depends on $$n$$.)

With some figuring out of bit counts we obtain

$$\binom{n+3}3-\binom{n+1}3-\binom n3+\binom{n-2}3-\binom{n-2}3+\binom{n-4}3+\binom{n-5}3-\binom{n-7}3-\binom{n-6}3+\binom{n-8}3+\binom{n-9}3-\binom{n-11}3+\binom{n-11}3-\binom{n-13}3-\binom{n-14}3+\binom{n-16}3\;,$$

and you can check that this reproduces the numbers in the OEIS entry given in Nick Matteo’s answer.

Note that the count is symmetric under $$n\to15-n$$, as arranging $$n$$ beads is like arranging $$15-n$$ missing beads. So you really only need this formula up to $$n=7$$, where it simplifies to

$$\binom{n+3}3-\binom{n+1}3-\binom n3+\binom{n-4}3\;,$$

and you can get the other half of the counts by reflection.

• Could you please explain what the set $B$ contains? Also, what is the function s(t,j) from the original equation? Lastly, what is inclusion–exclusion? Sorry in advance if these seem like rookie questions, but it's been a while since I've seen set theory stuff. Commented Mar 29, 2020 at 2:40
• @AlexBandy: I added a link to the Wikipedia article for inclusion–exclusion. (You may also want to look at this answer for an insightful perspective on this principle.) $B$ is the set of (indices of) columns / bins, in your case $\{0,1,2,3\}$, with the capacity of column $j$ given by $c_j=2^j$. Later I label the subsets $S_\ell$ of $B$ by the numbers $\ell$ they represent in binary, so e.g. the subset $\{0,2\}\subset B$ of columns is $S_5$, since $5=101_2$. Commented Mar 29, 2020 at 6:39
• @AlexBandy: The way that page uses $s(t,j)$ is a bit confusing. $t$ is the size of the subset, $j$ is an index for the $\binom mt$ subsets of size $t$, and $s(t,j)$ is the sum over the capacity-plus-one of the bins in the $j$-th subset of size $t$. I find it clearer to write the sum as I did, with a single sum summing over all subsets $S$, with $|S|$ corresponding to $t$ and $\sum_{j\in S}(c_j+1)$ corresponding to $s(t,j)$. (The two $j$s are different there; perhaps I should have used a different index.) Commented Mar 29, 2020 at 6:44
• @AlexBandy: I added a symmetry consideration at the end of the answer that considerably simplifies the result. Commented Mar 29, 2020 at 6:55
• I finally got it now! I agree that condensing the expression into one summation makes it easier to understand. s(t, j) isn't very helpful. Commented Mar 30, 2020 at 2:52

Well, it's OEIS sequence A131791, which is a triangle beginning $$1\\ 1, 1\\ 1, 2, 2, 1\\ 1, 3, 5, 6, 6, 5, 3, 1\\ 1, 4, 9, 15, 21, 26, 29, 30, 30, 29, 26, 21, 15, 9, 4, 1\\ 1, 5, 14, 29, 50, 76, 105, 135, 165, 194, 220, 241, 256, 265, 269, 270, \dotsc$$ where the $$n$$th row (starting from row 0) has $$2^n$$ entries, showing the number of ways to put 0 up to $$2^n - 1$$ beads on the $$n$$-column binary abacus.

Comments on that sequence show what's known as far as formulas. A notable one: the $$k$$th entry in each row is the sum of the first $$k$$ entries in the row above, up to the midpoint, and then the entries repeat in reverse order.