A038497 -id:A038497 - cp's OEIS frontend

A096797 Triangle of coefficients, read by row polynomials P_n(y), that satisfy the g.f.: A038497(x,y) = Product_{n>=1} 1/(1-x^n)^[P_n(y)/n], with P_n(0)=0 for n>=1 and P_0(0)=1.

1, 3, 1, 8, 0, 1, 16, -1, 0, 1, 34, -15, 0, 0, 1, 54, -40, 3, 0, 0, 1, 104, -119, 21, 0, 0, 0, 1, 156, -260, 88, -1, 0, 0, 0, 1, 261, -576, 305, -27, 0, 0, 0, 0, 1, 382, -1111, 850, -155, 3, 0, 0, 0, 0, 1, 615, -2167, 2167, -638, 33, 0, 0, 0, 0, 0, 1, 842, -3854, 5056, -2164, 240, -1, 0, 0, 0, 0, 0, 1

Offset: 1

Paul D. Hanna, Jul 13 2004

A038497 is the matrix square of partition triangle A008284. The first column forms the Moebius transform of {n*A000041(n), n>=1}. The inverse Moebius transform of each column forms the columns of triangle {n/k*A096798(n,k)}.

			1/A038497(x,y) =
(1-x)^y*(1-x^2)^[(3y+y^2)/2]*(1-x^3)^[(8y+y^3)/3]*(1-x^4)^[(16y-y^2+y^4)/
4]*(1-x^5)^[(34y-15y^2+y^5)/5]*...
Rows begin:
[1],
[3,1],
[8,0,1],
[16,-1,0,1],
[34,-15,0,0,1],
[54,-40,3,0,0,1],
[104,-119,21,0,0,0,1],
[156,-260,88,-1,0,0,0,1],
[261,-576,305,-27,0,0,0,0,1],
[382,-1111,850,-155,3,0,0,0,0,1],
[615,-2167,2167,-638,33,0,0,0,0,0,1],
[842,-3854,5056,-2164,240,-1,0,0,0,0,0,1],
[1312,-6916,11089,-6409,1183,-39,0,0,0,0,0,0,1],
[1782,-11649,23037,-17241,4704,-343,3,0,0,0,0,0,0,1],...

Cf. A038497, A008284, A096798.

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.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

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)
T(-n, k) is used as a definition for A380038, which can therefore be seen as an extension of this sequence for negative n. - Friedjof Tellkamp, Jan 18 2025

			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)

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.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 294.

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.
Roser Homs and Anna-Lena Winz, Deformations of local Artin rings via Hilbert-Burch matrices, arXiv:2309.06871 [math.AC], 2023. See p. 16.
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
Stephan Scholz and Lothar Berger, Fast computation of function composition derivatives for flatness-based control of diffusion problems, J. Math. Industry (2024) Vol. 14, Art. No. 15.
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
Index entries for triangles generated by the Multiset Transformation

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(maxsize=None)
def A008284_T(n,k):
    if k==n or k==1: return 1
    if k>n: return 0
    return A008284_T(n-1,k-1)+A008284_T(n-k,k) # Chai Wah Wu, Sep 21 2023

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

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

A038498 Matrix inverse of partition triangle A008284.

Original entry on oeis.org

1, -1, 1, 0, -1, 1, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, 1, 0, -1, -1, 1, -1, 1, 1, 0, -1, -1, 1, -1, 0, 2, 0, 0, -1, -1, 1, 0, -1, 0, 2, 0, 0, -1, -1, 1, 0, -2, 1, 1, 1, 0, 0, -1, -1, 1, 1, -2, -1, 1, 1, 1, 0, 0, -1, -1, 1, 1, -1, -2, 0, 2, 0, 1, 0, 0, -1, -1, 1

Offset: 1

Christian G. Bower, Feb 15 1999

Since A008284 has only ones in its first column, the sum of terms for any row n > 1 is 0. - François Marques, Feb 09 2021

			Triangle begins:
  1;
  -1,1;
  0,-1,1;
  1,-1,-1,1;
  ...

Cf. A008284, A038497, A039800-A039810, A010815.

tp(n, k) = if (n<1, 0, if (k<1, 0, if (k == n, 1, if (k > n, 0, tp(n-1, k-1) + tp(n-k, k)))));
tabl(nn) = {mtp = matrix(nn, nn, n, k, tp(n, k)); mtpi = mtp^(-1); for (n = 1, nn, for (k = 1, n, print1(mtpi[n, k], ", ");); print(););} \\ Michel Marcus, Mar 04 2014

T(n,n-k) = A010815(k) for k <= n/2. - François Marques, Feb 09 2021

A039805 Matrix cube of partition triangle A008284.

Original entry on oeis.org

1, 3, 1, 6, 3, 1, 13, 9, 3, 1, 23, 19, 9, 3, 1, 44, 42, 22, 9, 3, 1, 74, 80, 48, 22, 9, 3, 1, 129, 154, 99, 51, 22, 9, 3, 1, 210, 273, 193, 105, 51, 22, 9, 3, 1, 345, 484, 362, 212, 108, 51, 22, 9, 3, 1, 542, 815, 651, 401, 218, 108, 51, 22, 9, 3, 1, 858, 1369, 1147

Offset: 1

Christian G. Bower, Feb 15 1999

Row sums form A022812 (number of terms in n-th derivative of a function composed with itself 4 times). - Paul D. Hanna, Jul 13 2004

			1; 3,1; 6,3,1; 13,9,3,1; ...

Cf. A038497, A038498, A039806, A039807. a(n, 1) = A022811(n) (first column).

Cf. A022812.

A039807 Matrix 5th power of partition triangle A008284.

Original entry on oeis.org

1, 5, 1, 15, 5, 1, 45, 20, 5, 1, 110, 60, 20, 5, 1, 271, 170, 65, 20, 5, 1, 599, 426, 185, 65, 20, 5, 1, 1309, 1025, 486, 190, 65, 20, 5, 1, 2690, 2299, 1185, 501, 190, 65, 20, 5, 1, 5436, 4999, 2750, 1245, 506, 190, 65, 20, 5, 1, 10545, 10380, 6069, 2910, 1260

Offset: 0

Christian G. Bower, Feb 15 1999

			1; 5,1; 15,5,1; 45,20,5,1; ...

Cf. A038497, A038498, A039805, A039806. a(n, 1) = A022813(n) (first column).

A050304 Matrix 10th power of partition triangle A008284.

Original entry on oeis.org

1, 10, 1, 55, 10, 1, 265, 65, 10, 1, 1045, 320, 65, 10, 1, 3817, 1365, 330, 65, 10, 1, 12583, 5127, 1420, 330, 65, 10, 1, 39148, 17710, 5447, 1430, 330, 65, 10, 1, 114235, 56638, 19030, 5502, 1430, 330, 65, 10, 1, 318857, 170993, 61865, 19350, 5512

Offset: 1

Christian G. Bower, Aug 15 1999

			1; 10,1; 55,10,1; 265,65,10,1; ...

Cf. A038497, A038498, A039805-A039807. A050300-A050303. a(n, 1) = A024210(n) (first column).

A050300 Matrix 6th power of partition triangle A008284.

Original entry on oeis.org

1, 6, 1, 21, 6, 1, 71, 27, 6, 1, 196, 92, 27, 6, 1, 532, 288, 98, 27, 6, 1, 1301, 799, 309, 98, 27, 6, 1, 3101, 2100, 891, 315, 98, 27, 6, 1, 6956, 5145, 2373, 912, 315, 98, 27, 6, 1, 15217, 12121, 5980, 2465, 918, 315, 98, 27, 6, 1, 31951, 27247, 14292, 6253

Offset: 1

Christian G. Bower, Aug 15 1999

			1; 6,1; 21,6,1; 71,27,6,1; ...

Cf. A038497, A038498, A039805-A039807. A050301-A050304. a(n, 1) = A022814(n) (first column).

A039806 Matrix 4th power of partition triangle A008284.

Original entry on oeis.org

1, 4, 1, 10, 4, 1, 26, 14, 4, 1, 55, 36, 14, 4, 1, 121, 91, 40, 14, 4, 1, 237, 202, 101, 40, 14, 4, 1, 468, 439, 238, 105, 40, 14, 4, 1, 867, 887, 524, 248, 105, 40, 14, 4, 1, 1597, 1758, 1105, 560, 252, 105, 40, 14, 4, 1, 2821, 3325, 2223, 1190, 570, 252, 105, 40

Offset: 0

Christian G. Bower, Feb 15 1999

Row sums form A022813 (number of terms in n-th derivative of a function composed with itself 5 times). - Paul D. Hanna, Jul 13 2004

			1; 4,1; 10,4,1; 26,14,4,1; ...

Cf. A038497, A038498, A039805, A039807. a(n, 1) = A022812(n) (first column).

Cf. A022813.

A050301 Matrix 7th power of partition triangle A008284.

Original entry on oeis.org

1, 7, 1, 28, 7, 1, 105, 35, 7, 1, 322, 133, 35, 7, 1, 952, 455, 140, 35, 7, 1, 2541, 1379, 483, 140, 35, 7, 1, 6539, 3920, 1512, 490, 140, 35, 7, 1, 15833, 10375, 4354, 1540, 490, 140, 35, 7, 1, 37148, 26243, 11803, 4487, 1547, 490, 140, 35, 7, 1, 83594

Offset: 1

Christian G. Bower, Aug 15 1999

			1; 7,1; 28,7,1; 105,35,7,1; ...

Cf. A038497, A038498, A039805-A039807. A050300-A050304. a(n, 1) = A024207(n) (first column).

A050303 Matrix 9th power of partition triangle A008284.

Original entry on oeis.org

1, 9, 1, 45, 9, 1, 201, 54, 9, 1, 735, 246, 54, 9, 1, 2517, 981, 255, 54, 9, 1, 7785, 3453, 1026, 255, 54, 9, 1, 22857, 11238, 3699, 1035, 255, 54, 9, 1, 63024, 33930, 12183, 3744, 1035, 255, 54, 9, 1, 166819, 97038, 37464, 12429, 3753, 1035, 255, 54, 9, 1

Offset: 1

Christian G. Bower, Aug 15 1999

			1; 9,1; 45,9,1; 201,54,9,1; ...

Cf. A038497, A038498, A039805-A039807. A050300-A050304. a(n, 1) = A024209(n) (first column).

cp's OEIS Frontend

A096797 Triangle of coefficients, read by row polynomials P_n(y), that satisfy the g.f.: A038497(x,y) = Product_{n>=1} 1/(1-x^n)^[P_n(y)/n], with P_n(0)=0 for n>=1 and P_0(0)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

A038498 Matrix inverse of partition triangle A008284.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A039805 Matrix cube of partition triangle A008284.

Views

Author

Keywords

Comments

Examples

Crossrefs

A039807 Matrix 5th power of partition triangle A008284.

Views

Author

Keywords

Examples

Crossrefs

A050304 Matrix 10th power of partition triangle A008284.

Views

Author

Keywords

Examples

Crossrefs

A050300 Matrix 6th power of partition triangle A008284.

Views

Author

Keywords

Examples

Crossrefs

A039806 Matrix 4th power of partition triangle A008284.

Views

Author

Keywords

Comments

Examples

Crossrefs

A050301 Matrix 7th power of partition triangle A008284.

Views

Author

Keywords

Examples

Crossrefs

A050303 Matrix 9th power of partition triangle A008284.

Views

Author

Keywords

Examples

Crossrefs