A372871 Number of compositions of n into n nonnegative parts such that their xor-sum is not zero.

0, 1, 2, 10, 28, 126, 236, 1716, 4376, 24310, 71452, 352716, 1036432, 5200300, 15661088, 77558760, 234338224, 1166803110, 3538500140, 17672631900, 53754680928, 269128937220, 811847006192, 4116715363800, 12392037943040, 63205303218876, 190668639444376

Offset: 0

Author

Anna Ledworowska, May 15 2024

Keywords

• nonn

Comments

Number of starting configurations of Nim such that the 1st player wins, and the configurations are of the form {x_1, x_2, ..., x_n}, where x_i is the number of pieces on i-th stack (x_i>=0), and the sum of all pieces is n.

Examples

			For n=2 the a(2)=2 solutions are:  {0,2}, {2,0}.
For n=3 the a(3)=10 solutions are: {0,0,3}, {0,1,2}, {0,2,1}, {0,3,0}, {1,0,2}, {1,1,1}, {1,2,0}, {2,0,1}, {2,1,0}, {3,0,0}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..350
• C. L. Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics, Second Series, vol. 3 (1/4), 1902, 35-39.

Crossrefs

Cf. A048833, A088218, A233810.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n=0, signum(t),
      add(b(n-j, i-1, Bits[Xor](j, t)), j=`if`(i=1, n, 0..n)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..32);  # Alois P. Heinz, May 15 2024

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0, Sign[t], Sum[b[n-j, i-1, BitXor[j, t]], {j, If[i == 1, n, 0], n}]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jul 07 2025, after Alois P. Heinz *)

Formula

a(n) = A088218(n) if n is odd.