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

1, 1, 7, 226, 2059, 20926, 315646, 4397212, 66201971, 999067510, 15168583482, 240202475668, 3731763898510, 57290627029676, 887861389544668, 13713341876387776, 210889953761225667, 3248614469788303782, 50091681144815341810, 772966100038376636332

Offset

0,3

Comments

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

Links

Table of n, a(n) for n=0..19.

C. L. Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics, Second Series, vol. 3 (1/4), 1902, 35-39.

Formula

a(n) = A088218(2n) - A372871(2n).

a(n) mod 2 = 1 <=> n in { A131577 }.

Example

For n=1 the a(1)=1 solution is {1,1}.
For n=2 the a(2)=7 solutions are {0,0,2,2}, {0,2,0,2}, {0,2,2,0}, {1,1,1,1}, {2,0,0,2}, {2,0,2,0}, {2,2,0,0}.

Maple

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

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1-Sign[t],
   Sum[b[n-j, i-1, BitXor[j, t]], {j, If[i == 1, {n}, Range[0, n]]}]];
a[n_] := b[2n, 2n, 0];
Table[a[n], {n, 0, 23}] (* _Jean-François Alcover_, May 30 2024, after _Alois P. Heinz_ *)

Crossrefs

Cf. A088218, A131577, A372871, A048833, A233810.

Sequence in context: A210099 A193503 A303533 * A142606 A123832 A093167

Adjacent sequences: A372964 A372965 A372966 * A372968 A372969 A372970

Keyword

nonn

Author

_Anna Ledworowska_, May 18 2024

Extensions

More terms from _Alois P. Heinz_, May 22 2024

Status

approved