|
|
A082582
|
|
Expansion of (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) in powers of x.
|
|
62
|
|
|
1, 1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
a(n) is the number of Dyck paths of semilength n with no UUDD. See A025242 for a bijection between paths avoiding DDUU versus UUDD.
Also number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1. - Alois P. Heinz, Oct 07 2015
a(n) is the number of bargraphs of semiperimeter n (n>=2). Example: a(4) = 5; the 5 bargraphs correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3]. - Emeric Deutsch, May 20 2016 [a(n) are the row sums of A271942 for n >= 2. Peter Luschny, Oct 18 2020]
a(n) is the number of skew Motzkin paths of length n. A skew Motzkin path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down), F=(1,0) (flat) and A=(-1,1) (anti-down) so that down and anti-down steps do not overlap. - Sergey Kirgizov, Oct 03 2018
Conjecture: Also the number of maximal simple graphs with vertices {1..n} and no weakly nesting edges. Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. For example, the a(1) = 1 through a(5) = 13 edge-sets are:
{} {12} {13} {14} {15}
{12,23} {12,24} {12,25}
{13,24} {13,25}
{13,34} {14,25}
{12,23,34} {14,35}
{14,45}
{12,23,35}
{12,24,35}
{12,24,45}
{13,24,35}
{13,24,45}
{13,34,45}
{12,23,34,45}
Cf. A006125, A054726, A117662, A326244, A326257, A326289, A326293, A326329, A326337, A326338, A326340.
(End)
a(n) is the number of Dyck n-paths in which no nonterminal descent has the same length as the preceding ascent. Example: a(3) = 2 counts UUDUDD and UUUDDD where the latter path qualifies because DDD is the terminal descent. - David Callan, Dec 14 2021
|
|
LINKS
|
A. Blecher, C. Brennan, and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.
Qing Lin Lu, Skew Motzkin paths, Acta Mathematica Sinica, English Series, 33(5) (2017), 657-667.
|
|
FORMULA
|
G.f.: (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) = 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4)).
G.f. A(x) satisfies the equation 0 = 1 - (1 + x^2) * A(x) + x * A(x)^2. - Michael Somos, Jul 22 2003
G.f. A(x) satisfies A(x) = 1 / (1 + x^2 - x * A(x)). - Michael Somos, Mar 28 2011
G.f. A(x) = 1 / (1 + x^2 - x / (1 + x^2 - x / (1 + x^2 - ... ))) continued fraction. - Michael Somos, Jul 01 2011
a(n+1) = a(n) + Sum(a(k)*a(n-k): k=2..n), a(0) = a(1) = 1. - Reinhard Zumkeller, Nov 13 2012
G.f.: 1 + x - x*G(0), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013
D-finite with recurrence: (n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4) = 0. - Robert Israel, May 20 2016
a(n) = Sum_{k=0..n-2} Sum_{j=0..n-k-1} C(n-k-2,j)*C(k,j)*C(k+j+2,j)/(j+1), n>1, a(0)=1, a(1)=1. - Vladimir Kruchinin, Oct 18 2020
a(n) = Sum_{k=0..n-2} HypergeometricPFQ[{-k, 3 +k, k - n + 2}, {1, 2}, 1] for n >= 2. - Peter Luschny, Oct 18 2020
a(n) ~ sqrt(2+r) / (2 * sqrt(Pi) * n^(3/2) * r^n), where r = 0.295597742522084... is the real root of the equation r^3 + r^2 + 3*r - 1 = 0. - Vaclav Kotesovec, Jun 05 2022
G.f.: 1/G(x), with G(x) = 1 - (x-x^2)/(1-x/G(x)) (continued fraction). - Nikolaos Pantelidis, Jan 11 2023
|
|
EXAMPLE
|
1 + x + x^2 + 2*x^3 + 5*x^4 + 13*x^5 + 35*x^6 + 97*x^7 + 275*x^8 + ...
a(3)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - Emeric Deutsch, Jan 27 2003
|
|
MAPLE
|
f:= gfun:-rectoproc({(n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4), a(0) = 1, a(1) = 1, a(2) = 1, a(3) = 2}, a(n), remember):
|
|
MATHEMATICA
|
a[ n_] := SeriesCoefficient[ 2 / (1 + x^2 + Sqrt[1 - 4 x + 2 x^2 + x^4]), {x, 0, n}] (* Michael Somos, Jul 01 2011 *)
a[n_] := Sum[HypergeometricPFQ[{-k, 3 + k, k - n}, {1, 2}, 1], {k, 0, n}];
Join[{1, 1}, Table[a[n], {n, 0, 26}]] (* Peter Luschny, Oct 18 2020 *)
|
|
PROG
|
(PARI) {a(n) = polcoeff( (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4 + x^2 * O(x^n))) / 2, n+1)} /* Michael Somos, Jul 22 2003 */
(PARI) {a(n) = if( n<0, 0, polcoeff( 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4 + x * O(x^n))), n))} /* Michael Somos, Jul 01 2011 */
(PARI) {a(n) = local(A); if( n<0, 0, A = O(x); for( k = 0, n, A = 1 / (1 + x^2 - x * A)); polcoeff( A, n))} /* Michael Somos, Mar 28 2011 */
(Haskell)
a082582 n = a082582_list !! n
a082582_list = 1 : 1 : f [1, 1] where
f xs'@(x:_:xs) = y : f (y : xs') where
y = x + sum (zipWith (*) xs' $ reverse xs)
(Maxima)
a(n):=sum(sum((binomial(n-k-2, j)*binomial(k, j)*binomial(k+j+2, j))/(j+1), j, 0, n-k-1), k, 0, n-2); /* Vladimir Kruchinin, Oct 18 2020 */
|
|
CROSSREFS
|
Apart from initial term, same as A025242.
See A086581 for Dyck paths avoiding DDUU.
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|