|
|
A026807
|
|
Triangular array T read by rows: T(n,k) = number of partitions of n in which every part is >=k, for k=1,2,...,n.
|
|
28
|
|
|
1, 2, 1, 3, 1, 1, 5, 2, 1, 1, 7, 2, 1, 1, 1, 11, 4, 2, 1, 1, 1, 15, 4, 2, 1, 1, 1, 1, 22, 7, 3, 2, 1, 1, 1, 1, 30, 8, 4, 2, 1, 1, 1, 1, 1, 42, 12, 5, 3, 2, 1, 1, 1, 1, 1, 56, 14, 6, 3, 2, 1, 1, 1, 1, 1, 1, 77, 21, 9, 5, 3, 2, 1, 1, 1, 1, 1, 1, 101, 24, 10, 5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 135, 34, 13
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
T(n,g) is also the number of not necessarily connected 2-regular graphs with girth at least g: the part i corresponds to the i-cycle; addition of integers corresponds to disconnected union of cycles. - Jason Kimberley, Feb 05 2012
|
|
LINKS
|
|
|
FORMULA
|
G.f.: Sum_{k>=1} y^k*(-1+1/Product_{i>=0} (1-x^(k+i))). - Vladeta Jovovic, Jun 22 2003
|
|
EXAMPLE
|
Sum_{k>=1} y^k*(-1+1/Product_{i>=0} (1-x^(k+i))) = y*x+(2*y+y^2)*x^2+(3*y+y^2+y^3)*x^3+(5*y+2*y^2+y^3+y^4)*x^4+(7*y+2*y^2+y^3+y^4+y^5)*x^5+...
1;
2, 1;
3, 1, 1;
5, 2, 1, 1;
7, 2, 1, 1, 1;
11, 4, 2, 1, 1, 1;
15, 4, 2, 1, 1, 1, 1;
22, 7, 3, 2, 1, 1, 1, 1;
30, 8, 4, 2, 1, 1, 1, 1, 1;
42, 12, 5, 3, 2, 1, 1, 1, 1, 1;
56, 14, 6, 3, 2, 1, 1, 1, 1, 1, 1;
77, 21, 9, 5, 3, 2, 1, 1, 1, 1, 1, 1;
101, 24, 10, 5, 3, 2, 1, 1, 1, 1, 1, 1, 1;
n = 12, k = 4, t = A000217(k-1) = 6
T(12, 4) = vp * transpose(vc) = 77-56-42+22+15-11 = 5
(End)
|
|
MAPLE
|
T:= proc(n, k) option remember;
`if`(k<1 or k>n, 0, `if`(n=k, 1, T(n, k+1) +T(n-k, k)))
end:
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[ k<1 || k>n, 0, If[n == k, 1, T[n, k+1] + T[n-k, k]]]; Table [Table[ T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)
|
|
PROG
|
(Haskell)
import Data.List (tails)
a026807 n k = a026807_tabl !! (n-1) !! (k-1)
a026807_row n = a026807_tabl !! (n-1)
a026807_tabl = map
(\row -> map (p $ last row) $ init $ tails row) a002260_tabl
where p 0 _ = 1
p _ [] = 0
p m ks'@(k:ks) = if m < k then 0 else p (m - k) ks' + p m ks
(Python)
from see_there import a231599_row # A231599
from sympy.ntheory import npartitions # A000041
def a026807(n, k):
if k > n:
return 0
elif k > n/2:
return 1
else:
vc = a231599_row(k-1)
t = len(vc)
vp_range = range(n-t, n+1)
vp_range = vp_range[::-1] # reverse
r = 0
for i in range(0, t):
r += vc[i] * npartitions(vp_range[i])
return r
|
|
CROSSREFS
|
Not necessarily connected 2-regular graphs with girth at least g [partitions into parts >= g]: this sequence (triangle); columns of this sequence: 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
|
|
|
STATUS
|
approved
|
|
|
|