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,3

Comments

Number of starting configurations of Nim such that the 1st player wins, and the configurations are in 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.

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.

Formula

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

Example

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

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

Crossrefs

Cf. A048833, A088218, A233810.

Sequence in context: A371943 A106184 A327696 * A076438 A203551 A344791

Adjacent sequences: A372865 A372867 A372868 * A372872 A372873 A372874

Keyword

nonn

Author

Anna Ledworowska, May 15 2024

Status

approved