Without wishing to detract from chx's excellent answer, I note that the idea that a battery can have a current-time capacity of 20Ah at both 5V and 19V is pretty counter-intuitive, because energy delivered is voltage * current * time (leaving aside the odd root-2, issues with voltage falling off as batteries discharge, and so on). Given that 20Ah is a measure of current * time, to have a given current-time capacity independent of voltage suggests that, however much energy the batteries hold when the converter is running in 5V mode, they mysteriously have access to nearly four times as much (19/5) in 19V mode.
You don't say what brand of power brick this is, but I went and looked at the specs for an Anker Pro2 20000mAh 5V-12V-16V-19V power brick. The capacity is quoted as 20000mAh, but also as 74Wh. Unlike the current-time measure, Wh really are a measure of stored energy (they're more likely measuring deliverable energy, but those two should pretty closely match unless you've got either a perpetual motion machine or a melted brick).
When I put my cynical hat on, I guess that manufacturers of multivoltage power bricks will quote their current-time capacity at the most advantageous voltage (ie, the lowest). Leaving aside the root-2s and falloffs again, we find that 74Wh at 5V is about 15000mAh, so I suspect this is what they've done (or, as chx suggests, they've slightly naughtily quoted energy stored in the cells). At 19V, assuming comparable conversion efficiencies, the current-time capacity would be 5/19 of the quoted figure, ie about 5300mAh.
I also note that the FAA's FAQ on batteries applies a limit in Wh (being 100Wh for carry-on), suggesting that some physicists were involved in the writing of the rules. I suspect if you dig out your power brick's instructions you will find that the energy storage capacity (rather than the current-time capacity) is within spec for carry-on, output voltage notwithstanding.