login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; text; 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: A280943 A316707 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, Jul 24 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 15:34 EST 2019. Contains 320374 sequences. (Running on oeis4.)