A081696 Expansion of 1/(x + sqrt(1-4x)).

1, 1, 3, 9, 29, 97, 333, 1165, 4135, 14845, 53791, 196417, 721887, 2667941, 9907851, 36950465, 138320021, 519515209, 1957091277, 7392602917, 27992976565, 106236268337, 404005515873, 1539293204549, 5875059106769, 22459721336977

Offset: 0

Author

Emanuele Munarini, Apr 02 2003

Keywords

• nonn
• easy

Comments

Number of irreducible ordered pairs of compositions of n. A pair of compositions of n into the same number of (positive) parts, say n = a1 + ... + ak and n = b1 + ... + bk, is irreducible if for all j < k, a1 + ... + aj is not equal to b1 + ... + bj. E.g., a(3)=3 because the irreducible pairs are (1+2,2+1), (2+1,1+2), (3,3). - Herbert S. Wilf, May 22 2004

Hankel transform is 2^n. - Paul Barry, Nov 22 2007

Equals left border of triangle A152229. - Gary W. Adamson, Nov 29 2008

Equals INVERTi transform of A000984: (1, 2, 6, 20, 70, 252, ...). - Gary W. Adamson, May 15 2009

(1 + 3x + 9x^2 + 29x^3 + ...) * 1/(1 + x + 3x^2 + 9x^3 + 29x^4 + ...) = (1 + 2x + 4x^2 + 10x^3 + 28x^4 + ...); where A068875 = (1, 2, 4, 10, 28, ...). - Gary W. Adamson, Nov 21 2011

Apparently the number of grand Motzkin paths of length n with two types of flat step (F,f) and avoiding F at level 0. - David Scambler, Jul 04 2013

Starting at n=1 p-INVERT of Catalan numbers (A000108, starting at n=0), where p(S) = 1 - S - S^2; see A289780. - Clark Kimberling, Aug 12 2017

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..100
• Ron M. Adin, Arkady Berenstein, Jacob Greenstein, Jian-Rong Li, Avichai Marmor, and Yuval Roichman, Transitive and Gallai colorings, arXiv:2309.11203 [math.CO], 2023. See p. 25.
• Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
• Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
• Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
• Paul Barry and Arnauld Mesinga Mwafise, Classical and Semi-Classical Orthogonal Polynomials Defined by Riordan Arrays, and Their Moment Sequences, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.5.
• Edward A. Bender, Gregory F. Lawler, Robin Pemantle and Herbert S. Wilf, Irreducible compositions and the first return to the origin of a random walk, arXiv:math/0404253 [math.CO], 2004.
• Edward A. Bender, Gregory F. Lawler, Robin Pemantle and Herbert S. Wilf, Irreducible compositions and the first return to the origin of a random walk, Sem. Lothar. 50 (2004) B50h.
• David Callan, An identity for the central binomial coefficient, arXiv preprint arXiv:1206.3174 [math.CO], 2012. - From _N. J. A. Sloane_, Nov 25 2012
• G. Chatel and V. Pilaud, Cambrian Hopf Algebras, arXiv:1411.3704 [math.CO], 2014-2015.
• Ivan Dimitrov, Cole Gigliotti, Etan Ossip, Charles Paquette, and David Wehlau, Inversion Sets and Quotient Root Systems, arXiv:2310.16767 [math.CO], 2023.
• A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.

Crossrefs

Cf. A000045, A000984, A081698, A152229, A189675.

Cf. A068875.

Programs

Mathematica

y[n_] := y[n] = (2*(4*n - 3)*y[n - 1] - (15*n - 24)*y[n - 2] - (4*n - 6)*y[n - 3])/n; y[0] = 1; y[1] = 1; y[2] = 3; (* corrected by Wouter Meeussen, Apr 30 2011 *)
CoefficientList[Series[1/(x+Sqrt[1-4x] ),{x,0,30}],x] (* Harvey P. Dale, May 05 2021 *)

Maxima

makelist(sum(binomial(2*n-k,n+k)*(3*k+1)/(n+k+1),k,0,n),n,0,12); /* Emanuele Munarini, Apr 02 2011 */

PARI

x='x+O('x^66); Vec(1/(x+sqrt(1-4*x))) \\ Joerg Arndt, Jul 06 2013

Formula

G.f.: 1/(x + sqrt(1-4*x)).

D-finite with recurrence: n*a(n) + 2*(-4*n+3)*a(n-1) + 3*(5*n-8)*a(n-2) + 2*(2*n-3)*a(n-3) = 0.

a(n) = Sum_{k=0..n} binomial(2n-k,n+k)*(3k+1)/(n+k+1). - Emanuele Munarini, Apr 02 2011

From Paul Barry, Dec 18 2004: (Start)

A Catalan transform of the Fibonacci numbers F(n+1) under the mapping G(x) -> G(xc(x)), c(x) the g.f. of A000108. The inverse mapping is H(x) -> H(x(1-x)).

a(n) = Sum{k=0..n} (k/(2n-k))binomial(2n-k, n-k)F(k+1). (End)

From Bill Gosper, May 14 2011: (Start)

We have (per Wouter Meeussen): a(n) = (Sum_{k=1..n} k*Fibonacci(k+1)*(-1)^(n+k)*binomial(-n,n-k))/n = (Sum_{k=1..n} k*Fibonacci(k+1)*binomial(2*n-k-1,n-1))/n.

If we introduce an alternating sign, defining b(n) = (Sum_{k=1..n} k*Fibonacci(k+1)*binomial(-n,n-k))/n = (Sum_{k=1..n} k*Fibonacci(k+1)*(-1)^(n+k)*binomial(2*n-k-1,n-1))/n, then b(n) = 1 for all n. (Not obvious--I proved it satisfies b(n+2) = ((17*n^2 + 37*n + 18)*b(n+1) - 4*(2*n+1)*(2*n+3)*b(n))/((n+2)*(n+3)).) (End)

G.f.: 1/(1-x-2x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009

From Gary W. Adamson, Jul 11 2011: (Start)

a(n) = the upper left term in M^n, M = an infinite square production matrix in which a column of (1,2,2,2,...) is prepended to an infinite lower triangular matrix of all 1's and the rest zeros:

1, 1, 0, 0, 0, 0, ...

2, 1, 1, 0, 0, 0, ...

2, 1, 1, 1, 0, 0, ...

2, 1, 1, 1, 1, 0, ...

2, 1, 1, 1, 1, 1, ...

... (End)

Extensions

More terms from Paul Barry, Dec 18 2004

Wouter credited with first sums in Gosper's FORMULA Comment, which were mistyped by NJAS (caught by Julian Ziegler Hunts), May 14 2011