Yes the characterization is correct, and there are 58,084,310 legal collections in total.
To make headway, we need the right level of discourse, avoiding loss of accuracy while avoiding diving into trivialities.
Necessity & sufficiency of the deletion moves
Two kinds of operation were suggested to be necessary & sufficient to reach all legal collections:
(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.
Firstly, the two criteria are necessary. To unblock a file a capture must take place. Capturing an officer will allow both pawns from a file to promote. A pawn capturing a pawn from a neighbouring file is more efficient, as it allows three pawns to promote.
The condition is also sufficient, as can be seen by dividing up the board into 4 pairs of files. We have to make assumptions that the kings can keep out of the way of the action. See later for an example which explores the validity of this assumption.
"Supply & demand"
Maybe worth moving on to the question of which collections are achievable in this way:
- Count the number of visible "non-starting officers" for each side (queens beyond the first; other officers beyond the second of that type): N_w & N_b
- Count the number of "awol pawns" on each side: (pawns morphed into NSOs aren't counted): A_w & A_b
- Count the number of "missing officers" for each sides (missing queen, or other officers less than the second of that type): M_w & M_b
Then the following elegant "supply & demand" inequalities are necessary and sufficient criteria for a legal collection:
M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b
Grouping the terms by White & Black, the left hand side is the "supply", the right hand side is the "demand". The supply is always non-negative, so if the demand is zero or less, it's always satisfied. Similarly, a supply of 8+ will meet any demand that can occur.
Here's an example. Can we have 18 queens on the board? Yes!
N_w = N_b = 8
(because 8 promoted pawns on each side)
A_w = A_b = 0
(every missing pawn was promoted)
M_w = M_b = 6
(all Rs, Bs & Ns were captured)
M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2
So this is legal. Similarly for White supply for Black demand. Even if we had the knights still on the board, so M_b = M_w = 4, the inequality would be 4 >= 4, so still legal.
Aside on mate/stalemate
Some wonder if such a position can be achieved without mate or stalemate, which is a fair question. The answer is yes. It's like asking to prove that 450g of cornflakes will all fit in a box. It's a matter of common experience that one can just shake the pack and the cornflakes settle down. There are not too many cornflakes in the box. Although it's obviously illegal, it's possible to arrange the kings and up to 34(!) white queens on the board without mate or stalemate looming. At this density, it getting a bit tight, but this thought experiment shows that when we are dealing with merely 18 queens, where moreover friendly queens can shield against enemy ones, there a vast amount of slack, and no need to worry about forced mates or stalemates. Even with 18 queens, the chessboard is a very empty box of cornflakes :-)
Counting the collections
Let's focus on just the White units first. How many legal White collections are there? 8,694. Here's a quick proof.
Let k be the number of visible promotions to rook, knight or bishop (i.e. officers beyond the original complement of 2 for any of these types). (For symmetry reasons, queens are dealt with in a couple of paragraphs instead.)
Let v(k) be the number of different combinations of R,N,B which achieve this.
v(0) = 27:
because there may be 0-2 remaining of each of R,N,B.
For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:
v(1) = again 27:
3 ways to pick one of R,N,B to be 3;
& 0-2 possible for each of the other two types.
v(2) = 36:
27 ways to have 4,0-2,0-2;
& 9 ways to have 3,3,0-2.
Then the other 8-k pawns may still be Ps, or turned into Qs, or captured.
Let q be the number of visible queen promotions (i.e. queens beyond the original complement of 1).
Let u_k(q) be the number of different combinatorial ways we can achieve this (in terms of surviving pawns, queens and captured pawns)
u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.
For q>0, u_k(q) = (9-k-q)
s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.
Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1
So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694
All of these white collections are indeed achievable, e.g. if Black has only bare king remaining, but in fact in many other situations too: the supply/demand inequalities are not very demanding.
The next exercise involves counting for each combination of N_w, M_w ,A_w how many White collections exist.
I computed the following table of numbers of collections, sorted according to the total number of pieces on the board, as shown in this table:
For each number of units from 2-32, this shows
- v_0: the number of basic candidates without worrying about supply-demand,
- v_1: the number who have a single fail against supply-demand,
- v_2: the number who have a double fail against supply-demand.
To avoid double counting, the number of legal positions is computed as v_1 - 2*v_2 + v_3. My calculations match Kryukov's prior results exactly.
Note that there are no fails until one reaches 25 units. That's because with 8 captures, all candidate promotion collections can be achieved.
An "extra credit" open question (work in progress)
Retro enthusiasts further distinguish between the colour of squares the bishops are on, since that is an invariant. This has a major, visible impact on potential legality, is part of the essential classification for chess tablebases, and is also an aesthetic concern in composition. The corresponding term then is "non-standard officers" (queens or "tinted" bishops beyond the first; rooks or knights beyond the second). The count of missing officers is based on the same 5 types. The determination of which additional inequalities are necessary and sufficient to characterize legal collections is now substantially more complicated.
The best approach may be to first apply the adapted supply/demand inequalities. Then can ask how many extra pawn captures are required to "nudge" certain bishops to the correct tint?
A pawn capture of an officer/pawn will result in a batch of respectively 2/3 pawns all promoted on same tint squares, but it seems that for each such batch, we are free to choose the tint independently.
