A159299 Number of n-colorings of the 4 X 4 Sudoku graph.

0, 0, 0, 0, 288, 166560, 33539040, 2350746720, 75756999360, 1388552614848, 16744788486720, 146769785743680, 1002373493948640, 5606534724167520, 26640793339768608, 110556058012152480, 409297168707073920, 1374572399886053760, 4243833928227876480

Offset: 0

Author

Alois P. Heinz, Apr 09 2009

Keywords

• nonn
• easy

Comments

The 4 X 4 Sudoku graph is a septic graph on 16 vertices and 56 edges. a(n) gives the number of 4 X 4 Sudoku solutions, if each of up to n numbers is allowed only once in every row, column and block.

Examples

			For n=4 colors one of the 288 possible colorings is given by this Sudoku:
  +---+---+
  |1 2|3 4|
  |4 3|2 1|
  +---+---+
  |3 1|4 2|
  |2 4|1 3|
  +---+---+ .
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000
• Timme, Marc; van Bussel, Frank; Fliegner, Denny; Stolzenberg, Sebastian (2009) "Counting complex disordered states by efficient pattern matching: chromatic polynomials and Potts partition functions", New J. Phys. 11 023001, doi: 10.1088/1367-2630/11/2/023001.
• Eric Weisstein's World of Mathematics, Chromatic Polynomial
• Wikipedia, Mathematics of Sudoku
• Wikipedia, Sudoku
• Wikipedia, Sudoku algorithms
• Index entries for linear recurrences with constant coefficients, signature (17,-136,680, -2380,6188,-12376,19448,-24310,24310,-19448,12376,-6188,2380, -680,136,-17,1).

Crossrefs

Cf. A107739, A182866.

Programs

Maple

a:= n-> n^16 -56*n^15 +1492*n^14 -25072*n^13 +296918*n^12 -2621552*n^11 [phone]*n^10 -94352168*n^9 [phone]*n^8 -1279118840*n^7 [phone]*n^6 -6107865464*n^5 [phone]*n^4 -7877463064*n^3 [phone]*n^2 -1117762248*n: seq(a(n), n=0..20);

Formula

a(n) = n^16 -56*n^15 + ... (see Maple program).

G.f.: -96*x^4*(343316843*x^12 [phone]*x^11 [phone]*x^10 [phone]*x^9 [phone]*x^8 [phone]*x^7 [phone]*x^6 [phone]*x^5 [phone]*x^4 [phone]*x^3 +320278*x^2 +1684*x +3)/ (x-1)^17. - Colin Barker, Aug 04 2012