A228100 - OEIS

%I #32 May 12 2020 12:59:41

%S 1,1,1,2,1,1,1,2,1,3,1,1,1,1,2,1,1,2,2,3,1,4,1,1,1,1,1,2,1,1,1,2,2,1,

%T 3,1,1,3,2,4,1,5,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,3,1,1,1,2,2,2,3,2,1,4,

%U 1,1,3,3,4,2,5,1,6,1,1,1,1,1,1,1,2,1,1

%N Triangle in which n-th row lists all partitions of n, such that partitions of n into m parts appear in lexicographic order previous to the partitions of n into k parts if k < m. (Fenner-Loizou tree.)

%C First differs from A193073 at a(58). - _Omar E. Pol_, Sep 22 2013

%C The partition lengths appear to be A331581. - _Gus Wiseman_, May 12 2020

%D T. I. Fenner, G. Loizou: A binary tree representation and related algorithms for generating integer partitions. The Computer J. 23(4), 332-337 (1980)

%D D. E. Knuth: The Art of Computer Programming. Generating all combinations and partitions, vol. 4, fasc. 3, 7.2.1.4, exercise 10.

%D K. Yamanaka, Y. Otachi, Sh. Nakano: Efficient enumeration of ordered trees with k leaves. In: WALCOM: Algorithms and Computation, Lecture Notes in Computer Science Volume 5431, 141-150 (2009)

%D S. Zaks, D. Richards: Generating trees and other combinatorial objects lexicographically. SIAM J. Comput. 8(1), 73-81 (1979)

%D A. Zoghbi, I. Stojmenovic': Fast algorithms for generating integer partitions. Int. J. Comput. Math. 70, 319-332 (1998)

%H Alois P. Heinz, <a href="/A228100/b228100.txt">rows n = 1..19, flattened</a>

%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/IntegerPartitionTrees">Integer Partition Trees</a>

%H OEIS Wiki, <a href="http://oeis.org/wiki/Orderings of partitions">Orderings of partitions</a>

%H Wikiversity, <a href="https://en.wikiversity.org/wiki/Lexicographic_and_colexicographic_order">Lexicographic and colexicographic order</a>

%e The sixth row is:

%e [1, 1, 1, 1, 1, 1]

%e [2, 1, 1, 1, 1]

%e [2, 2, 1, 1]

%e [3, 1, 1, 1]

%e [2, 2, 2]

%e [3, 2, 1]

%e [4, 1, 1]

%e [3, 3]

%e [4, 2]

%e [5, 1]

%e [6]

%e From _Gus Wiseman_, May 10 2020: (Start)

%e The triangle with partitions shown as Heinz numbers (A333485) begins:

%e     1

%e     2

%e     4   3

%e     8   6   5

%e    16  12   9  10   7

%e    32  24  18  20  15  14  11

%e    64  48  36  40  27  30  28  25  21  22  13

%e   128  96  72  80  54  60  56  45  50  42  44  35  33  26  17

%e (End)

%p b:= proc(n, i) b(n, i):= `if`(n=0 or i=1, [[1$n]], [b(n, i-1)[],

%p       `if`(i>n, [], map(x-> [i, x[]], b(n-i, i)))[]])

%p     end:

%p T:= n-> map(h-> h[], sort(b(n$2), proc(x, y) local i;

%p         if nops(x)<>nops(y) then return nops(x)>nops(y) else

%p         for i to nops(x) do if x[i]<>y[i] then return x[i]<y[i]

%p         fi od fi end))[]:

%p seq(T(n), n=1..8);  # _Alois P. Heinz_, Aug 13 2013

%t row[n_] := Flatten[Reverse[Sort[#]]& /@ SplitBy[Sort[IntegerPartitions[n] ], Length], 1] // Reverse; Array[row, 8] // Flatten (* _Jean-François Alcover_, Dec 05 2016 *)

%t ralensort[f_,c_]:=If[Length[f]!=Length[c],Length[f]>Length[c],OrderedQ[{f,c}]];

%t Join@@Table[Sort[IntegerPartitions[n],ralensort],{n,0,8}] (* _Gus Wiseman_, May 10 2020 *)

%o (Sage)

%o from collections import deque

%o def GeneratePartitions(n, visit):

%o     p = ([], 0, n)

%o     queue = deque()

%o     queue.append(p)

%o     visit(p)

%o     while len(queue) > 0 :

%o         (phead, pheadLen, pnum1s) = queue.popleft()

%o         if pnum1s != 1 :

%o             head = phead[:pheadLen] + [2]

%o             q = (head, pheadLen + 1, pnum1s - 2)

%o             if 1 <= q[2] : queue.append(q)

%o             visit(q)

%o         if pheadLen == 1 or (pheadLen > 1 and \

%o                       (phead[pheadLen - 1] != phead[pheadLen - 2])) :

%o             head = phead[:pheadLen]

%o             head[pheadLen - 1] += 1

%o             q = (head, pheadLen, pnum1s - 1)

%o             if 1 <= q[2] : queue.append(q)

%o             visit(q)

%o def visit(q): print(q[0] + [1 for i in range(q[2])])

%o for n in (1..7): GeneratePartitions(n, visit)

%Y See A036036 for the Hindenburg (graded reflected colexicographic) ordering.

%Y See A036037 for the graded colexicographic ordering.

%Y See A080576 for the Maple (graded reflected lexicographic) ordering.

%Y See A080577 for the Mathematica (graded reverse lexicographic) ordering.

%Y See A182937 the Fenner-Loizou (binary tree in preorder traversal) ordering.

%Y See A193073 for the graded lexicographic ordering.

%Y The version for compositions is A296773.

%Y Taking Heinz numbers gives A333485.

%Y Lexicographically ordered reversed partitions are A026791.

%Y Sorting partitions by Heinz number gives A296150, or A112798 for reversed partitions.

%Y Reversed partitions under the (sum/length/revlex) ordering are A334302.

%Y Cf. A000041, A036043, A048793, A211992, A228351, A228531, A331581, A333484, A334301, A334439.

%K nonn,tabf

%O 1,4

%A _Peter Luschny_, Aug 10 2013