cp's OEIS Frontend

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

%I A322156 #48 Jan 28 2022 07:43:10
%S A322156 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,
%T A322156 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,
%U A322156 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
%N A322156 Irregular triangle where row n includes all decreasing sequences S = {k_0 = n, k_1, k_2, ..., k_m} in reverse lexicographic order such that the sum of subsequent terms k_j for all i < j <= m does not exceed any k_i.
%C A322156 Algorithm:
%C A322156 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 r-th sequence in row n.
%C A322156 Starting with S_1 = {n}, we either (A) append a 1 to the left of S_r, or (B) we drop the most recently-appended term S_(k) and increment the rightmost term (k - 1).
%C A322156 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, otherwise we execute (B).
%C A322156 We end after k_1 = n, since otherwise we would enter an endless loop that also increments k_0 ad infinitum.
%C A322156 The first sequence S in row n is {n} while the last is {n, n}.
%C A322156 All rows n contain {{n}, {n, 1}, {n, n}}.
%C A322156 Only one repeated term k may appear at the end of any S in row n.
%C A322156 The longest possible sequence S in row n has 2 + floor(log_2(n)) terms = 2 + A113473(n).
%C A322156 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 upper-left corner at origin. Then we set 2^k = 2^1 = 2 2X squares, each with its upper-left corner in any coordinate bounded at left and top by either a previously-lain 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:
%C A322156     0  0  0  0  1  1  2
%C A322156     0  0  0  0  1  1
%C A322156     0  0  0  0  2
%C A322156     0  0  0  0
%C A322156     1  1  2
%C A322156     1  1
%C A322156     2
%C A322156 The resulting partition L is recursively self-conjugate; 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.
%C A322156 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.
%C A322156 The sequences S in row n, converted into integer partitions L, sum to n^2 <= N <= 3 * n^2.
%H A322156 Michael De Vlieger, <a href="/A322156/b322156.txt">Table of n, a(n) for n = 1..10055</a> (rows 1 <= n <= 21, flattened)
%H A322156 Michael De Vlieger, <a href="/A322156/a322156.png">Illustration for A322156</a>
%H A322156 Michael De Vlieger, <a href="/A322156/a322156.txt">Rows 1 <= n <= 30, sequences S in row n have terms k that are space delimited</a>
%F A322156 Row n contains A000123(n) = 2*A033485(n) sequences S.
%e A322156 Triangle begins:
%e A322156 1; 1,1;
%e A322156 2; 2,1; 2,1,1; 2,2;
%e A322156 3; 3,1; 3,1,1; 3,2; 3,2,1; 3,3;
%e A322156 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;
%e A322156 ...
%e A322156 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, so 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.
%t A322156 (* Generate sequence: *)
%t A322156 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
%t A322156 (* Convert S = row n to standard partition: *)
%t A322156 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}}]]] ]
%Y A322156 Cf. A000123, A033485, A190899, A190900, A321223, A322457.
%K A322156 nonn,easy
%O A322156 1,4
%A A322156 _Michael De Vlieger_, Dec 11 2018