|
%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
|
