

A026794


Triangular array T read by rows: T(n,k) = number of partitions of n in which least part is k, 1<=k<=n.


38



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



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, 1x^j ) (k>=1).
Row sums yield the partition numbers (A000041).
T(n,1) = A000041(n1) (the partition numbers).
T(n,2) = A002865(n2) (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 2regular graphs with girth exactly g: the part i corresponds to the icycle; 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(nj) and let f(k) denote equations which generate column k.
To find f(k), start with f(1) = P(nj), j=1. Thus T(n,1) = f(1) = P(n1). This is the equation for column 1.
To find f(k) k>1, first sum the terms of f(k1) replacing the value j with j+1, and then subtract the terms of f(k1) 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(n1); first replace j with j+1 (yielding P(n2)), and then replace j with j+2 (yielding P(n3)). Subtracting the second term from the first, we get: f(2) = P(n2)  P(n3).
To find f(3), start with f(2), replace j with j+1 (yielding (P(n3)  P(n4)) and then replace j with j+3 (yielding (P(n5)  P(n6)). Subtracting the second group of terms from the first, we get: f(3) = P(n3)  P(n4)  P(n5) + P(n6). 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(133)  P(134)  P(135) + P(136) = 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, 19942008.
Jason Kimberley, Index of sequences counting not necessarily connected kregular simple graphs with girth exactly g.
Johannes W. Meijer, Euler's ship on the Pentagonal Sea, pdf and jpg.
J. W. Meijer and M. Nepveu, Euler's ship on the Pentagonal Sea, Acta Nova, Volume 4, No. 1, December 2008. pp. 176187.


FORMULA

T(n, k) = sum{T(nk, i), k<=i<=nk} for k=1, 2, ..., m, T(n, k)=0 for k=m+1, ..., n1, where m=floor(n/2); T(n, n)=1 for n >= 1.
G.f. = G(t,x)=sum(t^i*x^i/product(1x^j, j=i..infinity), i=1..infinity).  Emeric Deutsch, Feb 19 2006
G.f. = sum(tx^k/(1tx^k)/product(1x^j,j=1..k1), k=1..infinity).  Emeric Deutsch, Mar 13 2006
T(n,k) = T(n1,k1)  T(nk,k1) for n>=2 and 2<=k<=(n1) with T(n,1) = A000041(n1), T(n,n) = 1 for n>=1 and T(n,k) = 0 for k>n.  Johannes W. Meijer, Jun 21 2010


EXAMPLE

T(6,2)=2 because we have [4,2] and [2,2,2].
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;


MAPLE

g:=sum(t^i*x^i/product(1x^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
Contribution from Johannes W. Meijer, Jun 21 2010: (Start)
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 n1 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(nk, i), i=k..nk) od: od: seq(seq(T(n, k), k=1..n), n=1..nmax);
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(n1) 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 n1 do T(n, k) := T(n1, k1)  T(nk, k1) od: od: seq(seq(T(n, k), k=1..n), n=1..nmax);
(End)
#
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$(i1), 1], []);
`if`(i<1, h, p(p(h, b(n, i1)), `if`(n<i, [], b(ni, 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[nk, i], {i, k, nk}]; Flatten[ Table[t[n, k], {n, 1, 14}, {k, 1, n}]](* JeanFranç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, nk, T(nk, i))))}; /* Michael Somos, Feb 06 2003 */


CROSSREFS

Row sums give A000041.
Cf. A000041, A046746, A008284, A161363, A161364, A238341.
Not necessarily connected 2regular 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 2regular 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
Sequence in context: A079217 A079221 A168019 * A137712 A194711 A168532
Adjacent sequences: A026791 A026792 A026793 * A026795 A026796 A026797


KEYWORD

nonn,tabl,easy


AUTHOR

Clark Kimberling


EXTENSIONS

More terms from Emeric Deutsch, Feb 19 2006


STATUS

approved



