A141622 - OEIS

%I #16 Dec 28 2014 17:45:20

%S 1,1,1,-1,1,-5,10,-9,3,1,-21,210,-1321,5823,-18968,46908,-89034,

%T 129490,-142270,114532,-63791,21940,-3499,1,-84,3486,-95228,1924965,

%U -30690520,401700964,-4436161044,42161182074,-350011820616,2567538234448

%N Triangle read by rows: coefficients of chromatic polynomials for the poset of Dyck paths ordered by inclusion.

%C Number of entries in the rows are the Catalan numbers, see A000108.

%D G. Berman and K. D. Fryer, Introduction to Combinatorics, Academic Press, New York, 1972.

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999

%H Alois P. Heinz, <a href="/A141622/b141622.txt">Rows n = 0..5, flattened</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Chromatic_polynomial">Chromatic Polynomial</a>

%H J. Woodcock, <a href="http://garsia.math.yorku.ca/~zabrocki/papers/DPfinal.pdf">Properties of the poset of Dyck paths ordered by inclusion</a>

%e Chromatic polynomial for D_3 is t^5 - 5t^4 + 10t^3 - 9t^2 +3t =>

%e     [1, -5, 10, -9, 3]

%e Triangle begins:

%e 1;

%e 1;

%e 1,  -1;

%e 1,  -5,   10,     -9,       3;

%e 1, -21,  210,  -1321,    5823,    -18968,     46908, ...

%e 1, -84, 3486, -95228, 1924965, -30690520, 401700964, ...

%p with(networks);

%p new(G); # this is the graph for D_3

%p addvertex({1, 2, 3, 4}, G); addedge(Cycle(1, 2, 3, 4), G);

%p addvertex(5, G); addedge({4, 5}, G); draw(G);

%p ans:= sort (expand (chrompoly(G, x)));

%p # 2nd program

%p with(networks):

%p d:= proc(x, y, l) option remember;

%p        `if`(x<=1, [[l[], y]], [seq(d(x-1, i, [l[], y])[], i=x-1..y)])

%p     end:

%p le:= proc(l1, l2) local i;

%p        for i to nops(l1) do if l1[i]>l2[i] then return false fi od;

%p        true

%p      end:

%p T:= proc(n) local l, m, p;

%p       l:= d(n, n, []);  m:= nops(l);

%p       p:= chrompoly(graph({$1..m}, {seq(seq(`if`(le(l[i], l[j]),

%p            `if`(true in {seq(k<>i and k<>j and le(l[i], l[k])

%p                   and le(l[k], l[j]), k=1..m)}, NULL, {i, j}), NULL),

%p                   j=i+1..m), i=1..m)}), t);

%p       seq(coeff(p, t, m-i), i=0..m-1)

%p     end:

%p seq(T(n), n=0..4);  # _Alois P. Heinz_, Jul 24 2011

%Y Cf. A000108.

%K sign,tabf

%O 0,6

%A Jennifer Woodcock (Jennifer.Woodcock(AT)ugdsb.on.ca), Aug 23 2008

%E More terms from _Alois P. Heinz_, Jul 24 2011