

A006860


Erroneous version of A223911: Tiered orders on n nodes.
(Formerly M2959)


6



1, 3, 13, 111, 1381, 25623, 678133, 26269735, 1447451707, 114973020921, 13034306495563
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

WARNING: The currently listed value of a(8) is inconsistent with the result from Kreweras and Klarner quoted below, as pointed out by Michel Marcus.  M. F. Hasler, Nov 03 2012
A corrected version of this sequence is A223911.  Joerg Arndt, Mar 29 2013
Graded posets, i.e., those in which every maximal chain has the same length. (The terminology "graded" is also used to refer to a weaker notion; see A001833.)
Kreweras observed and Klarner proved that a(n) is congruent to 1 (resp. 3) modulo 6 when n is odd (resp. even).  Michel Marcus, Nov 03 2012
Using the formulas in the paper from Klarner (cf. PARI code), I get 1, 3, 13, 85, 801, 10231, 168253, 3437673, 85162465, 2511412651, 86805640461, 3469622549053, ...  M. F. Hasler, Nov 07 2012
The values currently in the sequence through 25623 are certainly correct (I've enumerated these posets by brute force and other methods). (...) Klarner's eq.(2) contains a typo: instead of f(m_1, m_h) it should be f(m_1, m_2). (The point here is that the Hasse diagram of each of these posets decomposes as a bunch of bipartite graphs layered on top of each other; there are f(m_1, m_2) ways to choose the bipartite graph between the first two ranks of vertices, then f(m_2, m_3) ways to choose the bipartite graph between the second and third ranks of vertices, etc.) (...). When I implement Klarner's eqs.(1) and (2) (corrected) I get the following sequence: 1, 3, 13, 111, 1381, 25623, 678133, 26169951, 1447456261, 114973232583, ... Now we get the right terms up as far as I personally have experience (...) and they agree with Kreweras (and the current OEIS sequence) until a(8), at which point there is disagreement. [Joel Brewster Lewis, Mar 06 2013; private communication to M. F. Hasler]


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=1..11.
D. Klarner, The number of tiered posets modulo six, Discrete Math., 62 (1986), 295297.
G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147149.


PROG

(PARI) ee(n)={my(f(m, n)=sum(k=0, m, (1)^(mk)*binomial(m, k)*(2^k1)^n), C(n, m)=n!/prod(i=1, #m, m[i]!), t(h, n)=my(s=0); forvec(m=vector(h, i, [if(i<h, 1, nh+1), nh+1]), if(0<m[h]=nsum(i=1, h1, m[i]), s+=C(n, m)*prod(i=1, h1, f(m[i], m[h])))); s); sum(h=1, n, t(h, n))} \\ This implements the formula in Klarner's paper, where equation 2 contains a typo. It does NOT yield the correct terms.  M. F. Hasler, Nov 07 2012


CROSSREFS

Sequence in context: A228563 A222863 A223911 * A181083 A090537 A063269
Adjacent sequences: A006857 A006858 A006859 * A006861 A006862 A006863


KEYWORD

dead


AUTHOR

Simon Plouffe


EXTENSIONS

Error in a(8) pointed out by Michel Marcus, Nov 03 2012


STATUS

approved



