For any set S let | seq 1-1 ( S ) | denote the cardinality of the set of all finite one-to-one sequences that can be formed from S , and for positive integers a let | a S | denote the cardinality of all functions from S to a . Using a result from combinatorial number theory, Halbeisen and Shelah have shown that even in the absence of the axiom of choice, for infinite sets S one always has | seq 1-1 ( S ) | <img src="halb0x.gif" alt="/=" class="neq" align="middle"> 1 | 2 S | (but nothing more can be proved without the aid of the axiom of choice). Combining stronger number-theoretic results with the combinatorial proof for a = 2, it will be shown that for most positive integers a one can prove the inequality | seq 1-1 ( S ) | 1 | a S | without using any form of the axiom of choice. Moreover, it is shown that a very probable number-theoretic conjecture implies that this inequality holds for every positive integer a in any model of set theory.