The OEIS is supported by the many generous donors to the OEIS Foundation. 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. 290
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,8 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) 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. 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. 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 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 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 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 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) 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) *) PROG (Haskell) a008284 n k = a008284_tabl !! (n-1) !! (k-1) a008284_row n = a008284_tabl !! (n-1) a008284_tabl =  : f [] where    f xss = ys : f (ys : xss) where      ys = (map sum \$ zipWith take [1..] xss) ++  -- Reinhard Zumkeller, Sep 05 2014 (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 (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 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. 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. Sequence in context: A219347 A114087 A215521 * A114088 A208245 A309049 Adjacent sequences:  A008281 A008282 A008283 * A008285 A008286 A008287 KEYWORD nonn,tabl,nice,easy,look AUTHOR STATUS approved

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

Last modified October 1 16:19 EDT 2022. Contains 357149 sequences. (Running on oeis4.)