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.

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, 20, 15, 11, 7, 5, 3, 2, 1, 1

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• nice
• easy
• look

Comments

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

A000041(n+1) = 1 + Sum_{r=1..n} Sum_{k=1..min(r,n-r+1)} T(r,k).

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

From Richard R. Forberg, Dec 26 2014: (Start)

Elements of T(n, k) for n <= 2+3k, equal A000041(n-k) - A000070(n-2k-1), with the assumption A000070(n) = 0 for n < 0.

The diagonal T(2+2k, k), for k > 1 equals A007042, and the diagonal T(3+3k,k), for k >= 1, equals A104384. (End)

T(-n, k) is used as a definition for A380038, which can therefore be seen as an extension of this sequence for negative n. - Friedjof Tellkamp, Jan 18 2025

Examples

			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
From _Omar E. Pol_, Nov 19 2019: (Start)
Illustration of initial terms: T(n,k) is also the number of vertical line segments in the k-th column of the n-th diagram, which represents the partitions of n:
.
    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
.
   _|   _| |   _| | |   _| | | |   _| | | | |   _| | | | | |   _| | | | | | |
        _ _|   _ _| |   _ _| | |   _ _| | | |   _ _| | | | |   _ _| | | | | |
               _ _ _|   _ _ _| |   _ _ _| | |   _ _ _| | | |   _ _ _| | | | |
                        _ _|   |   _ _|   | |   _ _|   | | |   _ _|   | | | |
                        _ _ _ _|   _ _ _ _| |   _ _ _ _| | |   _ _ _ _| | | |
                                   _ _ _|   |   _ _ _|   | |   _ _ _|   | | |
                                   _ _ _ _ _|   _ _ _ _ _| |   _ _ _ _ _| | |
                                                _ _|   |   |   _ _|   |   | |
                                                _ _ _ _|   |   _ _ _ _|   | |
                                                _ _ _|     |   _ _ _|     | |
                                                _ _ _ _ _ _|   _ _ _ _ _ _| |
                                                               _ _ _|   |   |
                                                               _ _ _ _ _|   |
                                                               _ _ _ _|     |
                                                               _ _ _ _ _ _ _|
(End)
		

References

• 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.
• 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.
• James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 294.

Links

• Franklin T. Adams-Watters, First 200 rows, flattened
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, p. 831. [scanned copy]
• Henry Bottomley, Illustration of initial terms
• D. J. Broadhurst and D. Kreimer, Towards cohomology of renormalization: bigrading the combinatorial Hopf algebra of rooted trees, arXiv:hep-th/0001202, 2000.
• FindStat - Combinatorial Statistic Finder, The length of the partition
• Martin Griffiths, Generating Functions for Extended Stirling Numbers of the First Kind, Journal of Integer Sequences, 17 (2014), #14.6.4.
• Roser Homs and Anna-Lena Winz, Deformations of local Artin rings via Hilbert-Burch matrices, arXiv:2309.06871 [math.AC], 2023. See p. 16.
• Wolfdieter Lang, First 10 rows and more.
• T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
• OEIS Wiki, Sorting numbers
• Tilman Piesk, Illustration of initial terms
• Stephan Scholz and Lothar Berger, Fast computation of function composition derivatives for flatness-based control of diffusion problems, J. Math. Industry (2024) Vol. 14, Art. No. 15.
• Teerapat Srichan, Watcharapon Pimsert, and Vichian Laohakosol, New Recursion Formulas for the Partition Function, J. Int. Seq., Vol. 24 (2021), Article 21.6.6.
• Eric Weisstein's World of Mathematics, Partition Function P
• Index entries for triangles generated by the Multiset Transformation

Crossrefs

A000041 is row sums and diagonal.

Columns k=1-10 are: A057427, A004526, A069905, A026810, A026811, A026812, A026813, A026814, A026815, A026816.

Partial sums of rows gives A026820.

Cf. A038497, A038498, A039805-A039809, A060016, A126988, A380038.

Read from right to left gives A058398.

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

Cf. A007042, A104384 which are diagonals with slope -2, -3.

Programs

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

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; # 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] (* Frederik Beaujean (beaujean(AT)mpp.mpg.de), Apr 09 2010 *)
(*Recurrence closely related to natural numbers and number of divisors of n*)
Clear[t]; nn = 14; t[n_, 1] = 1; t[n_, k_] := t[n, k] = If[n >= k, Sum[t[n - i, k - 1], {i, 1, n - 1}] - Sum[t[n - i, k], {i, 1, k - 1}], 0];Flatten[Table[Table[t[n, k], {k, 1, n}], {n, 1, nn}]][[1 ;; 96]] (* Mats Granvik, Jan 01 2015 *)
Table[SeriesCoefficient[1/QPochhammer[a q, q], {q, 0, n}, {a, 0, k}], {n, 1, 15}, {k, 1, n}] // Column (* Vladimir Reshetnikov, Nov 18 2016 *)
T[n_, k_] := T[n, k] = If[n>0 && k>0, T[n-1, k-1] + T[n-k, k], Boole[n==0 && k==0]]
Table[T[n, k], {n, 1, 20}, {k, 1, n}] // Flatten (* Robert A. Russell, May 12 2018 after Knuth 7.2.1.4 (39) *)

PARI

T(n,k)=#partitions(n-k,k)
for(n=1,9,for(k=1,n,print1(T(n,k)", "))) \\ Charles R Greathouse IV, Jan 04 2016

PARI

A8284=[]; A008284(n,k)={for(n=#A8284+1,n,A8284=concat(A8284,[vector(n,k,if(2*k1,A8284[n-k][k]+A8284[n-1][k-1],1),numbpart(n-k)))]));if(k,A8284[n][k],A8284[n])} \\ Without 2nd argument, return row n. - M. F. Hasler, Sep 26 2017

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A008284_T(n,k):
    if k==n or k==1: return 1
    if k>n: return 0
    return A008284_T(n-1,k-1)+A008284_T(n-k,k) # Chai Wah Wu, Sep 21 2023

Sage

from sage.combinat.partition import number_of_partitions_length
[[number_of_partitions_length(n, k) for k in (1..n)] for n in (1..12)] # Peter Luschny, Aug 01 2015

Formula

T(n, k) = Sum_{i=1..k} T(n-k, i), 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_{j=1..k} (1-x^j)). - 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

If k >= n/2, T(n,k) = T(2(n-k),n-k) = A000041(n-k). - Franklin T. Adams-Watters, Jan 12 2006 [Relation included by Hans Loeblich, Apr 16 2019, relation extended by Evan Robinson, Jun 30 2021]

G.f.: G(t,x) = -1 + 1/Product_{j>=1} (1-t*x^j). - Emeric Deutsch, Feb 12 2006

A002865(n) = Sum_{k=2..floor((n+2)/2)} T(n-k+1,k-1). - Reinhard Zumkeller, Nov 04 2007

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

G.f.: -1 + e^(F(x,z)), where F(x,z) = Sum_{n >= 1} (x*z)^n/(n*(1 - z^n)) is a g.f. for A126988. - Peter Bala, Jan 13 2015

Also, T(n, n-k) = k for k = 1, 2, 3; n >= 2k. T(n, 2) = floor(n/2). T(n, 3) = round(n^2/12). - M. F. Hasler, Sep 26 2017

T(n,k) = [n>0 & k>0] * (T(n-1,k-1) + T(n-k,k)) + [n==0 & k==0]. - Robert A. Russell, May 12 2018 from Knuth 7.2.1.4 (39)

T(n, k) = Sum_{i=0..n-1} T(n-ik-1, k-1) for k >= 1; T(-n, k) = 0 for n > 0; T(n, 0) = [n==0]. - Joshua Swanson (writing for Juexian Li), May 24 2020