%I #114 Nov 05 2025 15:22:02

%S 1,1,3,9,29,97,333,1165,4135,14845,53791,196417,721887,2667941,

%T 9907851,36950465,138320021,519515209,1957091277,7392602917,

%U 27992976565,106236268337,404005515873,1539293204549,5875059106769,22459721336977

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

%C 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

%C Hankel transform is 2^n. - _Paul Barry_, Nov 22 2007

%C Equals left border of triangle A152229. - _Gary W. Adamson_, Nov 29 2008

%C Equals INVERTi transform of A000984: (1, 2, 6, 20, 70, 252, ...). - _Gary W. Adamson_, May 15 2009

%C (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

%C 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

%C 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

%H Vincenzo Librandi, <a href="/A081696/b081696.txt">Table of n, a(n) for n = 0..100</a>

%H Ron M. Adin, Arkady Berenstein, Jacob Greenstein, Jian-Rong Li, Avichai Marmor, and Yuval Roichman, <a href="https://arxiv.org/abs/2309.11203">Transitive and Gallai colorings</a>, arXiv:2309.11203 [math.CO], 2023. See p. 25.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.11845">Chebyshev moments and Riordan involutions</a>, arXiv:1912.11845 [math.CO], 2019.

%H Paul Barry and Arnauld Mesinga Mwafise, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barry/barry362.html">Classical and Semi-Classical Orthogonal Polynomials Defined by Riordan Arrays, and Their Moment Sequences</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.5.

%H Edward A. Bender, Gregory F. Lawler, Robin Pemantle and Herbert S. Wilf, <a href="https://arxiv.org/abs/math/0404253">Irreducible compositions and the first return to the origin of a random walk</a>, arXiv:math/0404253 [math.CO], 2004.

%H Edward A. Bender, Gregory F. Lawler, Robin Pemantle and Herbert S. Wilf, <a href="http://www.math.ucsd.edu/~ebender/reprints/110.pdf">Irreducible compositions and the first return to the origin of a random walk</a>, Sem. Lothar. 50 (2004) B50h.

%H David Callan, <a href="https://arxiv.org/abs/1206.3174">An identity for the central binomial coefficient</a>, arXiv preprint arXiv:1206.3174 [math.CO], 2012. - From _N. J. A. Sloane_, Nov 25 2012

%H G. Chatel and V. Pilaud, <a href="https://arxiv.org/abs/1411.3704">Cambrian Hopf Algebras</a>, arXiv:1411.3704 [math.CO], 2014-2015.

%H Ivan Dimitrov, Cole Gigliotti, Etan Ossip, Charles Paquette, and David Wehlau, <a href="https://doi.org/10.48550/arXiv.2310.16767">Inversion Sets and Quotient Root Systems</a>, arXiv:2310.16767 [math.CO], 2023.

%H A. Umar, <a href="http://www.mathnet.ru/adm33">Some combinatorial problems in the theory of symmetric ...</a>, Algebra Disc. Math. 9 (2010) 115-126.

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

%F 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.

%F a(n) = Sum_{k=0..n} binomial(2n-k,n+k)*(3k+1)/(n+k+1). - _Emanuele Munarini_, Apr 02 2011

%F From _Paul Barry_, Dec 18 2004: (Start)

%F 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)).

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

%F From _Bill Gosper_, May 14 2011: (Start)

%F 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.

%F 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)

%F 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

%F From _Gary W. Adamson_, Jul 11 2011: (Start)

%F 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:

%F 1, 1, 0, 0, 0, 0, ...

%F 2, 1, 1, 0, 0, 0, ...

%F 2, 1, 1, 1, 0, 0, ...

%F 2, 1, 1, 1, 1, 0, ...

%F 2, 1, 1, 1, 1, 1, ...

%F ... (End)

%t 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 *)

%t CoefficientList[Series[1/(x+Sqrt[1-4x] ),{x,0,30}],x] (* _Harvey P. Dale_, May 05 2021 *)

%o (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 */

%o (PARI) x='x+O('x^66); Vec(1/(x+sqrt(1-4*x))) \\ _Joerg Arndt_, Jul 06 2013

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

%Y Cf. A068875.

%K nonn,easy

%O 0,3

%A _Emanuele Munarini_, Apr 02 2003

%E More terms from _Paul Barry_, Dec 18 2004

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