OFFSET
1,4
COMMENTS
At least one part is k and each part is at least k.
From Emeric Deutsch, Feb 19 2006: (Start)
Also number of partitions of n in which the largest part occurs exactly k times. Example: T(6,2)=2 because we have [3,3] and [2,2,1,1].
G.f. of column k is x^k/prod(j>=k, 1-x^j ) (k>=1).
Row sums yield the partition numbers (A000041).
T(n,1) = A000041(n-1) (the partition numbers).
T(n,2) = A002865(n-2) (n>=2).
T(n,3)=A026796(n). T(n,4) = A026797(n). T(n,5) = A026798(n). T(n,6) = A026799(n). T(n,7) = A026800(n). T(n,8) = A026801(n). T(n,9) = A026802(n). T(n,10) = A026803(n).
Sum(k*T(n,k),k=1..n) = A046746(n). (End)
Triangle inverse = A161363. - Gary W. Adamson, Jun 07 2009
T(n,g) is also the number of not necessarily connected 2-regular graphs with girth exactly g: the part i corresponds to the i-cycle; addition of integers corresponds to disconnected union of cycles. - Jason Kimberley, Feb 05 2012
From Bob Selcoe, Jul 24 2014 (Start):
Below is a process to generate equations for column k.
Let P be the partition numbers A000041(n-j) and let f(k) denote equations which generate column k.
To find f(k), start with f(1) = P(n-j), j=1. Thus T(n,1) = f(1) = P(n-1). This is the equation for column 1.
To find f(k) k>1, first sum the terms of f(k-1) replacing the value j with j+1, and then subtract the terms of f(k-1) replacing the value j with j+k. So to find f(2) (i.e., the equation for column 2, where k=2), start with f(1) = P(n-1); first replace j with j+1 (yielding P(n-2)), and then replace j with j+2 (yielding P(n-3)). Subtracting the second term from the first, we get: f(2) = P(n-2) - P(n-3).
To find f(3), start with f(2), replace j with j+1 (yielding P(n-3) - P(n-4)) and then replace j with j+3 (yielding P(n-5) - P(n-6)). Subtracting the second group of terms from the first, we get: f(3) = P(n-3) - P(n-4) - P(n-5) + P(n-6). This is the equation for column 3; also the equation for T(n,3) = A026796(n). So for example, T(13,3) = 5 because P(13-3) - P(13-4) - P(13-5) + P(13-6) = 42 - 30 - 22 + 15 = 5.
Continue as above to find f(k) k={4..inf.}. This will generate equations for T(n,4) = A026797(n), T(n,5) = A026798(n), T(n,6) = A026799(n), ad inf.
(End)
LINKS
Alois P. Heinz, Rows n = 1..141, flattened
Kevin Brown, On Euler's Pentagonal Theorem, 1994-2008.
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth exactly g.
J. W. Meijer and M. Nepveu, Euler's ship on the Pentagonal Sea, Acta Nova, Volume 4, No. 1, December 2008. pp. 176-187.
FORMULA
T(n, k) = sum{T(n-k, i), k<=i<=n-k} for k=1, 2, ..., m, T(n, k)=0 for k=m+1, ..., n-1, where m=floor(n/2); T(n, n)=1 for n >= 1.
G.f.: G(t,x)=sum(t^i*x^i/product(1-x^j, j=i..infinity), i=1..infinity). - Emeric Deutsch, Feb 19 2006
G.f.: Sum_{k>=1} tx^k/(1-tx^k)/product(1-x^j,j=1..k-1). - Emeric Deutsch, Mar 13 2006
T(n,k) = T(n-1,k-1) - T(n-k,k-1) for n>=2 and 2<=k<=(n-1) with T(n,1) = A000041(n-1), T(n,n) = 1 for n>=1 and T(n,k) = 0 for k>n. - Johannes W. Meijer, Jun 21 2010
T(k,k) = 1 and T(n,1) = row sum (n-1); thus Meijer's 2010 formula generates the triangle without a priori reference to A000041 (the partition sequence). - Bob Selcoe, Sep 03 2016
EXAMPLE
T(12,3) = 4 because we have [9,3], [6,3,3], [5,4,3] and [3,3,3,3]. - Edited by Bob Selcoe, Sep 03 2016
Triangle starts:
1;
1, 1;
2, 0, 1;
3, 1, 0, 1;
5, 1, 0, 0, 1;
7, 2, 1, 0, 0, 1;
11, 2, 1, 0, 0, 0, 1;
15, 4, 1, 1, 0, 0, 0, 1;
22, 4, 2, 1, 0, 0, 0, 0, 1;
30, 7, 2, 1, 1, 0, 0, 0, 0, 1;
42, 8, 3, 1, 1, 0, 0, 0, 0, 0, 1;
56, 12, 4, 2, 1, 1, 0, 0, 0, 0, 0, 1;
77, 14, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1;
101, 21, 6, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1;
135, 24, 9, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1;
...
MAPLE
g:=sum(t^i*x^i/product(1-x^j, j=i..30), i=1..30): gser:=simplify(series(g, x=0, 19)): for n from 1 to 15 do P[n]:=coeff(gser, x^n) od: for n from 1 to 15 do seq(coeff(P[n], t^j), j=1..n) od; # Emeric Deutsch, Feb 19 2006
nmax:=13; for n from 1 to nmax do T(n, n):=1 od: for n from 1 to nmax do for k from floor(n/2)+1 to n-1 do T(n, k):=0 od: od: for n from 2 to nmax do for k from 1 to floor(n/2) do T(n, k):=sum(T(n-k, i), i=k..n-k) od: od: seq(seq(T(n, k), k=1..n), n=1..nmax); # Johannes W. Meijer, Jun 21 2010
nmax:=13; with(combinat): for n from 1 to nmax do for k from n+1 to nmax do T(n, k):=0 od: od: for n from 1 to nmax do T(n, 1):=numbpart(n-1) od: for n from 1 to nmax do T(n, n):=1 od: for n from 2 to nmax do for k from 2 to n-1 do T(n, k) := T(n-1, k-1) - T(n-k, k-1) od: od: seq(seq(T(n, k), k=1..n), n=1..nmax); # Johannes W. Meijer, Jun 21 2010
#
p:= (f, g)-> zip((x, y)-> x+y, f, g, 0):
b:= proc(n, i) option remember; local h;
h:= `if`(n=i and i>0, [0$(i-1), 1], []);
`if`(i<1, h, p(p(h, b(n, i-1)), `if`(n<i, [], b(n-i, i))))
end:
T:= n-> b(n, n)[]:
seq(T(n), n=1..14); # Alois P. Heinz, Mar 28 2012
MATHEMATICA
t[n_, k_] /; k<1 || k>n = 0; t[n_, n_] = 1; t[n_, k_] := t[n, k] = Sum[t[n-k, i], {i, k, n-k}]; Flatten[ Table[t[n, k], {n, 1, 14}, {k, 1, n}]] (* Jean-François Alcover, May 11 2012, after PARI *)
PROG
(PARI) {T(n, k) = if( k<1 || k>n, 0, if( n==k, 1, sum(i=k, n-k, T(n-k, i))))} \\ Michael Somos, Feb 06 2003
(PARI) A026794(n, k)=#select(p->p[1]==k, partitions(n, [k, n])) \\ For illustration: Creates the list of all partitions of n with smallest part equal to k. - M. F. Hasler, Jun 14 2018
CROSSREFS
Row sums give A000041.
Not necessarily connected 2-regular graphs with girth at least g [partitions into parts >= g]: A026807 (triangle); chosen g: A000041 (g=1 -- multigraphs with loops allowed), A002865 (g=2 -- multigraphs with loops forbidden), A008483 (g=3), A008484 (g=4), A185325(g=5), A185326 (g=6), A185327 (g=7), A185328 (g=8), A185329 (g=9). For g >= 3, girth at least g implies no loops or parallel edges. - Jason Kimberley, Feb 05 2012
Not necessarily connected 2-regular graphs with girth exactly g [partitions with smallest part g]: this sequence (triangle); chosen g: A002865 (g=2), A026796 (g=3), A026797 (g=4), A026798 (g=5), A026799 (g=6), A026800(g=7), A026801 (g=8), A026802 (g=9), A026803 (g=10). - Jason Kimberley, Feb 05 2012
KEYWORD
AUTHOR
EXTENSIONS
More terms from Emeric Deutsch, Feb 19 2006
STATUS
approved