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