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. 139
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_{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)

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

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. - Richard R. Forberg, Dec 26 2014

The diagonal T(2+2k, k), for k > 1 equals A007042, and the diagonal T(3+3k,k), for k >=1, equals A104384. - Richard R. Forberg, Dec 26 2014

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 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, p. 831. [scanned copy]

H. 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.

W. 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

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

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

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

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

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

(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

CROSSREFS

A000041 is row sums and diagonal.

Column 3 is A001399.

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 29 03:15 EDT 2016. Contains 273487 sequences.