|
| |
|
|
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, 1-x^j ) (k>=1).
Row sums yield the partition numbers (A000041).
T(n,1) = A000041(n-1) (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 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
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
|
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(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)[]:
|
|
|
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
|
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
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
