login
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.
8

%I #36 Apr 29 2020 07:36:53

%S 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,

%T 18,19,20,21,22,1,8,19,22,26,27,28,29,30,1,13,22,30,37,38,39,40,41,42,

%U 1,13,30,41,46,51,52,53,54,55,56,1,20,44,59,62,71,72,73,74,75,76,77

%N 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.

%C 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.

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

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

%H Alois P. Heinz, <a href="/A330661/b330661.txt">Rows n = 1..200, flattened</a>

%H OEIS Wiki, <a href="http://oeis.org/wiki/Orderings of partitions#A_comparison">Orderings of partitions (a comparison)</a>.

%F T(n,1) = 1.

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

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

%F T(2n,2) = T(2n+1,2) = A216053(n). - _Alois P. Heinz_, Jan 28 2020

%e 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.

%e Triangle T(n,k) begins:

%e 1;

%e 1, 2;

%e 1, 2, 3;

%e 1, 3, 4, 5;

%e 1, 3, 5, 6, 7;

%e 1, 5, 8, 9, 10, 11;

%e 1, 5, 9, 12, 13, 14, 15;

%e 1, 8, 13, 18, 19, 20, 21, 22;

%e 1, 8, 19, 22, 26, 27, 28, 29, 30;

%e 1, 13, 22, 30, 37, 38, 39, 40, 41, 42;

%e ...

%p b:= proc(l) option remember; (n-> `if`(n=0, 1,

%p b(subsop(1=[][], l))+g(n, l[1]-1)))(add(j, j=l))

%p end:

%p g:= proc(n, i) option remember; `if`(n=0 or i=1, 1,

%p `if`(i<1, 0, g(n-i, min(n-i, i))+g(n, i-1)))

%p end:

%p T:= proc(n, k) option remember; 1 + g(n$2)-

%p b((q-> [q+1$r, q$k-r])(iquo(n, k, 'r')))

%p end:

%p seq(seq(T(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Feb 19 2020

%t b[l_List] := b[l] = Function[n, If[n == 0, 1, b[ReplacePart[l, 1 -> Nothing]] + g[n, l[[1]] - 1]]][Total[l]];

%t 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 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}]]]];

%t Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Apr 29 2020, after _Alois P. Heinz_ *)

%o (PARI)

%o balP(p) = p[1]-p[#p]<=1

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

%o { for(n=1, 10, print(Row(n))) }

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

%Y T(2n,n) gives A332706.

%K nonn,tabl

%O 1,3

%A _Peter Dolland_, Dec 23 2019