|
%I #225 Sep 28 2023 13:18:09
%S 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,
%T 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,
%U 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
%N 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.
%C From Frederik Beaujean (beaujean(AT)mpp.mpg.de), Apr 09 2010: (Start)
%C A000041(n+1) = 1 + Sum_{r=1..n} Sum_{k=1..min(r,n-r+1)} T(r,k).
%C T(n, n-k) is also the number of partitions of k in which the greatest part is at most n-k. (End)
%C From _Richard R. Forberg_, Dec 26 2014: (Start)
%C 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.
%C The diagonal T(2+2k, k), for k > 1 equals A007042, and the diagonal T(3+3k,k), for k >= 1, equals A104384. (End)
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 94, 96 and 307.
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 219.
%D 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 D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.4, p. 400.
%D D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.2, p. 493.
%H Franklin T. Adams-Watters, <a href="/A008284/b008284.txt">First 200 rows, flattened</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, p. 831. [scanned copy]
%H Henry Bottomley, <a href="/A008284/a008284.gif">Illustration of initial terms</a>
%H D. J. Broadhurst and D. Kreimer, <a href="http://arXiv.org/abs/hep-th/0001202">Towards cohomology of renormalization: bigrading the combinatorial Hopf algebra of rooted trees</a>, arXiv:hep-th/0001202, 2000.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000010/">The length of the partition</a>
%H Martin Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Griffiths/griffiths31.html">Generating Functions for Extended Stirling Numbers of the First Kind</a>, Journal of Integer Sequences, 17 (2014), #14.6.4.
%H Roser Homs and Anna-Lena Winz, <a href="https://arxiv.org/abs/2309.06871">Deformations of local Artin rings via Hilbert-Burch matrices</a>, arXiv:2309.06871 [math.AC], 2023. See p. 16.
%H Wolfdieter Lang, <a href="/A008284/a008284.txt">First 10 rows and more.</a>
%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
%H OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>
%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:Partitions_of_n_with_biggest_addend_k.svg">Illustration of initial terms</a>
%H Teerapat Srichan, Watcharapon Pimsert, and Vichian Laohakosol, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Pimsert/pim2.html">New Recursion Formulas for the Partition Function</a>, J. Int. Seq., Vol. 24 (2021), Article 21.6.6.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PartitionFunctionP.html">Partition Function P</a>
%H <a href="/index/Mu#multiplicative_completely">Index entries for triangles generated by the Multiset Transformation</a>
%F T(n, k) = Sum_{i=1..k} T(n-k, i), for 1 <= k <= n-1; T(n, n) = 1 for n >= 1.
%F 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).
%F G.f. for k-th column: x^k/(Product_{j=1..k} (1-x^j)). - _Wolfdieter Lang_, Nov 29 2000
%F 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
%F 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]
%F G.f.: G(t,x) = -1 + 1/Product_{j>=1} (1-t*x^j). - _Emeric Deutsch_, Feb 12 2006
%F A002865(n) = Sum_{k=2..floor((n+2)/2)} T(n-k+1,k-1). - _Reinhard Zumkeller_, Nov 04 2007
%F A000700(n) = Sum_{k=1..n} (-1)^(n-k) T(n,k). - _Jeremy L. Martin_, Jul 06 2013
%F 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
%F 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
%F 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)
%F 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
%e The triangle T(n,k) begins:
%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 ...
%e 1: 1
%e 2: 1 1
%e 3: 1 1 1
%e 4: 1 2 1 1
%e 5: 1 2 2 1 1
%e 6: 1 3 3 2 1 1
%e 7: 1 3 4 3 2 1 1
%e 8: 1 4 5 5 3 2 1 1
%e 9: 1 4 7 6 5 3 2 1 1
%e 10: 1 5 8 9 7 5 3 2 1 1
%e 11: 1 5 10 11 10 7 5 3 2 1 1
%e 12: 1 6 12 15 13 11 7 5 3 2 1 1
%e ... Reformatted and extended by _Wolfdieter Lang_, Dec 03 2012; additional extension by _Bob Selcoe_, Jun 09 2013
%e 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.
%e * 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.
%e * 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).
%e Example P(11) = 56, P(10) = 42, sum DT(10) = 1 + 4 + 5 + 3 + 1 = 14. - _Bob Selcoe_, Jun 09 2013
%e From _Omar E. Pol_, Nov 19 2019: (Start)
%e 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:
%e .
%e 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
%e .
%e _| _| | _| | | _| | | | _| | | | | _| | | | | | _| | | | | | |
%e _ _| _ _| | _ _| | | _ _| | | | _ _| | | | | _ _| | | | | |
%e _ _ _| _ _ _| | _ _ _| | | _ _ _| | | | _ _ _| | | | |
%e _ _| | _ _| | | _ _| | | | _ _| | | | |
%e _ _ _ _| _ _ _ _| | _ _ _ _| | | _ _ _ _| | | |
%e _ _ _| | _ _ _| | | _ _ _| | | |
%e _ _ _ _ _| _ _ _ _ _| | _ _ _ _ _| | |
%e _ _| | | _ _| | | |
%e _ _ _ _| | _ _ _ _| | |
%e _ _ _| | _ _ _| | |
%e _ _ _ _ _ _| _ _ _ _ _ _| |
%e _ _ _| | |
%e _ _ _ _ _| |
%e _ _ _ _| |
%e _ _ _ _ _ _ _|
%e (End)
%p 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
%p with(combstruct):for n from 0 to 18 do seq(count(Partition(n), size=m), m = 1 .. n) od; # _Zerinvary Lajos_, Mar 30 2009
%p 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
%t Column[Table[ IntegerPartitions[n, {k}] // Length, {n, 1, 20}, {k, 1, n}], Center] (* Frederik Beaujean (beaujean(AT)mpp.mpg.de), Apr 09 2010 *)
%t (*Recurrence closely related to natural numbers and number of divisors of n*)
%t 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 *)
%t 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 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]]
%t Table[T[n, k], {n, 1, 20}, {k, 1, n}] // Flatten (* _Robert A. Russell_, May 12 2018 after Knuth 7.2.1.4 (39) *)
%o (Haskell)
%o a008284 n k = a008284_tabl !! (n-1) !! (k-1)
%o a008284_row n = a008284_tabl !! (n-1)
%o a008284_tabl = [1] : f [[1]] where
%o f xss = ys : f (ys : xss) where
%o ys = (map sum $ zipWith take [1..] xss) ++ [1]
%o -- _Reinhard Zumkeller_, Sep 05 2014
%o (Sage)
%o from sage.combinat.partition import number_of_partitions_length
%o [[number_of_partitions_length(n, k) for k in (1..n)] for n in (1..12)] # _Peter Luschny_, Aug 01 2015
%o (PARI) T(n,k)=#partitions(n-k,k)
%o for(n=1,9,for(k=1,n,print1(T(n,k)", "))) \\ _Charles R Greathouse IV_, Jan 04 2016
%o (PARI) A8284=[]; A008284(n,k)={for(n=#A8284+1,n,A8284=concat(A8284,[vector(n,k,if(2*k<n,if(k>1,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
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A008284_T(n,k):
%o if k==n or k==1: return 1
%o if k>n: return 0
%o return A008284_T(n-1,k-1)+A008284_T(n-k,k) # _Chai Wah Wu_, Sep 21 2023
%Y A000041 is row sums and diagonal.
%Y Columns k=1-10 are: A057427, A004526, A069905, A026810, A026811, A026812, A026813, A026814, A026815, A026816.
%Y Partial sums of rows gives A026820.
%Y Cf. A038497, A038498, A039805-A039809, A060016, A126988.
%Y Read from right to left gives A058398.
%Y Subtriangle of A072233 without row n=0 and column m=0.
%Y Cf. A007042, A104384 which are diagonals with slope -2, -3.
%K nonn,tabl,nice,easy,look
%O 1,8
%A _N. J. A. Sloane_
|
