A193073 Triangle in which n-th row lists all partitions of n, in graded lexicographical ordering.

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, 2, 2, 2, 3, 1, 1, 1, 3, 2, 1, 3, 3, 4, 1, 1, 4, 2, 5, 1, 6, 1, 1, 1, 1, 1, 1, 1, 2, 1

Offset: 1

Author

M. F. Hasler, Jul 15 2011

Keywords

• nonn
• tabf

Comments

The partitions of the integer n are sorted in lexicographical order (cf. link: sums are written with terms in decreasing order, then they are sorted in lexicographical (increasing) order), i.e., as [1,1,...,1], [2,1,...,1], [2,2,...], ..., [n].

Examples

			First five rows are:
[[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]]
From _Gus Wiseman_, May 08 2020: (Start)
The sequence of all partitions begins:
  ()           (2,2,1)        (5,1)            (5,2)
  (1)          (3,1,1)        (6)              (6,1)
  (1,1)        (3,2)          (1,1,1,1,1,1,1)  (7)
  (2)          (4,1)          (2,1,1,1,1,1)    (1,1,1,1,1,1,1,1)
  (1,1,1)      (5)            (2,2,1,1,1)      (2,1,1,1,1,1,1)
  (2,1)        (1,1,1,1,1,1)  (2,2,2,1)        (2,2,1,1,1,1)
  (3)          (2,1,1,1,1)    (3,1,1,1,1)      (2,2,2,1,1)
  (1,1,1,1)    (2,2,1,1)      (3,2,1,1)        (2,2,2,2)
  (2,1,1)      (2,2,2)        (3,2,2)          (3,1,1,1,1,1)
  (2,2)        (3,1,1,1)      (3,3,1)          (3,2,1,1,1)
  (3,1)        (3,2,1)        (4,1,1,1)        (3,2,2,1)
  (4)          (3,3)          (4,2,1)          (3,3,1,1)
  (1,1,1,1,1)  (4,1,1)        (4,3)            (3,3,2)
  (2,1,1,1)    (4,2)          (5,1,1)          (4,1,1,1,1)
The triangle with partitions shown as Heinz numbers (A334434) begins:
    1
    2
    4   3
    8   6   5
   16  12   9  10   7
   32  24  18  20  15  14  11
   64  48  36  27  40  30  25  28  21  22  13
  128  96  72  54  80  60  45  50  56  42  35  44  33  26  17
(End)
		

Links

• Alois P. Heinz, Rows n = 1..19, flattened
• OEIS Wiki, Orderings of partitions.
• Wikiversity, Lexicographic and colexicographic order

Crossrefs

See A036036 for the Hindenburg (graded reflected colexicographic) ordering (listed in the Abramowitz and Stegun Handbook).

See A036037 for graded colexicographic ordering.

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

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

See A228100 for the Fenner-Loizou (binary tree) ordering.

A006128 gives row lengths.

Row n has A000041(n) partitions.

The version for reversed (weakly increasing) partitions is A026791.

Lengths of these partitions appear to be A049085.

Taking colex instead of lex gives A211992.

The generalization to compositions is A228351.

Sorting partitions by Heinz number gives A296150.

The length-sensitive refinement is A334301.

The Heinz numbers of these partitions are A334434.

Cf. A066099, A129129, A185974, A228531, A334302, A334433, A334437, A334439.

Programs

Mathematica

row[n_] := Flatten[Reverse[Reverse /@ SplitBy[IntegerPartitions[n], Length] ], 1]; Array[row, 19] // Flatten (* Jean-François Alcover, Dec 05 2016 *)
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
Join@@Table[Sort[IntegerPartitions[n],lexsort],{n,0,8}] (* Gus Wiseman, May 08 2020 *)

PARI

A193073_row(n)=concat(vecsort(apply(P->Vec(vecsort(P,,4)),partitions(n)))) \\ The two vecsort() are needed since the PARI function (version >= 2.7.1) yields the partitions in Abramowitz-Stegun order: sorted by increasing length, decreasing largest part, then lex order, with parts in increasing order. - M. F. Hasler, Jun 04 2018 [replaced older code from Jul 12 2015]

Sage

def p(n, i):
    if n==0 or i==1: return [[1]*n]
    T = [[i] + x for x in p(n-i, i)] if i<=n else []
    return p(n, i-1) + T
A193073 = lambda n: p(n,n)
for n in (1..5): print(A193073(n)) # Peter Luschny, Aug 07 2015