A330661 T(n,k) is the index within the partitions of n in canonical ordering of the k-th partition whose parts differ pairwise by at most one.

1, 1, 2, 1, 2, 3, 1, 3, 4, 5, 1, 3, 5, 6, 7, 1, 5, 8, 9, 10, 11, 1, 5, 9, 12, 13, 14, 15, 1, 8, 13, 18, 19, 20, 21, 22, 1, 8, 19, 22, 26, 27, 28, 29, 30, 1, 13, 22, 30, 37, 38, 39, 40, 41, 42, 1, 13, 30, 41, 46, 51, 52, 53, 54, 55, 56, 1, 20, 44, 59, 62, 71, 72, 73, 74, 75, 76, 77

Offset: 1

Author

Peter Dolland, Dec 23 2019

Keywords

• nonn
• tabl

Comments

For each length k in [1..n] there is exactly one such partition [p_1,...,p_k], with p_i = a+1 for i=1..j and p_i = a for i=j+1..k, where a = floor(n/k) and j = n - k * a.

If k | n, then all parts p_i are equal. A027750 lists the indices of these partitions in this triangle.

Canonical ordering is also known as graded reverse lexicographic ordering, see A080577 or link below.

Examples

			Partitions of 8 in canonical ordering begin: 8, 71, 62, 611, 53, 521, 5111, 44, 431, 422, 4211, 41111, 332, ... . The partitions whose parts differ pairwise by at most one in this list are 8, 44, 332, ... at indices 1, 8, 13, ... and this gives row 8 of this triangle.
Triangle T(n,k) begins:
  1;
  1,  2;
  1,  2,  3;
  1,  3,  4,  5;
  1,  3,  5,  6,  7;
  1,  5,  8,  9, 10, 11;
  1,  5,  9, 12, 13, 14, 15;
  1,  8, 13, 18, 19, 20, 21, 22;
  1,  8, 19, 22, 26, 27, 28, 29, 30;
  1, 13, 22, 30, 37, 38, 39, 40, 41, 42;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..200, flattened
• OEIS Wiki, Orderings of partitions (a comparison).

Crossrefs

Cf. A000041, A063008, A027750, A080577, A216053, A238639, A238640.

T(2n,n) gives A332706.

Programs

Maple

b:= proc(l) option remember; (n-> `if`(n=0, 1,
      b(subsop(1=[][], l))+g(n, l[1]-1)))(add(j, j=l))
    end:
g:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
     `if`(i<1, 0, g(n-i, min(n-i, i))+g(n, i-1)))
    end:
T:= proc(n, k) option remember; 1 + g(n$2)-
      b((q-> [q+1$r, q$k-r])(iquo(n, k, 'r')))
    end:
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Feb 19 2020

Mathematica

b[l_List] := b[l] = Function[n, If[n == 0, 1, b[ReplacePart[l, 1 -> Nothing]] + g[n, l[[1]] - 1]]][Total[l]];
g[n_, i_] := g[n, i] = If[n == 0 || i == 1, 1, If[i < 1, 0, g[n - i, Min[n - i, i]] + g[n, i - 1]]];
T[n_, k_] := T[n, k] = Module[{q, r}, {q, r} = QuotientRemainder[n, k]; 1 + g[n, n] - b[Join[Table[q + 1, {r}], Table[q, {k - r}]]]];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 29 2020, after Alois P. Heinz *)

PARI

balP(p) = p[1]-p[#p]<=1
Row(n)={v=vecsort([Vecrev(p) | p<-partitions(n)], , 4);select(i->balP(v[i]),[1..#v])}
{ for(n=1, 10, print(Row(n))) }

Formula

T(n,1) = 1.

T(n,n) = A000041(n).

T(n,k) = A000041(n) - (n - k) for k = ceiling(n/2)..n.

T(2n,2) = T(2n+1,2) = A216053(n). - Alois P. Heinz, Jan 28 2020