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.
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, 15, 18, 20, 21, 22, 1, 5, 12, 18, 23, 26, 28, 29, 30, 1, 6, 14, 23, 30, 35, 38, 40, 41, 42, 1, 6, 16, 27, 37, 44, 49, 52, 54, 55, 56, 1, 7, 19, 34, 47, 58, 65, 70, 73, 75, 76, 77
Offset: 1
Examples
Triangle starts: 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, 15, 18, 20, 21, 22; 1, 5, 12, 18, 23, 26, 28, 29, 30; 1, 6, 14, 23, 30, 35, 38, 40, 41, 42; 1, 6, 16, 27, 37, 44, 49, 52, 54, 55, 56; ...
References
- G. Chrystal, Algebra, Vol. II, p. 558.
- D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.2, p. 493.
Links
- Alois P. Heinz, Robert G. Wilson v, Rows n = 1..141, 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]
- Carolyn Echter, Georg Maier, Juan-Diego Urbina, Caio Lewenkopf, and Klaus Richter, Many-body density of states of bosonic and fermionic gases: a combinatorial approach, arXiv:2409.08696 [cond-mat.quant-gas], 2024. See p. 10.
- L. Euler, Introductio in Analysin Infinitorum, Book I, chapter XVI.
- 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.
- R. Sulzgruber, The Symmetry of the q,t-Catalan Numbers, Masterarbeit, Univ. Wien, 2013.
- Sergei Viznyuk, C program.
- Sergei Viznyuk, Local copy of C program.
- Eric Weisstein's World of Mathematics, Partition Function q.
- Index entries for sequences related to partitions - _Reinhard Zumkeller_, Jan 21 2010
Crossrefs
Partial sums of rows of A008284, row sums give A058397, central terms give A171985, mirror is A058400.
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.
Programs
-
Haskell
import Data.List (inits) a026820 n k = a026820_tabl !! (n-1) !! (k-1) a026820_row n = a026820_tabl !! (n-1) a026820_tabl = zipWith (\x -> map (p x) . tail . inits) [1..] $ tail $ inits [1..] where p 0 _ = 1 p _ [] = 0 p m ks'@(k:ks) = if m < k then 0 else p (m - k) ks' + p m ks -- Reinhard Zumkeller, Dec 18 2013
-
Maple
T:= proc(n, k) option remember; `if`(n=0 or k=1, 1, T(n, k-1) + `if`(k>n, 0, T(n-k, k))) end: seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Apr 21 2012 -
Mathematica
t[n_, k_] := Length@ IntegerPartitions[n, k]; Table[ t[n, k], {n, 12}, {k, n}] // Flatten (* Second program: *) 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 *) -
PARI
T(n,k)=my(s); forpart(v=n,s++,,k); s \\ Charles R Greathouse IV, Feb 27 2018
-
SageMath
from sage.combinat.partition import number_of_partitions_length from itertools import accumulate for n in (1..11): print(list(accumulate([number_of_partitions_length(n, k) for k in (1..n)]))) # Peter Luschny, Jul 28 2022
Formula
T(T(n,n),n) = A134737(n). - Reinhard Zumkeller, Nov 07 2007
T(n,k) = T(n,k-1) + T(n-k,k). - Thomas Dybdahl Ahle, Jun 13 2011
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]
O.g.f.: Product_{i>=0} 1/(1-y*x^i). - Geoffrey Critzer, Mar 11 2012
T(n,k) = A008284(n+k,k). - Álvar Ibeas, Jan 06 2015