Row 2 Completion Counts

Everything about Sudoku that doesn't fit in one of the other sections

Row 2 Completion Counts

Postby Mathimagics » Sun Oct 04, 2020 11:24 am

In the many, many pages of posts concerning the Mathematics of Sudoku, the focus seems to be on counting bands and grids. This is understandable, but nobody appears to have paid much attention to a more fundamental number, namely the number of ways in which the 2nd row can be filled in, for any given row 1.

I will denote this number as NR2(R, C), where the box sizes are R x C, and the corresponding grid size is N x N, where N = R x C. I will also assume, without loss of generalisation, that RC.

The value of NR2 boils down to the question: if we fix row 1 = {1, 2, ... N}, how many permutations are possible that do NOT have values (1 to C) appearing in any positions (1 to C), or values (C+1 to 2C) appearing in positions (C+1 to 2C), and so on. :?:

This is a classic combinatorial problem (permutations with forbidden positions), which has an explicit solution:

NR2_Formula1.png
NR2 formula
NR2_Formula1.png (6.05 KiB) Viewed 182 times

The values X[k] in this summation are the coefficients of (x ^ k) in P(R,C), the Rook polynomial for the given box size, after raising to the R-th power. That is, X = P(R,C) ^ R.

The rook polynomial P(R,C) for a single box (R x C) where RC is given by:

NR2_Formula2.png
NR2_Formula2.png (17.34 KiB) Viewed 182 times


For example: with R = C = 3 (standard Sudoku), the rook polynomial coefficients for (3 x 3) are {1, 9, 18, 6} (i.e. P(3,3) = 1 + 9x + 18x^2 + 6x^3).

After raising P(3,3) to the 3rd power, we get X[k] = { 1 , 27 , 297 , 1719 , 5670 , 10854 , 11772 , 6804 , 1944 , 216}. Plugging these into the first summation formula above gives NR2(3,3) = 12096.

Counts obtained for cases 3x3 to 6x6 are. Each NR2 value is divisible by (C! ^ R), so this is given along with the full NR2 count:

Code: Select all
RxC                                                                           NR2
---------------------------------------------------------------------------------
3x3                       56 x (3! ^ 3) =                                   12096
3x4                     1092 x (4! ^ 3) =                                15095808
4x4                   748521 x (4! ^ 4) =                            248341303296
4x5                134631576 x (5! ^ 4) =                       27917203599360000
4x6              25899377112 x (6! ^ 4) =                  6960161309975838720000
5x5            2671644472544 x (5! ^ 5) =                 66479063739206860800000
5x6         5752866855116280 x (6! ^ 5) =         1113132351251287958224896000000
6x6   4165949769769961828425 x (6! ^ 6) = 580375415775905260256627372851200000000
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: Row 2 Completion Counts

Postby Serg » Mon Oct 05, 2020 9:44 pm

Hi, Mathimagics!
Congratulations for these results! It's nice to see in Sudoku area mathematical results obtained by analytical methods, not by "brute force" entities enumerations. Results for 9 x 9 Sudoku and 16 x 16 Sudoku were published earlier and confirm your numbers.

In what way you got the main formula? I don't see it at Wiki page "Rook polynomial".

Serg
Serg
2018 Supporter
 
Posts: 732
Joined: 01 June 2010
Location: Russia

Re: Row 2 Completion Counts

Postby Mathimagics » Tue Oct 06, 2020 7:28 am

Hi Serg,

The main formula is an application of the Inclusion-exclusion principle.

I have attached a short document, Permutations with Restricted Positions and Rook Polynomials, which I found on the web, and which looks useful.

PermsForbiddenPositions.pdf
(74.28 KiB) Downloaded 28 times


[ EDIT ] I just spotted a typo in the attached document - the very first expression, following "The number of permutations with no objects in forbidden positions is", ends with a "+", and that should be a "-", since the signs in this expression are strictly alternating.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra


Return to General