A007595 -id:A007595 - cp's OEIS frontend

A071684 Number of plane trees with n edges and having an odd number of leaves.

1, 1, 2, 7, 22, 66, 212, 715, 2438, 8398, 29372, 104006, 371516, 1337220, 4847208, 17678835, 64823110, 238819350, 883629164, 3282060210, 12233141908, 45741281820, 171529777432, 644952073662, 2430973304732, 9183676536076

Offset: 1

Sen-peng Eu, Jun 23 2002

Narayana transform (A001263) of [1, 0, 1, 0, 1, 0, 1, ...]. Example: a(4) = 7 = (1, 6, 6, 1) dot (1, 0, 1, 0) = (1 + 0 + 6 + 0). - Gary W. Adamson, Jan 04 2008

			a(3)=2 because among the 5 plane 3-trees there are 2 trees with odd number of leaves; a(4)=7 because among the 14 plane 4-trees there are 7 trees with odd number of leaves.

Robert Israel, Table of n, a(n) for n = 1..1668
Yu Hin Au, Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers, arXiv:1912.00555 [math.CO], 2019.
S. P. Eu, S. C. Liu and Y. N. Yeh, Odd or Even on Plane Trees, Discrete Math. 281 (2004), 189-196.

a(n) + A071688 = A000108: Catalan numbers.

Cf. A001263, A007595.

G:=((1+4*x^2)^(1/2)-(1-4*x)^(1/2)-2*x)/4/x: Gser:=series(G,x=0,30): seq(coeff(Gser,x,n),n=1..26); # Emeric Deutsch, Feb 17 2007

a[n_] := If[EvenQ[n], Binomial[2n, n]/(2n + 2), Binomial[2n, n]/(2n + 2) - (-1)^((n + 1)/2)Binomial[n - 1, (n - 1)/2]/(n + 1)]
Table[(CatalanNumber[n] + 2^n Binomial[1/2, (n + 1)/2])/2, {n, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)

a(2*n) = (1/(4*n + 2))*binomial(4*n, 2*n);
a(2*n-1) = (1/(4*n))*binomial(4*n-2, 2*n-1) - (-1)^n*(1/(2*n))*binomial(2*n-2, n-1), with n>0.
G.f.: (1/4)*((1+4*x^2)^(1/2) - (1-4*x)^(1/2)-2*x)/x. - Vladeta Jovovic, Apr 19 2003
a(0)=0; a(n) = Sum_{k = 0..floor(n/2)} (1/n)*C(n,2*k+1)*C(n,2*k) for n>0. - Paul Barry, Jan 25 2007
a(n) = Sum_{k=1..n} (1/n)*C(n,k)*C(n,k-1)*(1-(-1)^k)/2. - Paul Barry, Dec 16 2008
Conjecture: n*(n+1)*(10*n-37)*a(n) + 2*n*(5*n^2-42*n+91)*a(n-1) + 4*(-40*n^3+270*n^2-560*n+357)*a(n-2) + 8*(n-3)*(5*n^2-42*n+91)*a(n-3) - 16*(n-4)*(25*n-51)*(2*n-7)*a(n-4) = 0. - R. J. Mathar, Jul 05 2018
a(n) = (A000108(n) + 2^n * binomial(1/2, (n+1)/2))/2. - Vladimir Reshetnikov, Oct 03 2016
32*n*(2*n+1)*a(n) - 48*(n+2)*(n+1)*a(n+1) + 8*(n^2-n-9)*a(n+2) - 4*(2*n^2+10*n+9)*a(n+3) - 2*(n+5)*(n+6)*a(n+4) + (n+5)*(n+6)*a(n+5) = 0. - Robert Israel, Jul 05 2018

Edited by Robert G. Wilson v, Jun 25 2002

A072506 Triangle giving T(n,m) = number of necklaces of two colors with 2n beads of which m=1..n are black.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 4, 7, 10, 1, 5, 12, 22, 26, 1, 6, 19, 43, 66, 80, 1, 7, 26, 73, 143, 217, 246, 1, 8, 35, 116, 273, 504, 715, 810, 1, 9, 46, 172, 476, 1038, 1768, 2438, 2704, 1, 10, 57, 245, 776, 1944, 3876, 6310, 8398, 9252, 1, 11, 70, 335, 1197, 3399, 7752

Offset: 1

Wouter Meeussen, Aug 03 2002

Left half of even rows of triangle A047996 (with the leftmost edge discarded).

Penultimate entries give binary necklaces of n-1 black beads and n+1 white beads, presumably A007595, antepenultimate entries give binary necklaces of n-2 black beads and n+2 white beads, presumably A003444.

Cf. A047996, A003444.

Table[(Plus@@(EulerPhi[ # ]Binomial[2n/#, m/# ] &)/@Intersection[Divisors[2n], Divisors[m]])/(2n), {n, 13}, {m, n}]

(1/(2n)) Sum_{d |(2n, m)} phi(d)*binomial(2n/d, m/d)

A073281 Self-inverse permutation of natural numbers induced by the composition of the Catalan bijections A072796 and A073269.

Original entry on oeis.org

0, 1, 3, 2, 7, 5, 8, 4, 6, 17, 18, 12, 11, 15, 20, 13, 21, 9, 10, 22, 14, 16, 19, 45, 46, 48, 49, 50, 31, 32, 30, 28, 29, 40, 39, 43, 52, 54, 55, 34, 33, 41, 57, 35, 58, 23, 24, 59, 25, 26, 27, 61, 36, 62, 37, 38, 63, 42, 44, 47, 64, 51, 53, 56, 60, 129, 130, 132, 133, 134

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences that are permutations of the natural numbers

Occurs for first time in A073200 as row 15. This is a conjugate of A069770, so the fixed element and the cycle counts are same as for A069770: "Aerated Catalan numbers" and A007595.

a(n) = A072796(A073269(n)) = A072796(A069770(A072796(n))).

A132892 Square array T(m,n) read by antidiagonals; T(m,n) is the number of equivalence classes in the set of sequences of n nonnegative integers that sum to m, generated by the equivalence relation defined in the following manner: we write a sequence in the form a[1]0a[2]0...0a[p], where each a[i] is a (possibly empty) sequence of positive integers; two sequences in this form, a[1]0a[2]0...0a[p] and b[1]0b[2]0...0b[q] are said to be equivalent if p=q and b[1],b[2],...,b[q] is a cyclic permutation of a[1],a[2],...a[p].

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 3, 1, 1, 5, 9, 7, 4, 1, 1, 6, 13, 14, 10, 4, 1, 1, 7, 19, 25, 22, 12, 5, 1, 1, 8, 25, 41, 42, 30, 15, 5, 1, 1, 9, 33, 63, 79, 66, 43, 19, 6, 1, 1, 10, 41, 92, 131, 132, 99, 55, 22, 6, 1, 1, 11, 51, 129, 213, 245, 217, 143, 73, 26, 7, 1, 1, 12, 61, 175, 325, 428, 429, 335, 201, 91, 31, 7, 1

Offset: 1

Emeric Deutsch and Ira M. Gessel, Oct 02 2007

T(n,n) = A000108(n) (the Catalan numbers; see R. P. Stanley, Catalan addendum, problem starting "Equivalence classes of the equivalence relation ..."). T(m,m+1) = A007595(m+1); T(m,m+2) = A003441(m+1); T(m,m+3) = A003444(m+3); T(n+2,n) = A001453(n+1) (Catalan numbers - 1); T(m,1)=1; T(m,2)=m; T(m,3) = A080827(m) = A099392(m+1); T(m,4) = A004006(m).

			T(2,4) = 3 because we have {2000, 0200, 0020, 0002}, {1100, 0110, 0011} and {1010, 0101, 1001}.
T(4,2) = 4 because we have {40, 04}, {31}, {13} and {22}.
The square array starts:
  1....1.....1.....1......1.....1.....1...
  1....2.....3.....3......4.....4.....5...
  1....3.....5.....7.....10....12....15...
  1....4.....9....14.....22....30....43...
  1....5....13....25.....42....66....99...

Alois P. Heinz, antidiagonals n = 1..200, flattened
Emeric Deutsch and Ira Gessel, Equivalence Classes and Cyclic Arrangements:Problem 10525, Amer. Math. Monthly, 105, No. 8, 1998, 774-775 (published solution by D. Beckwith).
R. P. Stanley, Catalan addendum. See the interpretation (www, "Vertices of height n-1 of the tree T ...").

Cf. A000108, A007595, A003441, A003444, A001453, A080827, A099392, A004006.

with(numtheory): T:=proc(m,n) local r, div, N: r:=igcd(m,n+1): div:=divisors(r): N:=nops(div): (sum(phi(div[j])*(binomial((m+n+1)/div[j]-1,(n+1)/div[j]-1) -binomial(m/div[j]-1,(n+1)/div[j]-1)),j=1..N))/(n+1) end proc: for m to 12 do seq(T(m, n),n=1..12) end do; # yields the upper left 12 by 12 block of the infinite matrix T(m,n)
# second Maple program:
T:= proc(m, n) uses numtheory; (C-> add(phi(d)*(C((m+n+1)/d-1, (n+1)/d-1)
      -C(m/d-1, (n+1)/d-1))/(n+1), d=divisors(igcd(m, n+1))))(binomial)
    end:
seq(seq(T(1+d-n, n), n=1..d), d=1..14);  # Alois P. Heinz, Jan 28 2025

T[m_, n_] := Module[{r, div, N}, r = GCD[m, n + 1]; div = Divisors[r]; N = Length[div]; (Sum[EulerPhi[div[[j]]]*(Binomial[(m + n + 1)/div[[j]] - 1, (n + 1)/div[[j]] - 1] - Binomial[m/div[[j]] - 1, (n + 1)/div[[j]] - 1]), {j, 1, N}])/(n + 1)];
Table[T[m - n + 1, n], {m, 1, 13}, {n, 1, m}] // Flatten (* Jean-François Alcover, Sep 01 2024, after Maple program *)

T(m,n) = Sum_{d | gcd(m,n+1)} phi(d)*(C((m+n+1)/d-1, (n+1)/d-1) - C(m/d-1, (n+1)/d-1))/(n+1). [corrected by Jason Yuen, Jan 28 2025]

A183759 Unlabeled super-Catalan numbers: patterns of nonintersecting chords joining unlabeled points on a circle, triangle decomposed by number of chords.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 2, 7, 7, 1, 3, 15, 33, 22, 1, 3, 24, 94, 136, 66, 1, 4, 41, 218, 525, 552, 217, 1, 4, 57, 440, 1517, 2673, 2233, 715, 1, 5, 86, 804, 3748, 9439, 12917, 8807, 2438

Offset: 1

David Scambler, Jan 06 2011

Decomposition of A183757 by number of chords (pairs of parentheses). Row sums are A183757. See A183757 for description.
Triangle is
1
1 1
1 2  3
1 2  7  7
1 3 15 33  22
1 3 24 94 136 66
...
Right diagonal is apparently A007595.

Decomposition of A183757.

Cf. analogous decomposition of super-Catalan numbers in triangle A033282.

A342770 T(n,k) is the number of rooted plane binary forests with n nodes and k trees: triangle read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 0, 3, 0, 1, 0, 1, 0, 5, 0, 3, 0, 1, 0, 1, 0, 0, 7, 0, 3, 0, 1, 0, 1, 0, 14, 0, 8, 0, 3, 0, 1, 0, 1, 0, 0, 22, 0, 8, 0, 3, 0, 1, 0, 1, 0, 42, 0, 24, 0, 8, 0, 3, 0, 1, 0, 1, 0, 0, 66, 0, 25, 0, 8, 0

Offset: 0

R. J. Mathar, Mar 21 2021

Multiset transform of A126120.

			See A222006 showing T(6,k).
The triangle starts (n>=0, 0<=k<=n):
  1
  0   1
  0   0   1
  0   1   0   1
  0   0   1   0   1
  0   2   0   1   0   1
  0   0   3   0   1   0   1
  0   5   0   3   0   1   0   1
  0   0   7   0   3   0   1   0   1
  0  14   0   8   0   3   0   1   0   1
  0   0  22   0   8   0   3   0   1   0   1
  0  42   0  24   0   8   0   3   0   1   0   1
  0   0  66   0  25   0   8   0   3   0   1   0   1
  0 132   0  74   0  25   0   8   0   3   0   1   0   1
  0   0 217   0  76   0  25   0   8   0   3   0   1   0   1

Cf. A222006 (row sums), A126120 (column k=1), A007595 (k=2), A046342 (k=3), A088327 (limit n->oo, row reverse).

cp's OEIS Frontend

A071684 Number of plane trees with n edges and having an odd number of leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A072506 Triangle giving T(n,m) = number of necklaces of two colors with 2n beads of which m=1..n are black.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A073281 Self-inverse permutation of natural numbers induced by the composition of the Catalan bijections A072796 and A073269.

Views

Author

Keywords

Links

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A183759 Unlabeled super-Catalan numbers: patterns of nonintersecting chords joining unlabeled points on a circle, triangle decomposed by number of chords.

Views

Author

Keywords

Comments

Crossrefs

A342770 T(n,k) is the number of rooted plane binary forests with n nodes and k trees: triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs