|
|
A007595
|
|
a(n) = C_n / 2 if n is even or ( C_n + C_((n-1)/2) ) / 2 if n is odd, where C = Catalan numbers (A000108).
(Formerly M2681)
|
|
16
|
|
|
1, 1, 3, 7, 22, 66, 217, 715, 2438, 8398, 29414, 104006, 371516, 1337220, 4847637, 17678835, 64823110, 238819350, 883634026, 3282060210, 12233141908, 45741281820, 171529836218, 644952073662, 2430973304732, 9183676536076, 34766775829452, 131873975875180
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Number of necklaces of 2 colors with 2n beads and n-1 black ones. - Wouter Meeussen, Aug 03 2002
Number of rooted planar binary trees up to reflection (trees with n internal nodes, or a total of 2n+1 nodes). - Antti Karttunen, Aug 19 2002
Number of even permutations avoiding 132.
Number of Dyck paths of length 2n having an even number of peaks at even height. Example: a(3)=3 because we have UDUDUD, U(UD)(UD)D and UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even height are shown between parentheses. - Emeric Deutsch, Nov 13 2004
Number of planar trees (A002995) on n edges with one distinguished edge. - David Callan, Oct 08 2005
Assuming offset 0 this is an analog of A275165: pairs of two Catalan nestings with index sum n. - R. J. Mathar, Jul 19 2016
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (2-2*x-sqrt(1-4*x)-sqrt(1-4*x^2))/x/4. - Vladeta Jovovic, Sep 26 2003
D-finite with recurrence: n*(n+1)*a(n) -6*n*(n-1)*a(n-1) +4*(2*n^2-10*n+9)*a(n-2) +8*(n^2+n-9)*a(n-3) -48*(n-3)*(n-4)*a(n-4) +32*(2*n-9)*(n-5)*a(n-5)=0. - R. J. Mathar, Jun 03 2014, adapted to offset Feb 20 2020
|
|
MAPLE
|
A007595 := n -> (1/2)*(Cat(n) + (`mod`(n, 2)*Cat((n-1)/2))); Cat := n -> binomial(2*n, n)/(n+1);
|
|
MATHEMATICA
|
Table[(Plus@@(EulerPhi[ # ]Binomial[2n/#, (n-1)/# ] &)/@Intersection[Divisors[2n], Divisors[n-1]])/(2n), {n, 2, 32}] (* or *) Table[If[EvenQ[n], CatalanNumber[n]/2, (CatalanNumber[n] + CatalanNumber[(n-1)/2])/2], {n, 24}]
Table[(CatalanNumber[n] + 2^n Binomial[1/2, (n + 1)/2] Sin[Pi n/2])/2, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)
Table[If[EvenQ[n], CatalanNumber[n]/2, (CatalanNumber[n]+CatalanNumber[(n-1)/2])/2], {n, 30}] (* Harvey P. Dale, Sep 06 2021 *)
|
|
PROG
|
(PARI) catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n % 2, (catalan(n) + catalan((n-1)/2))/2, catalan(n)/2); \\ Michel Marcus, Jan 23 2016
|
|
CROSSREFS
|
a(n) = A047996(2*n, n-1) for n >= 1 and a(n) = A072506(n, n-1) for n >= 2.
Occurs in A073201 as rows 0, 2, 4, etc. (with a(0)=1 included).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|