login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008289 Triangle read by rows: Q(n,m) = number of partitions of n into m distinct parts, n>=1, m>=1. 35
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 (list; graph; refs; listen; history; text; internal format)
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).

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

T. D. Noe and 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.

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

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 *)

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))

(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 */

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.

Sequence in context: A075104 A253667 A233932 * A188884 A116679 A146290

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 13:33 EST 2017. Contains 295876 sequences.