A143674 -id:A143674 - cp's OEIS frontend

A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.

1, 2, 4, 24, 816, 239968, 808814912, 38764383658368, 31491961129357837056, 503091371552266970507912704, 179763631086276515267399940231898112, 1609791936564515363272979180683040232936253440

Offset: 0

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Aug 28 2008

nonn

For each n, each vertex in the Hasse diagram of the poset corresponds to a Dyck path of size n. The chain polynomial, C(P,t)=(1 + sum_k(c_k*t^(k+1)), gives the breakdown of this sequence by number of vertices in the chain. The 1 in front of the sum in this equation denotes the empty chain. The coefficient, c_k, gives the number of chains of length k and the exponent, (k+1), indicates the number of vertices in the chain. Here are the chain polynomials corresponding to this sequence:
n=0 1
n=1 1 + t
n=2 1 + 2t + t^2
n=3 1 + 5t + 9t^2 + 7t^3 + 2t^4
n=4 1 + 14t + 70t^2 + 176 t^3+249t^4 + 202t^5 + 88 t^6 + 16 t^7
n=5 1 + 42t + 552t^2 + 3573t^3 + 13609t^4+ 33260 t^5 + 54430t^6 + 60517t^7 + 45248t^8 + 21824t^9 + 6144t^(10) + 768t^(11)
Note that for each n, the coefficient of t is equal to the Catalan number, C_n. It is well-known that the number of Dyck paths in D_n is given by C_n (A000108). The coefficient in front of the largest power of t gives the number of maximal (and also maximum) chains (A005118).

			a(3) = 24 since in D_3 there are 2 chains of length 3 (i.e., on 4 vertices in the Hasse diagram), 7 chains of length 2 (on 3 vertices), 9 chains of length 1 (on 2 vertices), 5 chains of length 0 (on 1 vertex) and the empty chain: 2 + 7 + 9 + 5 + 1 = 24 chains.

R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.

J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Cf. A143673, A143674, A193629. Chains on one vertex: A000108. Number of maximal chains: A005118.

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:
a:= proc(n) option remember; local l, m, g;
      if n=0 then return 1 fi;
      l:= d(n, n, []); m:= nops(l);
      g:= proc(t) option remember;
            1 +add(`if`(le(l[d], l[t]), g(d), 0), d=1..t-1);
          end;
      1+ add(g(h), h=1..m)
    end:
seq(a(n), n=0..7);  # Alois P. Heinz, Jul 26 2011

a(n) = 1 + Sum_{i,j in {1..C(n)}} (2*delta - zeta)^(-1)[i,j] where delta is the identity matrix and the zeta matrix is defined: zeta[a,b] = 1 if a<=b in D_n and 0 otherwise.

a(6)-a(11), from Alois P. Heinz, Jul 26 2011, Aug 01 2011

A143673 Number of antichains in the poset of Dyck paths ordered by inclusion.

Original entry on oeis.org

2, 2, 3, 7, 42, 2361, 37620704

Offset: 0

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Aug 28 2008

Also the number of order ideals (down-sets) for this poset.
This is the breakdown by size of (or number of elements in) the antichains beginning with antichains of size 0 and increasing:
n=0: 1,   1;
n=1: 1,   1;
n=2: 1,   2;
n=3: 1,   5,    1;
n=4: 1,  14,   21,     6;
n=5: 1,  42,  309,   793,    810,     348,      56,       2;
n=6: 1, 132, 4059, 54706, 390885, 1648100, 4380095, 7682096, 9172750, 7585779, 4370731, 1749626, 481189, 89055, 10676, 785, 38, 1;
Note that the number of maximum antichains (for each n) is given by the rightmost entry in each of these rows.

			For n = 3 there are 7 antichains. Assume that the five elements in the D_3 poset are depicted using a Hasse diagram and labeled A through E from bottom to top. Then the 7 antichains are: { }, {A}, {B}, {C}, {D}, {E}, {B,C}.

R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.

J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Cf. A143672. Number of maximal antichains A143674.

a(6) from Alois P. Heinz, Jul 28 2011

A358563 The number of maximal antichains in the Tamari lattice of order n.

Original entry on oeis.org

1, 2, 4, 26, 1979, 161117453

Offset: 1

Dmitry I. Ignatov, Nov 22 2022

Also the number of maximal order ideals in the Tamari lattice of order n.

Maximal antichains are those which cannot be extended without violating the antichain condition.

			The line (Hasse) diagram of the Tamari lattice for n=3 is
     ((ab)c)d
      /     \
 (a(bc))d (ab)(cd)
     |       /
  a((bc)d)  /
      \    /
     a(b(cd))
with the a(3)=4 maximal antichains {((ab)c)d}, {(ab)(cd), (a(bc))d}, {(ab)(cd), a((bc)d)}, {a(b(cd))}.

D. Tamari, The algebra of bracketings and their enumeration, Nieuw Archief voor Wiskunde, Series 3, 10 (1962), 131-146.

S. Huang and D. Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. of Comb. Theory, Series A, 13 (1972), 7-13.
Dmitry I. Ignatov, Supporting iPython code and input files for counting (maximal) antichains of the Tamari partition lattice up to n=5, Github repository.
Wikipedia, Tamari lattice

Cf. A358562 (number of antichains in the Tamari lattice).
Cf. A326358 (number of maximal antichains in the Boolean lattice).
Cf. A358041 (number of maximal antichains in the lattice of set partitions of an n-element set).
Cf. A358390 (number of maximal antichains in the Kreweras lattice of non-crossing set partitions).
Cf. A143674 (number of maximal antichains in the lattice of Dyck paths).

cp's OEIS Frontend

A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A143673 Number of antichains in the poset of Dyck paths ordered by inclusion.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A358563 The number of maximal antichains in the Tamari lattice of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs