

A322156


Irregular triangle where row n includes all decreasing sequences S = {k_0 = n, k_1, k_2, ..., k_m} in reverse lexical order such that the sum of subsequent terms k_j for all i < j <= m does not exceed any k_i.


5



1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 3, 3, 1, 3, 1, 1, 3, 2, 3, 2, 1, 3, 3, 4, 4, 1, 4, 1, 1, 4, 2, 4, 2, 1, 4, 2, 1, 1, 4, 2, 2, 4, 3, 4, 3, 1, 4, 4, 5, 5, 1, 5, 1, 1, 5, 2, 5, 2, 1, 5, 2, 1, 1, 5, 2, 2, 5, 3, 5, 3, 1, 5, 3, 1, 1, 5, 3, 2, 5, 4, 5, 4, 1, 5, 5, 6, 6, 1, 6, 1, 1, 6, 2, 6, 2, 1, 6, 2, 1, 1, 6, 2, 2, 6
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Algorithm:
Let S be a sequence starting with n. Let k be the index of a term in S, with n at position k = 0. Let S_r be the rth sequence in row n.
Starting with S_1 = {n}, we either (A) append a 1 to the left of S_r, or (B) we drop the most recentlyappended term S_(k) and increment the rightmost term (k  1).
By default we execute (A) and test according to the following. Consider the reversed accumulation A_(r + 1) = Sum(reverse(S_(k + 1))) = Sum(k_m, k_(m  1), ..., k_2, k_1). If S_r  A_(r + 1) contains nothing less than 0, then S_(k + 1) is retained, else we execute (B).
We end after k_1 = n, since otherwise we would enter an endless loop that also increments k_0 ad infinitum.
The first sequence S in row n is {n} while the last is {n, n}.
All rows n contain {{n}, {n, 1}, {n, n}}.
Only one repeated term k may appear at the end of any S in row n.
The longest possible sequence S in row n has 2 + floor(log2(n)) terms = 2 + A113473(n).
The sequence S describes unique integer partitions L that are recursively symmetrical. Example: We can convert S = {4, 2, 1} into the partition (7, 6, 5, 4, 3, 2, 1), a partition of N = 28. We set a 4X Durfee square with its upperleft corner at origin. Then we set 2^k = 2^1 = 2 2X squares with its upperleft corner in any coordinate bounded at left and top by either a previouslylain square or an axis. Finally, we set 2^2 = 4 1X squares as above once again. We obtain a Ferrer diagram as below, with the k marked, i.e., the 1st term 4X, the 2nd term 2X, the 3rd term 1X squares:
0 0 0 0 1 1 2
0 0 0 0 1 1
0 0 0 0 2
0 0 0 0
1 1 2
1 1
2
The resulting partition L is recursively selfconjugate; its arms are identical to its legs. We can eliminate the Durfee square and the other appendage and have a symmetrical partition L_1 with Durfee square of k_1 units, etc.
Were we to admit either more than 1 repeated k or a term such that S_k  A_(k + 1) had differences less than 1, we would have overlapping squares in the Ferrer diagram. Such diagrams are generated by larger n and all resulting diagrams are unique given the described algorithm.
The sequences S in row n, converted into integer partitions L, sum to n^2 <= N <= 3 * n^2.


LINKS

Michael De Vlieger, Table of n, a(n) for n = 1..10055 (rows 1 <= n <= 21, flattened)
Michael De Vlieger, Illustration for A322156
Michael De Vlieger, Rows 1 <= n <= 30, sequences S in row n have terms k that are space delimited


FORMULA

Row n contains A000123(n) = 2*A033485(n) sequences S.


EXAMPLE

Triangle begins:
1; 1,1;
2; 2,1; 2,1,1; 2,2;
3; 3,1; 3,1,1; 3,2; 3,2,1; 3,3;
4; 4,1; 4,1,1; 4,2; 4,2,1; 4,2,1,1; 4,2,2; 4,3; 4,3,1; 4,4;
...
Row n = 5 starts with S_1 = 5. We append 1 to get {5,1}. 1 does not exceed 5, thus S_2 = {5,1}. We append 1 to get {5,1,1}. A = {1,2}; {5,1}{2,1} = {3,0}, thus S_3 = {5,1,1} and we drop the last term and increment the new last term to get {5,2}. S_4 = {5,2}, and the ensuing terms {5,2,1}, {5,2,1,1}, {5,2,2} enter into the row. Since there are repeated terms at the last sequence, we drop the last term and increment the new last to get {5,3}. The terms {5,3,1}, {5,3,1,1}, {5,3,2}, {5,3,2,1}, are admitted. {5,3,2,1,1} has A = {1,2,4,6}. {5,3,2,1}{6,4,2,1} = {1,1,0,0}: {5,3,2,1,1} cannot be admitted, so we drop the last term and increment to {5,3,2,2} but the sum of the last two terms exceeds the second and we drop the last term and increment to {5,3,3}. For similar reasons, this cannot be admitted, we drop the last term and increment to {5,4}. This enters as well as {5,4,1}. Since any appendage or increment proves invalid, we end up incrementing to {5,5}. The two terms are the same, therefore we end the row n = 5.


MATHEMATICA

(* Generate sequence: *)
f[n_] := Block[{w = {n}, c}, c[x_] := Apply[Times, Most@ x  Reverse@ Accumulate@ Reverse@ Rest@ x]; Reap[Do[Which[And[Length@ w == 2, SameQ @@ w], Sow[w]; Break[], Length@ w == 1, Sow[w]; AppendTo[w, 1], c[w] > 0, Sow[w]; AppendTo[w, 1], True, Sow[w]; w = MapAt[1 + # &, Drop[w, 1], 1]], {i, Infinity}] ][[1, 1]] ]; Array[f, 6] // Flatten
(* Convert S = row n to standard partition: *)
g[w_] := Block[{k}, k = Total@ w; Total@ Map[Apply[Function[{s, t}, s Array[Boole[t <= # <= s + t  1] &, k] ], #] &, Apply[Join, Prepend[Table[Function[{v, c}, Map[{w[[k]], # + 1} &, Map[Total[v #] &, Tuples[{0, 1}, {Length@ v}]]]] @@ {Most@ #, ConstantArray[1, Length@ #  1]} &@ Take[w, k], {k, 2, Length@ w}], {{w[[1]], 1}}]]] ]


CROSSREFS

Cf.: A000123, A033485, A190899, A190900, A321223, A322457.
Sequence in context: A261126 A097456 A164002 * A332278 A182596 A087775
Adjacent sequences: A322153 A322154 A322155 * A322157 A322158 A322159


KEYWORD

nonn,easy


AUTHOR

Michael De Vlieger, Dec 11 2018


STATUS

approved



