|
|
A081696
|
|
Expansion of 1/(x + sqrt(1-4x)).
|
|
18
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
(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
|
|
LINKS
|
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.
|
|
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
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)
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
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
|
|
|
EXTENSIONS
|
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
|
|
|
|