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)
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.
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
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
CROSSREFS
KEYWORD
AUTHOR
EXTENSIONS
Additional comments from Michael Somos, Dec 04 2002
Entry revised by N. J. A. Sloane, Nov 20 2006
STATUS
approved