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

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.

Links

Alois P. Heinz, Rows n = 1..200, flattened

OEIS Wiki, Orderings of partitions (a comparison).

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

Example

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;
  ...

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

Prog

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

Crossrefs

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

T(2n,n) gives A332706.

Sequence in context: A213008 A215520 A026820 * A091438 A011794 A221640

Adjacent sequences: A330658 A330659 A330660 * A330662 A330663 A330664

Keyword

nonn,tabl

Author

Peter Dolland, Dec 23 2019

Status

approved