OFFSET
0,3
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.
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)
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Emanuele Munarini, Apr 02 2003
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
STATUS
approved