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

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.

• See section 5 of Tanya Khovanova and Joshua Xiong, "Nim Fractals", arxiv.org/abs/1405.5942, in particular Theorem 27. – Michael Lugo Jan 10 at 20:22
• @MichaelLugo Thanks, that's pretty good. It only gives $n$ even though. – Timon Knigge Jan 10 at 21:32
• Aha, but if $n \equiv 1 \mod 2$ then there is an odd number of odd sized piles and the nim sum is never $0$. – Timon Knigge Jan 10 at 21:36

## 1 Answer

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$$.

• One can use binary doubling (as in squaring by exponentiation) to get this to $O(n^3 \log k)$. Still very slow though. – Timon Knigge Jan 10 at 20:15