Let $X_1, X_2, \cdots, X_n$ be a sample of a one-dimensional random variable $X$ which has the continuous cumulative probability function (cpf) $F$. It has been observed that the distribution-free statistics commonly appearing in the literature can be written in the form $\Phi\lbrack F(X_1), F(X_2), \cdots, F(X_n)\rbrack$ where $\Phi$ is a measurable symmetric function defined on the unit cube. Such statistics are said to have structure (d). Birnbaum and Rubin [12] have proved that for the family $\Omega^{\ast}$, of strictly monotone continuous cpf's, statistics of structure (d) possess a property stronger than that of being distribution-free. The purpose of this paper is to study the extension of the Birnbaum-Rubin (B-R) result to other classes of cpf's and to present a different approach to these results. It is found that a one-sided extension of the B-R result is valid for all properly closed, symmetrically complete classes of cpf's. Then, from the existing literature on completeness, one can conclude that the extension is valid for several other classes of statistical interest. The relation between statistics of structure (d) and strongly distribution-free statistics (Section 1) is of importance for two reasons. First of all, if one is designing distribution-free tests, the results here and in [12] guarantee that if one chooses a statistic of structure (d), one has a strongly distribution-free statistic for several large classes of cpf's. On the other hand if one has a strongly distribution-free statistic, the results guarantee that it is of structure (d). Hence, its cpf can be written as the volume of a polyhedral region in the $n$ dimensional unit cube. Under such circumstances the work of Smirnov [20], Feller [13], Anderson and Darling [4], and Birnbaum [9] indicate that it should be possible to evaluate the cpf explicity; reduce it to a system of recursion formulae; tabulate it with the aid of high-speed computers or at least evaluate its limiting distribution. This article is divided into four sections. In Section 1 distribution-free statistics of various types are introduced. Section 2 contains some preliminary results concerning cpf's. The main theorem is proved in Section 3; and Section 4 contains a survey of the known pertinent completeness results as well as a corollary of the main theorem.