]> Discrete Simplices

Discrete Simplices

The simplices of a division ringlet are scale-invariant, in the sense that D(n, p) {({positives}: f :1+n): sum(f) = p} for various positive p are all simply images of one another under scalings; so that it makes no difference which p one choses. However, when division is limited, as in {naturals}, one gets different collections depending on p. I'll refer to the simplices in this case as discrete (because there are gaps between values: for each value there is a definite distance for which there is no value less than that far away; in naturals, for each n, there is no other natural m less than 1 away from n). The analysis below is for the natural ringlet, but other discrete ringlets presumably have similar results.

In particular, in a divison ringlet, D(n, p) has infinitely many members for n > 0; whereas it has finitely many in the naturals. (In either case, D(0, p) = {[p]} and D(−1, p) = {} are finite.) Although members of D(n, p) are specified as partial functions from 1+n to {positives}, so that one member of D(1, 1) maps 0 to 1 and doesn't map 1 to anything, while the other maps 1 to 1 and doesn't map zero to anything, it's convenient when writing the lists to write 0 for the officially omitted entries in a list; it's easier to read [0, 1] than [, 1] and similar, particularly when there are many omissions. For example, for naturals,

For the sake of the following discussion, I'll also write D(n, 0) for the empty list, equivalently the list of 1+n zeros. We can then partition the members f of D(n, p) by their value of f(n): given f(n) = i, (:f:n) must be in D(n−1, p−i); indeed, for naturals n, p:

in which the union is disjoint (i.e. distinct i in p+1 contribute disjoint collections to the union).

Counting members

Thus, if C(n, p) is the number of members in D(n, p), we get C(n+1, p) = sum(: C(n, j) ←j |p+1). For each n, C(n, 0) = 1 (as D(n, 0) is the list whose 1+n entries are all 0); likewise, for each p, C(0, p) = 1 (as D(0, p) = {[p]}), whence C(1, p) = p+1 (as D(1, p) is {[p, 0], …, [p−i, i], …, [0, p]}) and C(2, p) = sum(: j+1 ←j :p+1) = (p+1).(p+2)/2. The number of subsets of size k within a set of size m is given by chose(m, k) = m!/k!/(m−k)! for 0 ≤ k ≤ m (zero otherwise), for which our C(0, p) = 1 = chose(0, p), C(1, p) = 1+p = chose(1, 1+p) and C(2, p) = (1+p).(2+p)/2 = chose(2+p, 2). The function chose has a useful structural property, chose(m+1, k+1) = chose(m, k) +chose(m, k+1) which I'll use below as chose(m, k) = chose(m+1, k+1) −chose(m, k+1). Whenever C(n, p) = chose(n+p, n) for all p, for some given n, we can infer

C(n+1, p)
= sum(: C(n, j) ←j :p+1)
= sum(: chose(n+j, n) ←j :p+1)
= sum(: chose(n+j+1, n+1) −chose(n+j, n+1) ←j :p+1)

in which each j's added term matches j+1's subtracted term, cancelling to leave:

= chose(n+p+1, n+1) −chose(n, n+1)

and chose(n, n+1) = 0 (there are no subsets of size n+1 in a set of size n), so C(n, p) = chose(n+p, n) for all natural p, for any given n, implies C(n+1, p) = chose(n+1+p, n+1) for all natural p also; given that the precondition held for n = 0, we can induce that C(n, p) = chose(n+p, n) for all natural n, p.

Indeed, for any pair of distinct tokens cut and add, we can represent a list ({naturals}: f :n+1) whose sum is p by a list F with p add entries and n cut entries, interleaved as f(0) add entries, then a cut, then f(1) add entries, then a cut, and so on, so that F(j +sum(: f :1+j)) = cut, for each j in n, with all other F(m) = add, and n +sum(: f :1+n) = n+p is the index just past the end of F, at which we would have put one more cut, but we don't need it to mark the end of the last run of add entries. There is a direct correspondence between lists of these two forms; and a list of the latter form is equivalently just a subset of size n (the indices of the cut entries) selected within n+p, so there are chose(n+p, n) of them.

Thus D(n, p) has (n+p)!/n!/p! members. In particular, for given n, simplices with distinct sums aren't isomorphic; however, there is an isomorphism between D(n, p) and D(p, n) for each natural n, p (just interchange cut ↔ add in the preceding). For example, in D(1, 2) and D(2, 1), we have

Valid CSSValid XHTML 1.1 Written by Eddy.