|
| |
|
|
A141622
|
|
Triangle read by rows: coefficients of chromatic polynomials for the poset of Dyck paths ordered by inclusion.
|
|
1
| |
|
|
1, 1, 1, -1, 1, -5, 10, -9, 3, 1, -21, 210, -1321, 5823, -18968, 46908, -89034, 129490, -142270, 114532, -63791, 21940, -3499, 1, -84, 3486, -95228, 1924965, -30690520, 401700964, -4436161044, 42161182074, -350011820616, 2567538234448
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,6
|
|
|
COMMENTS
| Number of entries in the rows are the Catalan numbers, see A000108.
|
|
|
REFERENCES
| G. Berman and K. D. Fryer, Introduction to Combinatorics, Academic Press, New York, 1972.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999
|
|
|
LINKS
| Alois P. Heinz, Rows n = 0..5, flattened
Wikipedia, Chromatic Polynomial
J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion
|
|
|
EXAMPLE
| Chromatic polynomial for D_3 is t^5 - 5t^4 + 10t^3 - 9t^2 +3t =>
[1, -5, 10, -9, 3]
Triangle begins:
1;
1;
1, -1;
1, -5, 10, -9, 3;
1, -21, 210, -1321, 5823, -18968, 46908, ...
1, -84, 3486, -95228, 1924965, -30690520, 401700964, ...
|
|
|
MAPLE
| with(networks);
new(G); # this is the graph for D_3
addvertex({1, 2, 3, 4}, G); addedge(Cycle(1, 2, 3, 4), G);
addvertex(5, G); addedge({4, 5}, G); draw(G);
ans:= sort (expand (chrompoly(G, x)));
# 2nd program
with (networks):
d:= proc(x, y, l) option remember;
`if` (x<=1, [[l[], y]], [seq (d(x-1, i, [l[], y])[], i=x-1..y)])
end:
le:= proc(l1, l2) local i;
for i to nops(l1) do if l1[i]>l2[i] then return false fi od;
true
end:
T:= proc(n) local l, m, p;
l:= d(n, n, []); m:= nops(l);
p:= chrompoly (graph ({$1..m}, {seq (seq (`if` (le(l[i], l[j]),
`if`(true in {seq (k<>i and k<>j and le (l[i], l[k])
and le(l[k], l[j]), k=1..m)}, NULL, {i, j}), NULL),
j=i+1..m), i=1..m)}), t);
seq (coeff (p, t, m-i), i=0..m-1)
end:
seq (T(n), n=0..4); # Alois P. Heinz, Jul 24 2011
|
|
|
CROSSREFS
| Cf. A000108.
Sequence in context: A185341 A067843 A109360 * A144136 A198286 A001483
Adjacent sequences: A141619 A141620 A141621 * A141623 A141624 A141625
|
|
|
KEYWORD
| sign,tabf
|
|
|
AUTHOR
| Jennifer Woodcock (Jennifer.Woodcock(AT)ugdsb.on.ca), Aug 23 2008
|
|
|
EXTENSIONS
| More terms from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 24 2011
|
| |
|
|
