A228099 Triangle read by rows, T(n, k) = prime(1)^p(k,1)*...*prime(n)^p(k,n) where p(k,j) is the j-th part of the k-th partition of n, additionally T(0,0) = 1. The partitions of n are ordered such that partitions of n into r parts appear in lexicographic order previous to the partitions of n into s parts if s < r. (Fenner-Loizou tree).

1, 2, 6, 4, 30, 12, 8, 210, 60, 36, 24, 16, 2310, 420, 180, 120, 72, 48, 32, 30030, 4620, 1260, 840, 900, 360, 240, 216, 144, 96, 64, 510510, 60060, 13860, 9240, 6300, 2520, 1680, 1800, 1080, 720, 480, 432, 288, 192, 128, 9699690, 1021020, 180180, 120120

Offset

0,2

Comments

The partitions' representation (A228100) is a weakly decreasing list of parts.

The rows (read from left to right) are strongly decreasing. The T(n, 0) are the primorial numbers A002110(n). The right side of the triangle are the powers of 2,

T(n, A000041(n)) = A000079(n). The row sums are A074140.

The partition corresponding to a(n), n > 0, can be recovered as the exponents of the primes in the canonical prime factorization of a(n).

References

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

Links

Peter Luschny, Rows n = 0..25, flattened

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

Peter Luschny, Integer Partition Trees

Example

The six-th row is:
[1, 1, 1, 1, 1, 1] -> 30030
[2, 1, 1, 1, 1] -> 4620
[2, 2, 1, 1] -> 1260
[3, 1, 1, 1] -> 840
[2, 2, 2] -> 900
[3, 2, 1] -> 360
[4, 1, 1] -> 240
[3, 3] -> 216
[4, 2] -> 144
[5, 1] -> 96
[6] -> 64

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-> mul(ithprime(j)^h[j], j=1..nops(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=0..8);  # Alois P. Heinz, Aug 13 2013

Mathematica

b[n_, i_] := If[n == 0 || i == 1, {Array[1&, n]}, Join[b[n, i-1], If[i>n, {}, Map[Function[x, Prepend[x, i]], b[n-i, i]]]]]; T[n_] := Map[Function[h, Times @@ ((Prime /@ Range[Length[h]])^h)], Sort[b[n, n], Which[Length[#1] > Length[#2], True, Length[#1] < Length[#2], False, True, OrderedQ[#1, #2]]&]]; Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Jan 27 2014, after Maple *)

Prog

(Sage)
from collections import deque
def Partitions_Fenner_Loizou(n):
    p = ([], 0, n)
    queue = deque()
    queue.append(p)
    yield 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)
            yield 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)
            yield q
def A228099_row(n):
    if n == 0: return [1]
    L = []
    P = primes_first_n(n)
    for p in Partitions_Fenner_Loizou(n):
        e = p[0] + [1 for i in range(p[2])]
        c = mul(P[i]^e[i] for i in range(len(e)))
        L.append(c)
    return L
for n in (0..7): A228099_row(n)

Crossrefs

Cf. A228100.

Sequence in context: A073039 A322792 A253588 * A227955 A324922 A329886

Adjacent sequences: A228096 A228097 A228098 * A228100 A228101 A228102

Keyword

nonn,tabf,look

Author

Peter Luschny, Aug 10 2013

Status

approved