%I #113 Oct 26 2023 15:13:19
%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="http://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="http://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="http://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