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,4

Comments

First differs from A193073 at a(58). - Omar E. Pol, Sep 22 2013

The partition lengths appear to be A331581. - Gus Wiseman, May 12 2020

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

Example

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)

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]<y[i]
        fi od fi end))[]:
seq(T(n), n=1..8);  # Alois P. Heinz, Aug 13 2013

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 *)

Prog

(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)

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.

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

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

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

Sequence in context: A365105 A093993 A193073 * A211992 A182937 A340035

Adjacent sequences: A228097 A228098 A228099 * A228101 A228102 A228103

Keyword

nonn,tabf

Author

Peter Luschny, Aug 10 2013

Status

approved