Counting $k$-sets with sum $n$ and xor-sum $0$.

126 Views Asked by At

Given $k, n > 0$, how many ordered lists $a_1, a_2, \dots, a_k$ are there such that $a_i \geq 0$ for all $i$, such that $\sum_i a_i = n$ and $\oplus_i a_i = 0$, where the latter operation denotes bitwise xor (i.e. $15 \oplus 3 = 12$).

It is likely there is no closed-form expression, in that case a reasonably fast algorithm would also be interesting.

EDIT: Context: this is the number of losing starting positions in a game of Nim with $k$ initial piles containing a total of $n$ stones.

1

There are 1 best solutions below

1
On

Let $F(n,k,x)$ denote the amount of ordered lists $a_1,...,a_k$ such that $a_i\geq0$, $\sum a_i=n$ and $\oplus a_i=x$. Then considering all possible values of $a_k$ we find the recursive formula $$F(n,k,x)=\sum_{i=0}^nF(n-i,k-1,x\oplus i).$$ This gives us an $\mathcal{O}(n^3k)$ time algorithm. Not very fast, but at least polynomial in $n$ and $k$.