cp's OEIS Frontend

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

%I A008289 #105 Feb 16 2025 08:32:32
%S A008289 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,
%T A008289 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,
%U A008289 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
%N A008289 Triangle read by rows: Q(n,m) = number of partitions of n into m distinct parts, n>=1, m>=1.
%C A008289 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
%C A008289 Row sums give A000009.
%C A008289 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
%D A008289 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 115.
%H A008289 Alois P. Heinz, <a href="/A008289/b008289.txt">Rows n = 1..500 of triangle, flattened</a> (first 200 rows from T. D. Noe)
%H A008289 Carolyn Echter, Georg Maier, Juan-Diego Urbina, Caio Lewenkopf, and Klaus Richter, <a href="https://arxiv.org/abs/2409.08696">Many-body density of states of bosonic and fermionic gases: a combinatorial approach</a>, arXiv:2409.08696 [cond-mat.quant-gas], 2024. See p. 10.
%H A008289 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PartitionFunctionQ.html">Partition Function Q.</a>
%F A008289 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
%F A008289 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
%F A008289 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
%F A008289 Sum_{k>=0} k! * Q(n,k) = A032020(n). - _Alois P. Heinz_, Feb 25 2020
%F A008289 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
%e A008289 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.
%e A008289 Triangle starts:
%e A008289   1;
%e A008289   1;
%e A008289   1,  1;
%e A008289   1,  1;
%e A008289   1,  2;
%e A008289   1,  2,  1;
%e A008289   1,  3,  1;
%e A008289   1,  3,  2;
%e A008289   1,  4,  3;
%e A008289   1,  4,  4,  1;
%e A008289   1,  5,  5,  1;
%e A008289   1,  5,  7,  2;
%e A008289   1,  6,  8,  3;
%e A008289   1,  6, 10,  5;
%e A008289   1,  7, 12,  6,  1;
%e A008289   1,  7, 14,  9,  1;
%e A008289   1,  8, 16, 11,  2;
%e A008289   1,  8, 19, 15,  3;
%e A008289   1,  9, 21, 18,  5;
%e A008289   1,  9, 24, 23,  7;
%e A008289   1, 10, 27, 27, 10,  1;
%e A008289   1, 10, 30, 34, 13,  1;
%e A008289   1, 11, 33, 39, 18,  2;
%e A008289   1, 11, 37, 47, 23,  3;
%e A008289   1, 12, 40, 54, 30,  5;
%e A008289   1, 12, 44, 64, 37,  7;
%e A008289   1, 13, 48, 72, 47, 11;
%e A008289   1, 13, 52, 84, 57, 14, 1;
%e A008289   1, 14, 56, 94, 70, 20, 1; ...
%e A008289 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
%p A008289 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
%p A008289 # second Maple program:
%p A008289 b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)
%p A008289       -> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0)))
%p A008289     end:
%p A008289 T:= n-> subsop(1=NULL, b(n, n))[]:
%p A008289 seq(T(n), n=1..40);  # _Alois P. Heinz_, Nov 18 2012
%t A008289 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. *)
%t A008289 (* As a triangular table: *)
%t A008289 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 *)
%t A008289 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 *)
%t A008289 nrows = 24; d=Table[Select[IntegerPartitions[n], DeleteDuplicates[#] == # &],{n, nrows}] ;
%t A008289 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 *)
%o A008289 (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 */
%o A008289 (PARI) Q(n,k)=if(n<k || k<1,0,if(n==1,1,Q(n-k,k)+Q(n-k,k-1)))
%o A008289 for(n=1,45, for(k=1, floor((sqrt(8*n+1)-1)/2), print1(Q(n, k), ", ")); print("")) \\ _Paul D. Hanna_
%o A008289 (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 */
%o A008289 (Python)
%o A008289 from functools import lru_cache
%o A008289 @lru_cache(maxsize=None)
%o A008289 def A008289_T(n,k):
%o A008289     if k<1 or n<k: return 0
%o A008289     if n==1: return 1
%o A008289     return A008289_T(n-k,k)+A008289_T(n-k,k-1) # _Chai Wah Wu_, Sep 22 2023
%Y A008289 Cf. A030699, A104382, A117147, A209318.
%Y A008289 Sum of n-th row is A000009(n). Sum(Q(n,k)*k, k>=1) = A015723(n).
%Y A008289 A060016 is another version.
%Y A008289 Cf. A032020.
%K A008289 nonn,tabf,easy,nice,look
%O A008289 1,8
%A A008289 _N. J. A. Sloane_
%E A008289 Additional comments from _Michael Somos_, Dec 04 2002
%E A008289 Entry revised by _N. J. A. Sloane_, Nov 20 2006