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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008284 Triangle of partition numbers: T(n,k) = number of partitions of n in which the greatest part is k, 1<=k<=n. Also number of partitions of n into k positive parts (1 <= k <= n). 129
1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 3, 2, 1, 1, 1, 4, 5, 5, 3, 2, 1, 1, 1, 4, 7, 6, 5, 3, 2, 1, 1, 1, 5, 8, 9, 7, 5, 3, 2, 1, 1, 1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1, 1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1, 1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1, 1, 7, 16, 23, 23 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

If k > n/2, T(n,k) = P(n-k) = A000041(n-k). - Franklin T. Adams-Watters, Jan 12 2006

A002865(n) = Sum(a(n-k+1,k-1): 1<k<=floor((n+2)/2). - Reinhard Zumkeller, Nov 04 2007

From Frederik Beaujean (beaujean(AT)mpp.mpg.de), Apr 09 2010: (Start)

A000041(n+1)=1+ Sum( Sum(T(r,k) :1<=k<=Min(r,n-r+1) ) : 1<=r<=n)

T(n, n-k) is also the number of partitions of k in which the greatest part is at most n-k. (End)

A000700(n) = Sum_{k=1..n} (-1)^(n-k) T(n,k). - Jeremy L. Martin, Jul 06 2013

REFERENCES

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 831.

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 94, 96 and 307.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 219.

Martin Griffiths, Generating Functions for Extended Stirling Numbers of the First Kind, Journal of Integer Sequences, 17 (2014), #14.6.4.

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley Professional, 2005, pp. 38, 45, 50 [From Frederik Beaujean (beaujean(AT)mpp.mpg.de), Apr 09 2010]

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.4, p. 400.

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.2, p. 493.

LINKS

Franklin T. Adams-Watters, First 100 rows, flattened

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

H. Bottomley, Illustration of initial terms

D. J. Broadhurst and D. Kreimer, Towards cohomology of renormalization...

W. Lang, First 10 rows and more.

Tilman Piesk, Illustration of initial terms

Eric Weisstein's World of Mathematics, Partition Function P

FORMULA

T(n, k)=Sum{T(n-k, i)}, 1<=i<=k for 1<=k<=n-1; T(n, n)=1 for n >= 1.

Or, T(n, 1) = T(n, n) = 1, T(n, k) = 0 (k>n), T(n, k) = T(n-1, k-1) + T(n-k, k).

G.f. for k-th column: x^k/(product(1-x^j, j=1..k)) - Wolfdieter Lang, Nov 29 2000

G.f.: A(x, y) = Product_{n>=1} 1/(1-x^n)^(P_n(y)/n), where P_n(y) = Sum_{d|n} eulerphi(n/d)*y^d. - Paul D. Hanna, Jul 13 2004

G.f.=G(t,x)=-1+1/product(1-tx^j,j=1..infinity). - Emeric Deutsch, Feb 12 2006

EXAMPLE

The triangle T(n,k) begins:

n/k  1  2  3  4  5  6  7  8  9  10 11 12...

1:   1

2:   1  1

3:   1  1  1

4:   1  2  1  1

5:   1  2  2  1  1

6:   1  3  3  2  1  1

7:   1  3  4  3  2  1  1

8:   1  4  5  5  3  2  1  1

9:   1  4  7  6  5  3  2  1  1

10:  1  5  8  9  7  5  3  2  1  1

11:  1  5  10 11 10 7  5  3  2  1  1

12:  1  6  12 15 13 11 7  5  3  2  1  1

... Reformatted and extended by Wolfdieter Lang, Dec 03 2012; additional extension by Bob Selcoe, Jun 09 2013

T(7,3)=4 because we have [3,3,1], [3,2,2], [3,2,1,1] and [3,1,1,1,1], each having greatest part 3; or [5,1,1], [4,2,1], [3,3,1] and [3,2,2] each having 3 parts.

* Example from formula above: T(10,4) = 9 because T(6,4) + T(6,3) + T(6,2) + T(6,1) = 2 + 3 + 3 + 1 = 9.

* P(n) = P(n-1) + DT(n-1).  P(n) = unordered partitions of n. (A000041)  DT(n-1) = sum of diagonals beginning at T(n-1,1).

Example P(11) = 56, P(10) = 42, sum DT(10) = 1 + 4 + 5 + 3 + 1 = 14. - Bob Selcoe, Jun 09 2013

MAPLE

G:=-1+1/product(1-t*x^j, j=1..15): Gser:=simplify(series(G, x=0, 17)): for n from 1 to 14 do P[n]:=coeff(Gser, x^n) od: for n from 1 to 14 do seq(coeff(P[n], t^j), j=1..n) od; # yields sequence in triangular form - Emeric Deutsch, Feb 12 2006

with(combstruct):for n from 0 to 18 do seq(count(Partition(n), size=m), m = 1 .. n) od; # [From Zerinvary Lajos, Mar 30 2009]

T := proc(n, k) option remember; if k < 0 or n < 0 then 0 elif k = 0 then if n = 0 then 1 else 0 fi else T(n - 1, k - 1) + T(n - k, k) fi end: seq(print(seq(T(n, k), k=1..n)), n=1..14); # Peter Luschny, Jul 24 2011

MATHEMATICA

Column[Table[ IntegerPartitions[n, {k}] // Length, {n, 1, 20}, {k, 1, n}], Center] [From Frederik Beaujean (beaujean(AT)mpp.mpg.de), Apr 09 2010]

PROG

(Haskell)

a008284 n k = a008284_tabl !! (n-1) !! (k-1)

a008284_row n = a008284_tabl !! (n-1)

a008284_tabl = [1] : f [[1]] where

   f xss = ys : f (ys : xss) where

     ys = (map sum $ zipWith take [1..] xss) ++ [1]

-- Reinhard Zumkeller, Sep 05 2014

CROSSREFS

Cf. A000041 (row sums and diagonal), A038497, A038498, A039805-A039809, A060016. Read from right to left gives A058398. Partial sums of rows gives A026820.

Column 3 is A001399.

First difference triangle of triangle A026820.

Subtriangle of A072233 without row n=0 and column m=0.

Sequence in context: A219347 A114087 A215521 * A114088 A208245 A037306

Adjacent sequences:  A008281 A008282 A008283 * A008285 A008286 A008287

KEYWORD

nonn,tabl,nice,easy,look

AUTHOR

N. J. A. Sloane

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 25 20:39 EDT 2014. Contains 248557 sequences.