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
Examples
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
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)
- Carolyn Echter, Georg Maier, Juan-Diego Urbina, Caio Lewenkopf, and Klaus Richter, Many-body density of states of bosonic and fermionic gases: a combinatorial approach, arXiv:2409.08696 [cond-mat.quant-gas], 2024. See p. 10.
- Eric Weisstein's World of Mathematics, Partition Function Q.
Crossrefs
Programs
-
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 *) -
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
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
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
Extensions
Additional comments from Michael Somos, Dec 04 2002
Entry revised by N. J. A. Sloane, Nov 20 2006
Comments