|
| |
|
|
A026794
|
|
Triangular array T read by rows: T(n,k) = number of partitions of n in which least part is k, 1<=k<=n.
|
|
37
|
|
|
|
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.
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/product(1-x^j, j=k..infinity) (k=1,2,...). 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). - Emeric Deutsch, Feb 19 2006
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
|
|
|
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.
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. 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(tx^k/(1-tx^k)/product(1-x^j,j=1..k-1), k=1..infinity). - 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
|
|
|
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(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
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 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);
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);
(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$(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}]](* From 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))))
|
|
|
CROSSREFS
|
Row sums give A000041.
Cf. A000041, A046746, A008284, A161363, A161364.
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
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
|
| |
|
|
