

A026794


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


50



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
(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.
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).
Sum(k*T(n,k),k=1..n) = A046746(n). (End)
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
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

Johannes W. Meijer, Euler's ship on the Pentagonal Sea, pdf and jpg.
Tilman Piesk, First 50 rows and illustrations of columns n = 2, 3, 4, 5, 6, 7, 8. a(n, k) is the number of gray fields in row n of table k.


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_{k>=1} tx^k/(1tx^k)/product(1x^j,j=1..k1).  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
T(k,k) = 1 and T(n,1) = row sum (n1); 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(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
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); # 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(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); # 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$(i1), 1], []);
`if`(i<1, h, p(p(h, b(n, i1)), `if`(n<i, [], b(ni, i))))
end:
T:= n> b(n, n)[]:


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
(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

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


KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



