A116861 Triangle read by rows: T(n,k) is the number of partitions of n such that the sum of the parts, counted without multiplicities, is equal to k (n>=1, k>=1).

1, 1, 1, 1, 0, 2, 1, 1, 1, 2, 1, 0, 2, 1, 3, 1, 1, 3, 1, 1, 4, 1, 0, 3, 2, 2, 2, 5, 1, 1, 3, 3, 2, 4, 2, 6, 1, 0, 5, 2, 3, 4, 4, 3, 8, 1, 1, 4, 3, 4, 7, 4, 5, 3, 10, 1, 0, 5, 3, 4, 7, 7, 6, 6, 5, 12, 1, 1, 6, 4, 3, 12, 6, 8, 7, 9, 5, 15, 1, 0, 6, 4, 5, 10, 10, 9, 10, 11, 10, 7, 18, 1, 1, 6, 4, 5, 15, 11, 13, 9, 16, 11, 13, 8, 22

Offset: 1

Author

Emeric Deutsch, Feb 27 2006

Keywords

• nonn
• tabl

Comments

Conjecture: Reverse the rows of the table to get an infinite lower-triangular matrix b with 1's on the main diagonal. The third diagonal of the inverse of b is minus A137719. - George Beck, Oct 26 2019

Proof: The reversed rows yield the matrix I+N where N is strictly lower triangular, N[i,j] = 0 for j >= i, having its 2nd diagonal equal to the 2nd column (1, 0, 1, 0, 1, ...): N[i+1,i] = A000035(i), i >= 1, and 3rd diagonal equal to the 3rd column of this triangle, (2, 1, 2, 3, 3, 3, ...): N[i+2,i] = A137719(i), i >= 1. It is known that (I+N)^-1 = 1 - N + N^2 - N^3 +- .... Here N^2 has not only the second but also the 3rd diagonal zero, because N^2[i+2,i] = N[i+2,i+1]*N[i+1,i] = A000035(i+1)*A000035(i) = 0. Therefore the 3rd diagonal of (I+N)^-1 is equal to -A137719 without leading 0. - M. F. Hasler, Oct 27 2019

From Gus Wiseman, Aug 27 2023: (Start)

Also the number of ways to write n-k as a nonnegative linear combination of a strict integer partition of k. Also the number of ways to write n as a (strictly) positive linear combination of a strict integer partition of k. Row n=7 counts the following:

7*1 . 1*2+5*1 1*3+4*1 1*3+2*2 1*5+2*1 1*7

2*2+3*1 2*3+1*1 1*4+3*1 1*3+1*2+2*1 1*4+1*3

3*2+1*1 1*5+1*2

1*6+1*1

1*4+1*2+1*1

(End)

Examples

			T(10,7) = 4 because we have [6,1,1,1,1], [4,3,3], [4,2,2,1,1] and [4,2,1,1,1,1] (6+1=4+3=4+2+1=7).
Triangle starts:
  1;
  1, 1;
  1, 0, 2;
  1, 1, 1, 2;
  1, 0, 2, 1, 3;
  1, 1, 3, 1, 1,  4;
  1, 0, 3, 2, 2,  2, 5;
  1, 1, 3, 3, 2,  4, 2, 6;
  1, 0, 5, 2, 3,  4, 4, 3, 8;
  1, 1, 4, 3, 4,  7, 4, 5, 3, 10;
  1, 0, 5, 3, 4,  7, 7, 6, 6,  5, 12;
  1, 1, 6, 4, 3, 12, 6, 8, 7,  9,  5, 15;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• P. J. Rossky, M. Karplus, The enumeration of Goldstone diagrams in many-body perturbation theory, J. Chem. Phys. 64 (1976) 1569, equation (16)(1).

Crossrefs

Cf. A000041 (row sums), A000009 (diagonal), A014153.

Cf. A114638 (count partitions with #parts = sum(distinct parts)).

Column 1: A000012, column 2: A000035(1..), column 3: A137719(1..).

For subsets instead of partitions we have A026820.

This statistic is ranked by A066328.

The central diagonal is T(2n,n) = A364910(n), non-strict A364907.

Partial sums of columns are columns of A364911.

Same as A364916 (offset 0) with rows reversed.

A008284 counts partitions by length, strict A008289.

A364912 counts linear combinations of partitions.

A364913 counts combination-full partitions, strict A364839.

Cf. A237667, A364272, A364915, A365002, A365004, A365006.

Programs

Maple

g:= -1+product(1+t^j*x^j/(1-x^j), j=1..40): gser:= simplify(series(g,x=0,18)): for n from 1 to 14 do P[n]:=sort(coeff(gser,x^n)) od: for n from 1 to 14 do seq(coeff(P[n],t^j),j=1..n) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, i) option remember; local f, g, j;
      if n=0 then [1] elif i<1 then [ ] else f:= b(n, i-1);
         for j to n/i do
           f:= zip((x, y)->x+y, f, [0$i, b(n-i*j, i-1)[]], 0)
         od; f
      fi
    end:
T:= n-> subsop(1=NULL, b(n, n))[]:
seq(T(n), n=1..20);  # Alois P. Heinz, Feb 27 2013

Mathematica

max = 14; s = Series[-1+Product[1+t^j*x^j/(1-x^j), {j, 1, max}], {x, 0, max}, {t, 0, max}] // Normal; t[n_, k_] := SeriesCoefficient[s, {x, 0, n}, {t, 0, k}]; Table[t[n, k], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 17 2014 *)
Table[Length[Select[IntegerPartitions[n],Total[Union[#]]==k&]],{n,0,10},{k,0,n}] (* Gus Wiseman, Aug 29 2023 *)

PARI

A116861(n,k,s=0)={forpart(X=n,vecsum(Set(X))==k&&s++,k);s} \\ M. F. Hasler, Oct 27 2019

Formula

G.f.: -1 + Product_{j>=1} (1 + t^j*x^j/(1-x^j)).

Sum_{k=1..n} T(n,k) = A000041(n).

T(n,n) = A000009(n).

Sum_{k=1..n} k*T(n,k) = A014153(n-1).

T(n,1) = 1. T(n,2) = A000035(n+1). T(n,3) = A137719(n-2). - R. J. Mathar, Oct 27 2019

T(n,4) = A002264(n-1) + A121262(n). - R. J. Mathar, Oct 28 2019