cp's OEIS Frontend

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

%I A372871 #36 Jul 07 2025 10:21:33
%S A372871 0,1,2,10,28,126,236,1716,4376,24310,71452,352716,1036432,5200300,
%T A372871 15661088,77558760,234338224,1166803110,3538500140,17672631900,
%U A372871 53754680928,269128937220,811847006192,4116715363800,12392037943040,63205303218876,190668639444376
%N A372871 Number of compositions of n into n nonnegative parts such that their xor-sum is not zero.
%C A372871 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.
%H A372871 Alois P. Heinz, <a href="/A372871/b372871.txt">Table of n, a(n) for n = 0..350</a>
%H A372871 C. L. Bouton, <a href="https://www.jstor.org/stable/1967631">Nim, A Game with a Complete Mathematical Theory</a>, Annals of Mathematics, Second Series, vol. 3 (1/4), 1902, 35-39.
%F A372871 a(n) = A088218(n) if n is odd.
%e A372871 For n=2 the a(2)=2 solutions are:  {0,2}, {2,0}.
%e A372871 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}.
%p A372871 b:= proc(n, i, t) option remember; `if`(n=0, signum(t),
%p A372871       add(b(n-j, i-1, Bits[Xor](j, t)), j=`if`(i=1, n, 0..n)))
%p A372871     end:
%p A372871 a:= n-> b(n$2, 0):
%p A372871 seq(a(n), n=0..32);  # _Alois P. Heinz_, May 15 2024
%t A372871 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}]];
%t A372871 a[n_] := b[n, n, 0];
%t A372871 Table[a[n], {n, 0, 32}] (* _Jean-François Alcover_, Jul 07 2025, after _Alois P. Heinz_ *)
%Y A372871 Cf. A048833, A088218, A233810.
%K A372871 nonn
%O A372871 0,3
%A A372871 _Anna Ledworowska_, May 15 2024