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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.