I thought it was impossible to say Nombro de because Nombro represents a quantity and Da is supposed to be used for quantities. When would someone say Nombro de?
The same principles apply.
When the thing being quantified is definite (preceded by la, tiu, mia, or another difinilo) you use de.
Most other times it's da to emphasize that it's a quantity.
- duobla nombro da krieguloj
When there is less emphasis on the quantity, you can use de
- [Malgrandigi la] nombron de regimentoj kaj la nombron de soldatoj
Da is used with answers to kiom. If you wanted to know how many soldiers there are, you wouldn't say "a number's worth" - but you could say granda nombro da ili or duobla nombro da ili. When you're talking about reducing the number of soldiers, the phrase "of soliders" explains which number you're reducing, not that you have a "number's worth" of them.
I'm working on a video answer to this question. In the meanwhile, this video covers the same material. This link will bring you right to where he discusses nombro de.