A079502 -id:A079502 - cp's OEIS frontend

A006327 a(n) = Fibonacci(n) - 3. Number of total preorders.

0, 2, 5, 10, 18, 31, 52, 86, 141, 230, 374, 607, 984, 1594, 2581, 4178, 6762, 10943, 17708, 28654, 46365, 75022, 121390, 196415, 317808, 514226, 832037, 1346266, 2178306, 3524575, 5702884, 9227462, 14930349, 24157814, 39088166, 63245983, 102334152, 165580138

Offset: 4

N. J. A. Sloane, Simon Plouffe

Minimal cost of maximum height Huffman tree of size n. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004

			G.f. = 2*x^5 + 5*x^6 + 10*x^7 + 18*x^8 + 31*x^9 + 52*x^10 + 86*x^11 + ...

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

T. D. Noe, Table of n, a(n) for n = 4..1000
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
A. B. Vinokur, Huffman trees and Fibonacci numbers, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.
Alex Vinokur, Fibonacci connection between Huffman codes and Wythoff array, arXiv:cs/0410013 [cs.DM], 2004-2005.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

A diagonal of A079502.

Cf. A000045, A001611, A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616. [Added by N. J. A. Sloane, Jun 25 2010 in response to a comment from Aviezri S. Fraenkel]

List([4..45], n-> Fibonacci(n)-3) # G. C. Greubel, Jul 13 2019

[Fibonacci(n)-3: n in [4..45]]; // G. C. Greubel, Jul 13 2019

with(combinat):a:=n->sum(fibonacci(j),j=3..n): seq(a(n),n=2..40); # Zerinvary Lajos, Oct 03 2007
A006327:=(2+z)/(z-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation

Fibonacci[Range[4, 45]] - 3 (* Vladimir Joseph Stephan Orlovsky, Mar 19 2010 *)

a(n)=fibonacci(n)-3 \\ Charles R Greathouse IV, Feb 03 2014

[fibonacci(n)-3 for n in (4..45)] # G. C. Greubel, Jul 13 2019

G.f.: x^5*(2 + x)/((1-x)*(1-x-x^2)).
a(n) = a(n-1) + a(n-2) + 3.
a(n+3) = Sum_{k=-n+1..n} F(abs(n)+1). - Paul Barry, Oct 24 2007
a(n) = F(4*n) mod F(n+1) = F(n) - (F(n+4)^2 - F(n)^2)/F(2*n+4). - Gary Detlefs, Apr 02 2012

Offset corrected by Gary Detlefs, Apr 02 2012

A350354 Number of up/down (or down/up) patterns of length n.

Original entry on oeis.org

1, 1, 1, 3, 11, 51, 281, 1809, 13293, 109899, 1009343, 10196895, 112375149, 1341625041, 17249416717, 237618939975, 3491542594727, 54510993341523, 901106621474801, 15723571927404189, 288804851413993941, 5569918636750820751, 112537773142244706427

Offset: 0

Gus Wiseman, Jan 16 2022

nonn

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A patten is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase.
A pattern is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2).
Conjecture: Also the half the number of weakly up/down patterns of length n.
These are the values of the Euler zig-zag polynomials A205497 evaluated at x = 1/2 and normalized by 2^n. - Peter Luschny, Jun 03 2024

			The a(0) = 1 through a(4) = 11 patterns:
  ()  (1)  (1,2)  (1,2,1)  (1,2,1,2)
                  (1,3,2)  (1,2,1,3)
                  (2,3,1)  (1,3,1,2)
                           (1,3,2,3)
                           (1,3,2,4)
                           (1,4,2,3)
                           (2,3,1,2)
                           (2,3,1,3)
                           (2,3,1,4)
                           (2,4,1,3)
                           (3,4,1,2)

Andrew Howroyd, Table of n, a(n) for n = 0..200

The version for permutations is A000111, undirected A001250.
For compositions we have A025048, down/up A025049, undirected A025047.
This is the up/down (or down/up) case of A345194.
A205497 are the Euler zig-zag polynomials.
A000670 counts patterns, ranked by A333217.
A005649 counts anti-run patterns.
A019536 counts necklace patterns.
A226316 counts patterns avoiding (1,2,3), weakly A052709.
A335515 counts patterns matching (1,2,3).
A349058 counts weakly alternating patterns.
A350252 counts non-alternating patterns.
Row sums of A079502.
Cf. A000041, A003242, A049774, A124754, A128761, A335457, A344604, A344605, A344615, A348610.

# Using the recurrence by Kyle Petersen from A205497.
G := proc(n) option remember; local F;
if n = 0 then 1/(1 - q*x) else F := G(n - 1);
simplify((p/(p - q))*(subs({p = q, q = p}, F) - subs(p = q, F))) fi end:
A350354 := n -> 2^n*subs({p = 1, q = 1, x = 1/2}, G(n)*(1 - x)^(n + 1)):
seq(A350354(n), n = 0..22);  # Peter Luschny, Jun 03 2024

allnorm[n_]:=If[n<=0,{{}},Function[s, Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
updoQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]>y[[m+1]],y[[m]]

F(p,x) = {sum(k=0, p, (-1)^((k+1)\2)*binomial((p+k)\2, k)*x^k)}
R(n,k) = {Vec(if(k==1, 0, F(k-2,-x)/F(k-1,x)-1) + x + O(x*x^n))}
seq(n)= {concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Feb 04 2022

a(n > 2) = A344605(n)/2.

a(n > 1) = A345194(n)/2.

Terms a(10) and beyond from Andrew Howroyd, Feb 04 2022

A006328 Total preorders.

Original entry on oeis.org

5, 24, 79, 223, 579, 1432, 3434, 8071, 18714, 42991, 98127, 222965, 505008, 1141236, 2574845, 5802636, 13065935, 29403439, 66141015, 148734156, 334391354, 751675943, 1689494650, 3797059555, 8533209055, 19176039925, 43091557504, 96831330948, 217586892705

Offset: 3

N. J. A. Sloane

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

Colin Barker, Table of n, a(n) for n = 3..1000
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (4,-3,-4,4,1,-1).

A column of A079502.

CoefficientList[ Series[(5 + 4x - 2x^2 - x^3)/(1 - 4x + 3x^2 + 4x^3 - 4 x^4 - x^5 + x^6), {x, 0, 30}], x] (* Robert G. Wilson v, Mar 12 2017 *)

Vec(x^3*(1 + x)*(5 - x - x^2) / ((1 - x)*(1 - x - x^2)*(1 - 2*x - x^2 + x^3)) + O(x^40)) \\ Colin Barker, Mar 19 2017

From Colin Barker, Mar 19 2017: (Start)
G.f.: x^3*(1 + x)*(5 - x - x^2) / ((1 - x)*(1 - x - x^2)*(1 - 2*x - x^2 + x^3)).
a(n) = 4*a(n-1) - 3*a(n-2) - 4*a(n-3) + 4*a(n-4) + a(n-5) - a(n-6) for n>8.
(End)

More terms from Sean A. Irvine, Mar 12 2017

A006326 Total preorders.

Original entry on oeis.org

1, 5, 24, 122, 680, 4155, 27776, 202084, 1592064, 13513825, 123025408, 1196165886, 12374422528, 135740585015, 1573990072320, 19239037403528, 247255523459072, 3333340694137725, 47039231504678912, 693488743931379010, 10661950808321949696, 170659875799127955955

Offset: 3

N. J. A. Sloane

nonn

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

G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)

Cf. A000111, A079502.

# After Alois P. Heinz in A000111:
b := proc(u, o) option remember;
`if`(u + o = 0, 1, add(b(o - 1 + j, u - j), j = 1..u)) end:
a := n -> (n-2)*b(n-1, 1)/2: seq(a(n), n = 3..23); # Peter Luschny, Oct 27 2017

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[o-1+j, u-j], {j, 1, u}]];
a[n_] := (n-2) b[n-1, 1]/2;
Array[a, 22, 3] (* Jean-François Alcover, Jun 01 2019, from Maple *)

More terms from Sean A. Irvine, Mar 12 2017

A006329 Total preorders.

Original entry on oeis.org

1, 10, 79, 602, 4682, 38072, 326570, 2964992, 28506383, 289973248, 3116028865, 35308153600, 421048783264, 5273818620928, 69250997724484, 951571372015616, 13658940616055885, 204474999700324352, 3187421031909630947, 51663403849575956480

Offset: 3

N. J. A. Sloane

nonn

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

G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)

A diagonal of A079502.

More terms from Sean A. Irvine, Mar 12 2017

cp's OEIS Frontend

A006327 a(n) = Fibonacci(n) - 3. Number of total preorders.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A350354 Number of up/down (or down/up) patterns of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A006328 Total preorders.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A006326 Total preorders.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A006329 Total preorders.

Views

Author

Keywords

References

Links

Crossrefs

Extensions