A008289 Triangle read by rows: Q(n,m) = number of partitions of n into m distinct parts, n>=1, m>=1.

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 3, 1, 4, 4, 1, 1, 5, 5, 1, 1, 5, 7, 2, 1, 6, 8, 3, 1, 6, 10, 5, 1, 7, 12, 6, 1, 1, 7, 14, 9, 1, 1, 8, 16, 11, 2, 1, 8, 19, 15, 3, 1, 9, 21, 18, 5, 1, 9, 24, 23, 7, 1, 10, 27, 27, 10, 1, 1, 10, 30, 34, 13, 1, 1, 11, 33, 39, 18, 2, 1, 11, 37

Offset

1,8

Comments

Row n contains A003056(n) = floor((sqrt(8*n+1)-1)/2) terms (number of terms increases by one at each triangular number). - Michael Somos, Dec 04 2002

Row sums give A000009.

Q(n,m) is the number of partitions of n whose greatest part is m and every number in {1,2,...,m} occurs as a part at least once. - Geoffrey Critzer, Nov 17 2011

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 115.

Links

Alois P. Heinz, Rows n = 1..500 of triangle, flattened (first 200 rows from T. D. Noe)

Eric Weisstein's World of Mathematics, Partition Function Q.

Formula

G.f.: Product_{n>0} (1 + y*x^n) = 1 + Sum_{n>0, k>0} Q(n, k) * x^n * y^k. - Michael Somos, Dec 04 2002

Q(n, k) = Q(n-k, k) + Q(n-k, k-1) for n>k>=1, with Q(1, 1)=1, Q(n, 0)=0 (n>=1). - Paul D. Hanna, Mar 04 2005

G.f.: Sum_{n>0, k>0} x^n * y^(k*(k+1)/2) / Product_{i=1..k} (1 - y^i). - Michael Somos, Jul 11 2017

Sum_{k>=0} k! * Q(n,k) = A032020(n). - Alois P. Heinz, Feb 25 2020

Q(n, m) = A008284(n - m*(m-1)/2, m) = A026820(n - m*(m+1)/2, m), using for the latter, the extension A026820(n, k) = A026820(n, n) = A000041(n), for every k >= n >= 0. - Álvar Ibeas, Jul 23 2020

Example

Q(8,3) = 2 since 8 can be written in 2 ways as sum of 3 distinct positive integers: 5+2+1 and 4+3+1.
Triangle starts:
  1;
  1;
  1,  1;
  1,  1;
  1,  2;
  1,  2,  1;
  1,  3,  1;
  1,  3,  2;
  1,  4,  3;
  1,  4,  4,  1;
  1,  5,  5,  1;
  1,  5,  7,  2;
  1,  6,  8,  3;
  1,  6, 10,  5;
  1,  7, 12,  6,  1;
  1,  7, 14,  9,  1;
  1,  8, 16, 11,  2;
  1,  8, 19, 15,  3;
  1,  9, 21, 18,  5;
  1,  9, 24, 23,  7;
  1, 10, 27, 27, 10,  1;
  1, 10, 30, 34, 13,  1;
  1, 11, 33, 39, 18,  2;
  1, 11, 37, 47, 23,  3;
  1, 12, 40, 54, 30,  5;
  1, 12, 44, 64, 37,  7;
  1, 13, 48, 72, 47, 11;
  1, 13, 52, 84, 57, 14, 1;
  1, 14, 56, 94, 70, 20, 1; ...
Q(8,3) = 2 because there are 2 partitions of 8 in which  1, 2 and 3 occur as a part at least once: (3,2,2,1), (3,2,1,1,1). - Geoffrey Critzer, Nov 17 2011

Maple

g:=product(1+t*x^j, j=1..40): gser:=simplify(series(g, x=0, 32)): P[0]:=1: for n from 1 to 30 do P[n]:=sort(coeff(gser, x^n)) od: for n from 1 to 25 do seq(coeff(P[n], t, j), j=1..floor((sqrt(8*n+1)-1)/2)) od; # yields sequence in triangular form; Emeric Deutsch, Feb 21 2006
# second Maple program:
b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)
      -> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0)))
    end:
T:= n-> subsop(1=NULL, b(n, n))[]:
seq(T(n), n=1..40);  # Alois P. Heinz, Nov 18 2012

Mathematica

q[n_, k_] := q[n, k] = If[n < k || k < 1, 0, If[n == 1, 1, q[n-k, k] + q[n-k, k-1]]]; Take[ Flatten[ Table[q[n, k], {n, 1, 24}, {k, 1, Floor[(Sqrt[8n+1] - 1)/2]}]], 91] (* Jean-François Alcover, Aug 01 2011, after PARI prog. *)
(* As a triangular table: *)
Table[Coefficient[Series[Product[1+t    x^i, {i, n}], {x, 0, n}], x^n t^m], {n, 24}, {m, n}] (* Wouter Meeussen, Feb 22 2014 *)
Table[Count[PowersRepresentations[n, k, 1], _?(Nor[MemberQ[#, 0], MemberQ[Differences@ #, 0]] &)], {n, 23}, {k, Floor[(Sqrt[8 n + 1] - 1)/2]}] // Flatten (* Michael De Vlieger, Jul 12 2017 *)
nrows = 24; d=Table[Select[IntegerPartitions[n], DeleteDuplicates[#] == # &], {n, nrows}] ;
Flatten@Table[Table[Count[d[[n]], x_ /; Length[x] == m], {m, Floor[(Sqrt[8 n + 1] - 1)/2]}], {n, nrows}] (* Robert Price, Aug 17 2020 *)

Prog

(PARI) {Q(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( prod(i=1, n, 1 + y*x^i, 1 + x * O(x^n)), n), k))}; /* Michael Somos, Dec 04 2002 */
(PARI) Q(n, k)=if(n<k || k<1, 0, if(n==1, 1, Q(n-k, k)+Q(n-k, k-1)))
for(n=1, 45, for(k=1, floor((sqrt(8*n+1)-1)/2), print1(Q(n, k), ", ")); print("")) \\ Paul D. Hanna
(PARI) {Q(n, k) = my(u); if( n<1 || k<1 || k>(sqrtint(8*n+1)-1)\2, 0, u = n - k *(k+1)/2; polcoeff( 1 / prod(i=1, k, 1 - x^i, 1 + x*O(x^u)), u))}; /* Michael Somos, Jul 11 2017 */
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A008289_T(n, k):
    if k<1 or n<k: return 0
    if n==1: return 1
    return A008289_T(n-k, k)+A008289_T(n-k, k-1) # Chai Wah Wu, Sep 22 2023

Crossrefs

Cf. A030699, A104382, A117147, A209318.

Sum of n-th row is A000009(n). Sum(Q(n,k)*k, k>=1) = A015723(n).

A060016 is another version.

Cf. A032020.

Sequence in context: A360189 A368210 A233932 * A326625 A188884 A116679

Adjacent sequences: A008286 A008287 A008288 * A008290 A008291 A008292

Keyword

nonn,tabf,easy,nice,look

Author

N. J. A. Sloane

Extensions

Additional comments from Michael Somos, Dec 04 2002

Entry revised by N. J. A. Sloane, Nov 20 2006

Status

approved