cp's OEIS Frontend

A026820 Euler's table: triangular array T read by rows, where T(n,k) = number of partitions in which every part is <= k for 1 <= k <= n. Also number of partitions of n into at most k parts.

%I A026820 #125 Mar 10 2025 13:35:42
%S A026820 1,1,2,1,2,3,1,3,4,5,1,3,5,6,7,1,4,7,9,10,11,1,4,8,11,13,14,15,1,5,10,
%T A026820 15,18,20,21,22,1,5,12,18,23,26,28,29,30,1,6,14,23,30,35,38,40,41,42,
%U A026820 1,6,16,27,37,44,49,52,54,55,56,1,7,19,34,47,58,65,70,73,75,76,77
%N A026820 Euler's table: triangular array T read by rows, where T(n,k) = number of partitions in which every part is <= k for 1 <= k <= n. Also number of partitions of n into at most k parts.
%D A026820 G. Chrystal, Algebra, Vol. II, p. 558.
%D A026820 D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.2, p. 493.
%H A026820 Alois P. Heinz, Robert G. Wilson v, <a href="/A026820/b026820.txt">Rows n = 1..141, flattened</a>
%H A026820 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 A026820 Carolyn Echter, Georg Maier, Juan-Diego Urbina, Caio Lewenkopf, and Klaus Richter, <a href="https://arxiv.org/abs/2409.08696">Many-body density of states of bosonic and fermionic gases: a combinatorial approach</a>, arXiv:2409.08696 [cond-mat.quant-gas], 2024. See p. 10.
%H A026820 L. Euler, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k69587/f335.item">Introductio in Analysin Infinitorum</a>, Book I, chapter XVI.
%H A026820 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 A026820 OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>.
%H A026820 R. Sulzgruber, <a href="https://othes.univie.ac.at/30616/">The Symmetry of the q,t-Catalan Numbers</a>, Masterarbeit, Univ. Wien, 2013.
%H A026820 Sergei Viznyuk, <a href="http://phystech.com/ftp/A026820.c">C program</a>.
%H A026820 Sergei Viznyuk, <a href="/A026820/a026820.c.txt">Local copy of C program</a>.
%H A026820 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PartitionFunctionq.html">Partition Function q</a>.
%H A026820 <a href="/index/Par#partN">Index entries for sequences related to partitions</a> - _Reinhard Zumkeller_, Jan 21 2010
%F A026820 T(T(n,n),n) = A134737(n). - _Reinhard Zumkeller_, Nov 07 2007
%F A026820 T(A000217(n),n) = A173519(n). - _Reinhard Zumkeller_, Feb 20 2010
%F A026820 T(n,k) = T(n,k-1) + T(n-k,k). - _Thomas Dybdahl Ahle_, Jun 13 2011
%F A026820 T(n,k) = Sum_{i=1..min(k,floor(n/2))} T(n-i,i) + Sum_{j=1+floor(n/2)..k} A000041(n-j). - _Bob Selcoe_, Aug 22 2014 [corrected by _Álvar Ibeas_, Mar 15 2018]
%F A026820 O.g.f.: Product_{i>=0} 1/(1-y*x^i). - _Geoffrey Critzer_, Mar 11 2012
%F A026820 T(n,k) = A008284(n+k,k). - _Álvar Ibeas_, Jan 06 2015
%e A026820 Triangle starts:
%e A026820   1;
%e A026820   1, 2;
%e A026820   1, 2,  3;
%e A026820   1, 3,  4,  5;
%e A026820   1, 3,  5,  6,  7;
%e A026820   1, 4,  7,  9, 10, 11;
%e A026820   1, 4,  8, 11, 13, 14, 15;
%e A026820   1, 5, 10, 15, 18, 20, 21, 22;
%e A026820   1, 5, 12, 18, 23, 26, 28, 29, 30;
%e A026820   1, 6, 14, 23, 30, 35, 38, 40, 41, 42;
%e A026820   1, 6, 16, 27, 37, 44, 49, 52, 54, 55, 56;
%e A026820   ...
%p A026820 T:= proc(n, k) option remember;
%p A026820       `if`(n=0 or k=1, 1, T(n, k-1) + `if`(k>n, 0, T(n-k, k)))
%p A026820     end:
%p A026820 seq(seq(T(n, k), k=1..n), n=1..12); # _Alois P. Heinz_, Apr 21 2012
%t A026820 t[n_, k_] := Length@ IntegerPartitions[n, k]; Table[ t[n, k], {n, 12}, {k, n}] // Flatten
%t A026820 (* Second program: *)
%t A026820 T[n_, k_] := T[n, k] = If[n==0 || k==1, 1, T[n, k-1] + If[k>n, 0, T[n-k, k]]]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 22 2015, after _Alois P. Heinz_ *)
%o A026820 (Haskell)
%o A026820 import Data.List (inits)
%o A026820 a026820 n k = a026820_tabl !! (n-1) !! (k-1)
%o A026820 a026820_row n = a026820_tabl !! (n-1)
%o A026820 a026820_tabl = zipWith
%o A026820    (\x -> map (p x) . tail . inits) [1..] $ tail $ inits [1..] where
%o A026820    p 0 _ = 1
%o A026820    p _ [] = 0
%o A026820    p m ks'@(k:ks) = if m < k then 0 else p (m - k) ks' + p m ks
%o A026820 -- _Reinhard Zumkeller_, Dec 18 2013
%o A026820 (PARI) T(n,k)=my(s); forpart(v=n,s++,,k); s \\ _Charles R Greathouse IV_, Feb 27 2018
%o A026820 (SageMath)
%o A026820 from sage.combinat.partition import number_of_partitions_length
%o A026820 from itertools import accumulate
%o A026820 for n in (1..11):
%o A026820     print(list(accumulate([number_of_partitions_length(n, k) for k in (1..n)])))
%o A026820 # _Peter Luschny_, Jul 28 2022
%Y A026820 Partial sums of rows of A008284, row sums give A058397, central terms give A171985, mirror is A058400.
%Y A026820 T(n,n) = A000041(n), T(n,1) = A000012(n), T(n,2) = A008619(n) for n>1, T(n,3) = A001399(n) for n>2, T(n,4) = A001400(n) for n>3, T(n,5) = A001401(n) for n>4, T(n,6) = A001402(n) for n>5, T(n,7) = A008636(n) for n>6, T(n,8) = A008637(n) for n>7, T(n,9) = A008638(n) for n>8, T(n,10) = A008639(n) for n>9, T(n,11) = A008640(n) for n>10, T(n,12) = A008641(n) for n>11, T(n,n-2) = A007042(n-1) for n>2, T(n,n-1) = A000065(n) for n>1.
%Y A026820 Cf. A008284, A026840, A134737, A173519.
%K A026820 nonn,tabl,nice
%O A026820 1,3
%A A026820 _Clark Kimberling_