A228100 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.)
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, 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, 1, 1, 3, 3, 4, 2, 5, 1, 6, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1
Offset: 1
Examples
The sixth row is:
[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, 1, 1]
[3, 3]
[4, 2]
[5, 1]
[6]
From _Gus Wiseman_, May 10 2020: (Start)
The triangle with partitions shown as Heinz numbers (A333485) begins:
1
2
4 3
8 6 5
16 12 9 10 7
32 24 18 20 15 14 11
64 48 36 40 27 30 28 25 21 22 13
128 96 72 80 54 60 56 45 50 42 44 35 33 26 17
(End)
References
- 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. E. Knuth: The Art of Computer Programming. Generating all combinations and partitions, vol. 4, fasc. 3, 7.2.1.4, exercise 10.
- 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)
- S. Zaks, D. Richards: Generating trees and other combinatorial objects lexicographically. SIAM J. Comput. 8(1), 73-81 (1979)
- A. Zoghbi, I. Stojmenovic': Fast algorithms for generating integer partitions. Int. J. Comput. Math. 70, 319-332 (1998)
Links
- Alois P. Heinz, rows n = 1..19, flattened
- Peter Luschny, Integer Partition Trees
- OEIS Wiki, Orderings of partitions
- Wikiversity, Lexicographic and colexicographic order
Crossrefs
See A036036 for the Hindenburg (graded reflected colexicographic) ordering.
See A036037 for the graded colexicographic ordering.
See A080576 for the Maple (graded reflected lexicographic) ordering.
See A080577 for the Mathematica (graded reverse lexicographic) ordering.
See A182937 the Fenner-Loizou (binary tree in preorder traversal) ordering.
See A193073 for the graded lexicographic ordering.
The version for compositions is A296773.
Taking Heinz numbers gives A333485.
Lexicographically ordered reversed partitions are A026791.
Reversed partitions under the (sum/length/revlex) ordering are A334302.
Programs
-
Maple
b:= proc(n, i) b(n, i):= `if`(n=0 or i=1, [[1$n]], [b(n, i-1)[], `if`(i>n, [], map(x-> [i, x[]], b(n-i, i)))[]]) end: T:= n-> map(h-> h[], sort(b(n$2), proc(x, y) local i; if nops(x)<>nops(y) then return nops(x)>nops(y) else for i to nops(x) do if x[i]<>y[i] then return x[i] -
Mathematica
row[n_] := Flatten[Reverse[Sort[#]]& /@ SplitBy[Sort[IntegerPartitions[n] ], Length], 1] // Reverse; Array[row, 8] // Flatten (* Jean-François Alcover, Dec 05 2016 *) ralensort[f_,c_]:=If[Length[f]!=Length[c],Length[f]>Length[c],OrderedQ[{f,c}]]; Join@@Table[Sort[IntegerPartitions[n],ralensort],{n,0,8}] (* Gus Wiseman, May 10 2020 *)
-
Sage
from collections import deque def GeneratePartitions(n, visit): p = ([], 0, n) queue = deque() queue.append(p) visit(p) while len(queue) > 0 : (phead, pheadLen, pnum1s) = queue.popleft() if pnum1s != 1 : head = phead[:pheadLen] + [2] q = (head, pheadLen + 1, pnum1s - 2) if 1 <= q[2] : queue.append(q) visit(q) if pheadLen == 1 or (pheadLen > 1 and \ (phead[pheadLen - 1] != phead[pheadLen - 2])) : head = phead[:pheadLen] head[pheadLen - 1] += 1 q = (head, pheadLen, pnum1s - 1) if 1 <= q[2] : queue.append(q) visit(q) def visit(q): print(q[0] + [1 for i in range(q[2])]) for n in (1..7): GeneratePartitions(n, visit)
Comments