- FindStat

edit this statistic or download as text // json

Identifier

St000137: Integer partitions ⟶ ℤ

Values

[1] => 1

[2] => 0

[1,1] => 0

[3] => 1

[2,1] => 1

[1,1,1] => 1

[4] => 0

[3,1] => 0

[2,2] => 2

[2,1,1] => 0

[1,1,1,1] => 0

[5] => 1

[4,1] => 1

[3,2] => 1

[3,1,1] => 1

[2,2,1] => 1

[2,1,1,1] => 1

[1,1,1,1,1] => 1

[6] => 0

[5,1] => 0

[4,2] => 0

[4,1,1] => 0

[3,3] => 2

[3,2,1] => 0

[3,1,1,1] => 0

[2,2,2] => 2

[2,2,1,1] => 0

[2,1,1,1,1] => 0

[1,1,1,1,1,1] => 0

[7] => 1

[6,1] => 1

[5,2] => 1

[5,1,1] => 1

[4,3] => 1

[4,2,1] => 1

[4,1,1,1] => 1

[3,3,1] => 3

[3,2,2] => 3

[3,2,1,1] => 1

[3,1,1,1,1] => 1

[2,2,2,1] => 1

[2,2,1,1,1] => 1

[2,1,1,1,1,1] => 1

[1,1,1,1,1,1,1] => 1

[8] => 0

[7,1] => 0

[6,2] => 0

[6,1,1] => 0

[5,3] => 0

[5,2,1] => 0

[5,1,1,1] => 0

[4,4] => 0

[4,3,1] => 0

[4,2,2] => 2

[4,2,1,1] => 0

[4,1,1,1,1] => 0

[3,3,2] => 0

[3,3,1,1] => 2

[3,2,2,1] => 0

[3,2,1,1,1] => 0

[3,1,1,1,1,1] => 0

[2,2,2,2] => 0

[2,2,2,1,1] => 0

[2,2,1,1,1,1] => 0

[2,1,1,1,1,1,1] => 0

[1,1,1,1,1,1,1,1] => 0

[9] => 1

[8,1] => 1

[7,2] => 1

[7,1,1] => 1

[6,3] => 1

[6,2,1] => 1

[6,1,1,1] => 1

[5,4] => 1

[5,3,1] => 1

[5,2,2] => 3

[5,2,1,1] => 1

[5,1,1,1,1] => 1

[4,4,1] => 2

[4,3,2] => 1

[4,3,1,1] => 1

[4,2,2,1] => 1

[4,2,1,1,1] => 1

[4,1,1,1,1,1] => 1

[3,3,3] => 2

[3,3,2,1] => 1

[3,3,1,1,1] => 3

[3,2,2,2] => 2

[3,2,2,1,1] => 1

[3,2,1,1,1,1] => 1

[3,1,1,1,1,1,1] => 1

[2,2,2,2,1] => 1

[2,2,2,1,1,1] => 1

[2,2,1,1,1,1,1] => 1

[2,1,1,1,1,1,1,1] => 1

[1,1,1,1,1,1,1,1,1] => 1

[10] => 0

[9,1] => 0

[8,2] => 0

[8,1,1] => 0

[7,3] => 0

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The Grundy value of an integer partition.
Consider the two-player game on an integer partition.
In each move, a player removes either a box, or a 2x2-configuration of boxes such that the resulting diagram is still a partition.
The first player that cannot move lose. This happens exactly when the empty partition is reached.
The grundy value of an integer partition is defined as the grundy value of this two-player game as defined in [1].
This game was described to me during Norcom 2013, by Urban Larsson, and it seems to be quite difficult to give a good description of the partitions with Grundy value 0.

References

[1] wikipedia:Sprague–Grundy_theorem

Code

(* This is the Mathematica code for computing the Grundy value of a partition. *)


GetChildren[part_] := Module[{n, onePieceMoves, fourPieceMoves},
   n = Length[part];
   (* Get partitions reachable when removing one box. *)
   
   onePieceMoves = Table[
     If[i == n || part[[i + 1]] < part[[i]],
      ReplacePart[part, i -> part[[i]] - 1],
      Sequence @@ {}],
     {i, n}];
   
   (* Get partitions reachable when removing a 2x2 square of boxes. *)

      fourPieceMoves = Table[
     If[part[[i]] >= 2 && 
       part[[i + 1]] == 
        part[[i]] && (i == n - 1 || 
         part[[i + 1]] >= 2 + part[[i + 2]]),
      ReplacePart[
       part, {i -> part[[i]] - 2, i + 1 -> part[[i + 1]] - 2}],
      Sequence @@ {}],
     {i, n - 1}];
   Return[
    Select[#, Positive] & /@ Join[onePieceMoves, fourPieceMoves]];
   ];


Grundy[{}] := 0;
Grundy[part_] := 
  Grundy[part] = With[{gset = Grundy /@ GetChildren[part]},
    Min@Complement[Range[0, Max[gset] + 1], gset]];

(* Now, Grundy[{3,2,1}] returns the Grundy value for the partition {3,2,1} *)

(* The following code generates the statistics above. *)
ip = Flatten[IntegerPartitions /@ Range[17], 1];
data = "[" <> StringJoin @@ Riffle[ToString /@ #1, ","] <> "]=>" <> 
     ToString[Grundy@#1] & /@ ip;
StringJoin @@ Riffle[data, "\n"]

Created

Jun 20, 2013 at 19:29 by Per Alexandersson

Updated

Dec 29, 2016 at 09:10 by Christian Stump