# How to calculate the total number of orderings of two samples while allowing for ties?

The total number of orderings of a sample (from lowest to highest) of two independently distributed continuous variables $$x$$ and $$y$$ is calculated thus:

$$\text{No. of orderings } = {n_x +n_y \choose{n_x}} = \frac{(n_x +n_y)!}{n_x!n_y!},$$

where $$n_x$$ and $$n_y$$ are the respective sample sizes of $$x$$ and $$y$$.

I am interested to know if there is a straightforward calculation when $$x$$ and $$y$$ are samples of independently and ordinally distributed, rather than continuous, distributed variables, so that ties become possible, and assume that when supports of both variables are finite sets, the cardinality of the union of supports for both variables includes cardinalities from $$1$$ to $$n_x+n_y$$ so that any number of ties from $$0$$ to $$\max (n_x,n_y)$$ are possible.

I can make an iterative algorithm to calculate this figure based on lattice traversals a la Schröer, & Trenkler (1995), but wonder if there is a faster closed-form formula?

Schröer, G., & Trenkler, D. (1995). Exact and randomization distributions of Kolmogorov-Smirnov tests two or three samples. Computational Statistics & Data Analysis, 20, 185–202.

• Please explain what an ordering of continuous variables is and what you mean by $n$ and $k.$ I would guess you are referring to a realization of $k$ iid values of $x$ and, independently, $n-k$ iid values of $y$ and that an "ordering" is the pattern in which instances of each variable appear when all $n$ values are placed in (ascending or descending) order. When either of the variables is not continuous, the answer depends on the details. Tell us more specifically what you are assuming about the distributions of $x$ and $y.$
– whuber
Dec 9, 2022 at 22:24
• @whuber Oh good gravy... I just went into a common combinatoric convention when writing that. Editing now. Thank you for your comment! Dec 10, 2022 at 1:46
• I have edited to add the following: "and assume both that it is possible for the variables to tie on any value, and that there are at least as many values as $\max (n_x,n_y)$" Dec 11, 2022 at 20:50
• Because your question is about "when x and y are samples of independently and ordinally distributed ... variables," I have been commenting the supports of those random variables. When the supports are finite sets of points, the answer to your question depends on the cardinality of the union of the supports, for all cardinalities from $1$ through $n_x+n_y$ inclusive.
– whuber
Dec 15, 2022 at 19:12
• Yes, I think so.
– whuber
Dec 15, 2022 at 21:06

The formula in the question indicates the meaning of "ordering" is the pattern of ties in a batch of data. That is, if we take $$n$$ numbers (possibly with ties), of which $$a$$ values are unique, we can fix the sequence of those unique values and write down how many of each one there are. This gives a vector of $$a \ge 1$$ counts summing to $$n:$$ a composition of $$n.$$

Another way to look at it is to write down all $$n$$ numbers in the same sequence, leaving $$n-1$$ blanks between them:

$$x_1\quad x_2\quad x_3\quad x_4\quad \cdots\quad x_k.$$

Place "$$=$$" signs in $$n-a$$ of those blanks to indicate the ties. There are $$\binom{n-1}{n-a}=\binom{n-1}{a-1}$$ ways to do so and each way gives a distinct ordering of $$n$$ numbers of length $$a.$$

When two batches of data, $$X$$ and $$Y,$$ are in hand, we obtain three orderings if we fix a sequence of all unique values occurring in either batch: an ordering of $$X,$$ an ordering of $$Y,$$ and an ordering of the combined values.

Additionally, we need to consider how the orderings of $$X$$ and $$Y$$ overlap. One way is to write the ordering for the union of $$X$$ and $$Y$$ and then classify the unique values according to whether they occur in both $$X$$ and $$Y$$ -- suppose there are $$d\ge 0$$ of these -- or only in $$X$$ ($$a-d$$ values) or only in $$Y$$ ($$b-d$$ values). In this notation, $$X$$ has $$a$$ unique values and $$Y$$ has $$b$$ unique values, but collectively the two batches have only $$a+b-d$$ unique values. Each classification gives a different joint order. Given $$a,$$ $$b,$$ and $$d,$$ the number of such classifications equals the multinomial coefficient

$$\binom{a+b-d}{d,a-d,b-d} = \frac{(a+b-d)!}{d!(a-d)!(b-d)!}.$$

Suppose $$X$$ has $$m$$ values (not necessarily distinct) and $$Y$$ has $$n$$ values. Because the joint orderings of $$(X,Y)$$ are in one-to-one correspondence with the orderings of $$X,$$ the orderings of $$Y,$$ and the joint classifications, we conclude

The number of joint orderings of $$X$$ and $$Y$$ where $$X$$ has $$a$$ distinct values, $$Y$$ has $$b$$ distinct values, and $$d$$ distinct values are common to $$X$$ and $$Y,$$ is $$h(a,b,d; m,n)=\binom{a+b-d}{d,a-d,b-d} \binom{m-1}{a-1} \binom{n-1}{b-1}.$$

To count all joint orderings, observe that any orderings with different values of $$a,$$ $$b,$$ or $$d$$ must be distinct, so all we need do is sum over the possibilities:

The number of joint orderings of $$X$$ and $$Y$$ is $$\sum_{a=1}^{m}\sum_{b=1}^{n} \sum_{d=0}^{\min(a,b)} h(a,b,d; m,n).$$

When both $$m$$ and $$n$$ exceed $$1,$$ there does not appear to be a closed formula for this sum.

Note that this approach gives a way to construct all joint orderings for batches of size $$m$$ and $$n.$$

As a tiny example, let $$X$$ have $$m=1$$ values and $$Y$$ have $$n=2$$ values. There are $$8$$ possible joint orderings, which we may denote schematically by showing where the $$X$$ and $$Y$$ values occur and where the ties are. The corresponding classification of the $$a+b-d$$ distinct ordered values is indicated by "$$x$$" (the value appears only in $$X$$), "$$y$$" (the value appears only in $$Y$$), and "$$.$$" (the value appears in both $$X$$ and $$Y$$).

$$\begin{array}{c|crrr} \text{Ordering} & \text{Classification} & \text{a} & \text{b} & \text{d}\\ \hline x\lt y=y & xy & 1 & 1 & 0\\ y=y\lt x & yx & 1 & 1 & 0\\ x=y=y & . & 1 & 1 & 1\\ x=y\lt y & .y & 1 & 2 & 1\\ x\lt y\lt y & xyy & 1 & 2 & 0\\ y\lt x\lt y & yxy & 1 & 2 & 0\\ y\lt y\lt x & yyx & 1 & 2 & 0\\ y\lt x=y & y. & 1 & 2 & 1 \end{array}$$

The counts grow rapidly with $$m$$ and $$n.$$ Here is a short table for small values of $$m$$ and $$n$$ as computed by the R code below.

   n
m     1   2    3    4     5     6      7      8
1   3   8   20   48   112   256    576   1280
2   8  26   76  208   544  1376   3392   8192
3  20  76  252  768  2208  6080  16192  41984
4  48 208  768 2568  8016 23776  67776 187136
5 112 544 2208 8016 26928 85376 258752 756224


The first row is a well-known sequence, but subsequent rows appear not to be known in mathematics.

h <- function(a,b,d,m,n)
exp(lfactorial(a+b-d) - lfactorial(d) - lfactorial(a-d) - lfactorial(b-d) +
lchoose(m-1,a-1) + lchoose(n-1,b-1))

g <- Vectorize(function(a,b,m,n) sum(h(a,b,seq(0, min(a,b)),m,n)), c("a", "b"))

f. <- function(m, n) {
G <- outer(seq(1,m), seq(1,n), g, m = m, n = n)
dimnames(G) <- list(X = seq(1, m), Y = seq(1, n))
G
}

f <- Vectorize(function(m, n) sum(f.(m, n)))

m <- 1:5
n <- 1:8
X <- outer(m, n, f)
dimnames(X) <- list(m = m, n = n)
(X)
$$$$
`
• Thank you so much! Before I asked the question, I had developed an iterative solution based on the lattice representation of orderings as in the Schröer and Trenkler article (including for arbitrary bounds parallel to the diagonal corresponding to K-S statistics). I noticed that if the origin at lower right had the value of 1, and I proceeded iteratively (either by rows or columns) the number of ordering corresponding to each point in the lattice is the sum of numbers assigned to all values below and/or left of that point. (so $0,1$ and $1,0$ also get 1, but $1,1$ gets 3, etc.). Dec 18, 2022 at 17:48
• Also delighted with your code, and am going to contrast performance with my own. :) Dec 18, 2022 at 17:49