|
%I M2959 #55 Jun 16 2016 23:27:16
%S 1,3,13,111,1381,25623,678133,26269735,1447451707,114973020921,
%T 13034306495563
%N Erroneous version of A223911: Tiered orders on n nodes.
%C 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
%C A corrected version of this sequence is A223911. - _Joerg Arndt_, Mar 29 2013
%C 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.)
%C 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
%C 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
%C 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_]
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H D. Klarner, <a href="http://dx.doi.org/10.1016/0012-365X(86)90216-5">The number of tiered posets modulo six</a>, Discrete Math., 62 (1986), 295-297.
%H G. Kreweras, <a href="http://dx.doi.org/10.1016/0012-365X(85)90137-2">Dénombrement des ordres étagés</a>, Discrete Math., 53 (1985), 147-149.
%o (PARI) ee(n)={my(f(m,n)=sum(k=0,m,(-1)^(m-k)*binomial(m,k)*(2^k-1)^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,n-h+1),n-h+1]),if(0<m[h]=n-sum(i=1,h-1,m[i]),s+=C(n,m)*prod(i=1,h-1,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
%K dead
%O 1,2
%A _Simon Plouffe_
%E Error in a(8) pointed out by _Michel Marcus_, Nov 03 2012
|
