OFFSET
1,2
COMMENTS
Suppose that S = (s(m)), for m >= 1, is a sequence of distinct real numbers that is dense in an open interval (a,b). The increasing partition array (p(n,k)) of the set N of positive integers is defined inductively as follows: p(1,1) = 1, and for k >= 2, p(1,k) = least m such that s(m) > s(p(1,k-1)). For n>=2, p(n,1) = least new m (that is, m is not p(h,k) for any h<=n-1 and k>=1), and for k>=2, p(n,k) = least new m such that s(m) > s(p(n,k-1)).
The decreasing partition array (p(n,k)) of N is defined as follows: p(1,1)=s(1), and for k>=2, p(1,k) = least new m such that s(m) < s(p(1,k-1)). For n>=2, p(n,1) = least new m, and for k>=2, p(n,k) = least new m such that s(m) < (p(n,k-1)).
Note that if S = (s(n)) is dense in (a,b), then for m>=1 and k=1..m, the sequence (s(k+m*n)) is dense in (a,b); indeed, if any nondense subsequence of S is removed from S, the remaining subsequence is dense; consequently, infinitely many increasing and decreasing partition arrays are defined from any such S.
If R is an array whose rows partition N, such as the Wythoff array, A035513, then for any sequence S of distinct real numbers that is dense in an open interval (a,b), there are infinitely many dense subsequences of S, each of whose increasing partition array is R, and likewise for decreasing partition sequences.
EXAMPLE
The dense sequence S is (1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7,...), consisting of the Farey fractions in the interval (0,1), in order of their occurrence in the Farey sequence. Writing S = (s(n)), the increasing S-array is represented by the following increasing chains:
(row 1): 1/2 < 2/3 < 3/4 < 4/5 < ...
(row 2): 1/3 < 2/5 < 3/5 < 5/7 < ...
(row 3): 1/4 < 2/7 < 3/7 < 4/7 < ...
(row 4): 1/5 < 3/8 < 4/9 < 5/9 < ...
Numerators: A038566.
Denominators: A038567.
Every row of the increasing S-array has limit 1; every column is decreasing array has limit 0.
Corner of the increasing partition array:
1 3 5 9 11 17 21 27 31 41
2 7 8 16 26 40 56 70 94 118
4 13 14 15 20 30 39 55 62 78
6 19 24 25 38 54 69 92 116 137
10 23 29 35 36 37 44 53 61 77
12 33 34 43 51 52 76 89 90 114
18 47 48 49 50 67 68 99 113 125
22 59 60 75 87 88 112 135 164 193
32 73 83 84 98 123 133 134 162 206
MATHEMATICA
highs := {Map[First, #], Most[FoldList[Plus, 1, Map[Length, #]]]} &[Split[Rest[FoldList[Max, -\[Infinity], #]]]] &;
lows := {Map[First, #], Most[FoldList[Plus, 1, Map[Length, #]]]} &[Split[Rest[FoldList[Min, +\[Infinity], #]]]] &;
seqS = Rest[Rest[SortBy[FareySequence[40], Denominator[#] &]]];
(* User: put your dense sequence S just above, after seqS = *)
indices = Range[Length[seqS]];
arrI = {}; (* start accumulating increasing partition array *)
Until[Last[arrI] == {}, AppendTo[arrI, Flatten[Map[Position[seqS, #] &,
highs[seqS[[Complement[indices, Flatten[arrI]]]]][[1]]]]]];
Grid[Most[arrI], Frame -> All]
arrD = {}; (* start accumulating decreasing partition array *)
Until[Last[arrD] == {}, AppendTo[arrD,
Flatten[Map[Position[seqS, #] &, lows[seqS[[Complement[indices, Flatten[arrD]]]]][[1]]]]]];
Grid[Most[arrD], Frame -> All]
(* Peter J. C. Moses, Sep 04 2025 *)
CROSSREFS
KEYWORD
AUTHOR
Clark Kimberling, Oct 08 2025
STATUS
approved
