A237980 Array: row n gives the number of distinct square partitions of n; see Comments.

1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 13, 15, 18, 21, 25, 28, 32, 36, 44, 49, 60, 66, 80, 89, 103, 115, 132, 147, 168, 188, 212, 236, 269, 301, 344, 385, 437, 485, 549, 606, 678, 751, 837, 926, 1031, 1133, 1263, 1389, 1541, 1696, 1889, 2068, 2306, 2529

Offset: 1

Author

Clark Kimberling and Peter J. C. Moses, Feb 25 2014

Keywords

• nonn
• tabf
• easy

Comments

Suppose that p is a partition of n. Let m X m be the size of its Ferrers matrix, f(p), defined at A237981. Then f(p) consists of ceiling(m/2) concentric squares, where the innermost square is a single point if m is odd. The square partition of p is introduced here as the partition [x(1), x(2), ..., x(k)], where x(i) is the number of 1s in the i-th concentric square, where the squares are taken in order starting with the outermost.

Examples

			The 7 square partitions of 12 are as follows: [12], [11,1], [10,2], [9,3], [8,3,1], [8,4], [7,4,1]. The Ferrers matrix of the partition [4,3,3,1,1] of 12 is shown here:
1 . 1 . 1 . 1 . 0
1 . 1 . 1 . 0 . 0
1 . 1 . 1 . 0 . 0
1 . 0 . 0 . 0 . 0
1 . 0 . 0 . 0 . 0.
The outermost square has 8 1s, the next has 3 1s, and the innermost, 1 1, so that [8,3,1] is a square partition of 12.
		

Crossrefs

Cf. A237985.

Programs

Mathematica

z=20;
ferrersMatrix[list_]:=PadRight[Map[Table[1,{#}]&,#],{#,#}&[Max[#,Length[#]]]]&[list];
sqPart[list_]:=DeleteCases[Total[{Total[LowerTriangularize[#]+ Transpose[UpperTriangularize[#,1]]]&[Reverse[LowerTriangularize[#]]],Reverse[Total[Transpose[ LowerTriangularize[#]]+UpperTriangularize[#,1]]]&[Reverse[UpperTriangularize[#,1]]]}&[ferrersMatrix[list]]],0];
sqParts[n_]:=#[[Reverse[Ordering[PadRight[#]]]]]&[DeleteDuplicates[Map[sqPart,IntegerPartitions[n]]]]
Flatten[sq=Map[sqParts[#]&,Range[z]]] (*A237985*)
Map[Length,sq] (*A237980*)
(* Peter J. C. Moses, Feb 19 2014 *)