integer partition

使用加法,湊得給定數字。

給你一個數,例如5。哪些數字相加,可以得到5呢?

例如2+3=5、1+1+1+1+1=5、……。

使用加法,分解給定數字。

湊合與分解,一體兩面。5可以分解成哪些數字相加呢?

例如5=2+3、5=1+1+1+1+1、……。

一個數字的一種分解結果,稱做一個「整數分割」。

專著《Integer Partitions》。

整數分割無視數字先後次序

同一種數字組成方式,視作同一種整數分割。

例如5=2+3、5=3+2是同一種整數分割。

一種整數分割的數字們,由大到小排序。所有分割們,按照字典順序排序。以方便判斷同一種分割。

例如5=1+1+1+1+1、5=2+1+1+1、5=2+2+1、……。

Ferrers diagram / Young tableau

排序之後,畫成圖形。每個橫條,數量遞減。

例如5的整數分割,總共7種。

1      2      3      4      5      6     7    
●      ●●     ●●     ●●●    ●●●    ●●●●  ●●●●●
●      ●      ●●     ●      ●●     ●          
●      ●      ●      ●                        
●      ●                                      
●                                             

所有圖形,左右對應,沿對角線鏡射,豎著數就是橫著數。

sum of powers

sum of squares

https://en.wikipedia.org/wiki/Sum_of_squares_function
https://en.wikipedia.org/wiki/Jacobi's_four-square_theorem
https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem
https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem
https://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares

sum of cubes

https://en.wikipedia.org/wiki/Taxicab_number
https://en.wikipedia.org/wiki/Sums_of_three_cubes

sum of powers

https://en.wikipedia.org/wiki/Diophantine_equation
https://en.wikipedia.org/wiki/Waring's_problem
https://en.wikipedia.org/wiki/Fermat's_Last_Theorem

sum of special numbers

https://en.wikipedia.org/wiki/Fermat_polygonal_number_theorem

tessellation

tessellation(tiling)

https://en.wikipedia.org/wiki/Tiling_by_regular_polygons
https://en.wikipedia.org/wiki/Domino_tiling

ICPC 3275

Goldbach's conjecture

Goldbach's conjecture

哥德巴赫猜想。大於2的偶數,皆可分割成兩個質數相加?

UVa 543 686