|
| |
|
|
A000957
|
|
Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.
(Formerly M1624 N0635)
|
|
77
|
|
|
|
0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 2892818244, 10786724388, 40347919626, 151355847012, 569274150156, 2146336125648, 8110508473252, 30711521221376
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
There are two schools of thought about the best indexing for these numbers. Deutsch and Shapiro have a(4) = 6 whereas here a(5) = 6. The formulas given here use both labelings.
From D. G. Rogers, Oct 18 2005: (Start)
I notice that you have some other zero-one evaluations of binary bracketings (such as A055395). But if you have an operation # with 0#0 = 1#0 = 1, 0#1 = 1#1 = 0, and look at the number of bracketings of a string of n 0's that come out 0, you get another instance of the Fine numbers.
For Z = 1 + x(ZW + WW) = 1 + x CW and W = x(ZZ + ZW) = xZC. Hence Z = 1 + xxCCZ, the functional equational for the g.f. of the Fine numbers. Indeed, C = Z + W = Z + xCZ.
In terms of rooted planar trees with root of even degree, this says that of all rooted planar trees, some have root of even degree (Z) and some have root of odd degree (xCZ). (End)
Hankel transform of a(n+1) = [1,0,1,2,6,18,57,186,...] is A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Starting with offset 3 = iterates of M * [1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,1,...] as the super and subdiagonals. - Gary W. Adamson, Jan 09 2009
Starting with 1 and convolved with A068875 = the Catalan numbers with offset 1. - Gary W. Adamson, May 01 2009
For a relation to non-crossing partitions of the root system A_n, see A100754. - Tom Copeland, Oct 19 2014
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)] = (x-2x^2)/(1-x)^2, and Fin(Cinv(x)) = P(x).
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
a(n+1) is the number of Dyck paths of semilength n avoiding UD at Level 0. For n = 3 the a(4) = 2 such Dyck paths are UUUDDD and UUDUDD. - Ran Pan, Sep 23 2015
For n >= 3, a(n) is the number of permutations pi of [n-2] such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - Colin Defant, Sep 16 2018
Named after the American scientist Terrence Leon Fine (1939-2021). - Amiram Eldar, Jun 08 2021
|
|
|
REFERENCES
|
Emeric Deutsch and Louis W. Shapiro, Seventeen Catalan identities, Bull. Instit. Combin. Applic., Vol. 31 (2001), pp. 31-38.
Ki Hang Kim, Douglas G. Rogers and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013). - N. J. A. Sloane, Jun 05 2012
Louis W. Shapiro and Carol J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb., Vol. 12 (2005), R31.
Peter J. Cameron, Some sequences of integers, Discrete Math., Vol. 75, No. 1-3 (1989), pp. 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., Vol. 43 (1989), pp. 89-102.
Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, On some discrete statistics of parking functions, arXiv:2312.16786 [math.CO], 2023. See p. 13.
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
|
|
|
FORMULA
|
a(n) = (A064306(n-1) + (-1)^(n-1))/2^n, n >= 1.
a(n) ~ 4^n/(9*n*sqrt(n*Pi)). (Corrected by Peter Luschny, Oct 26 2015.)
a(n) = (2/(n-1))*Sum_{j=0..n-3}(-2)^j*(j+1)*binomial(2n-1, n-3-j), n>=2. - Emeric Deutsch, Dec 26 2003
a(n) = 3*Sum_{j=0..floor((n-1)/2)} binomial(2n-2j-2, n-1) - binomial(2n, n) for n>0. - Emeric Deutsch, Jan 28 2004
Reversion of g.f. (x-2x^2)/(1-x)^2. - Ralf Stephan, Mar 22 2004
a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, C(1/2, k)8^k})+0^n; a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, (-1)^(k-1)*2^k*(2k)!/((k!)^2*(2k-1))})+0^n. - Paul Barry, Jun 10 2005
Hankel determinant transform is 1-n. - Michael Somos, Sep 17 2006
a(n+1) has g.f. 1/(1-0*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(..... (continued fraction). - Paul Barry, Dec 02 2008
G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;
a(n+1) = Sum_{k=0..n} (-1)^k*C(2n-k,n-k)*(k+1)/(n+1). (End)
a(n) = 3*(-1/2)^(n+1) + Gamma(n+1/2)*4^n*hypergeom([1, n+1/2],[n+2],-8) /(sqrt(Pi)*(n+1)!) (for n>0). - Mark van Hoeij, Nov 11 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n>=1, a(n+1) = (-1)^n*charpoly(A,1). - Milan Janjic, Jul 08 2010
a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
0, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar, Nov 15 2011
a(n) = sum(sum(2^(s-2n-2k)*(n/n+2k)binomial(n+2k, k)*binomial(s-n-1, s-2n-2k), (k=0, ..., floor((s-2n)/2)), (n=1, ..., s) with s>=2. - José Luis Ramírez Ramírez, Mar 22 2012
0 = a(n)*(16*a(n+1) + 22*a(n+2) - 20*a(n+3)) + a(n+1)*(34*a(n+1) + 53*a(n+2) - 38*a(n+3)) + a(n+2)*(10*a(n+2) + 4*a(n+3)) for all n in Z if we extend by a(0)=-1, a(-n) = -3/4 * (-2)^n if n>0. - Michael Somos, Jan 31 2014 [Corrected by Pontus von Brömssen, Aug 04 2022]
G.f. A(x) satisfies x*A'(x)/A(x) = x + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for A072547. - Peter Bala, Oct 01 2015
a(n) = 2^n*(n-2)*(2*n-1)!!*(3*(n-1)*hypergeom([1,3-n], [3+n], 2)-n-2)/(n+2)! + 0^n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = binomial(2*n,n)*(hypergeom([1,(1-n)/2,1-n/2],[1-n,3/2-n],1)*3/(4-2/n)-1) for n>=2. - Peter Luschny, Oct 26 2015
O.g.f. A(x) satisfies 1 + A(x) = (1 + 3*Sum_{n >= 1} Catalan(n)*x^n)/(1 + 2*Sum_{n >= 1} Catalan(n)*x^n) = (1 + 2*Sum_{n >= 1} binomial(2*n,n)*x^n )/(1 + 3/2*Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016
|
|
|
EXAMPLE
|
G.f. = x + x^3 + 2*x^4 + 6*x^5 + 18*x^6 + 57*x^7 + 186*x^8 + 622*x^9 + 2120*x^10 + ...
|
|
|
MAPLE
|
t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1, x, 90); A000957 := n- coeff(t2, x, n);
A000957 := proc(n): if n = 0 then 0 else add((-1)^(n+k-1)*binomial(n+k-1, n-1)*(n-k)/n, k=0..n-1) fi: end: seq(A000957(n), n=0..28); # Johannes W. Meijer, Jul 22 2013
# third Maple program:
a:= proc(n) option remember; `if`(n<3, n*(2-n),
((7*n-12)*a(n-1)+(4*n-6)*a(n-2))/(2*n))
end:
|
|
|
MATHEMATICA
|
Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} ], {n, 0, 36} ] (* Wouter Meeussen *)
a[0] = 0; a[n_] := (1/2)*(-3*(-1/2)^n + 2^(n+1)*(2n-1)!!* Hypergeometric2F1Regularized[2, 2n+1, n+2, -1]); (* Jean-François Alcover, Feb 22 2012 *)
Table[2^n (n-2) (2n-1)!! (3 (n-1) Hypergeometric2F1[1, 3-n, 3+n, 2] - n - 2)/(n+2)! + KroneckerDelta[n], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<1, 0, polcoeff( 1 / (1 + 2 / (1 - sqrt(1 - 4*x + x*O(x^n)))), n))}; /* Michael Somos, Sep 17 2006 */
(PARI) {a(n) = if( n<1, 0, polcoeff( 1 / (1 + 1 / serreverse(x - x^2 + x*O(x^n))), n))}; /* Michael Somos, Sep 30 2006 */
(Haskell)
a000957 n = a000957_list !! n
a000957_list = 0 : 1 :
(map (`div` 2) $ tail $ zipWith (-) a000108_list a000957_list)
(Magma) [0, 1] cat [n le 1 select n-1 else (Catalan(n)-Self(n-1))/2: n in [1..30]]; // Vincenzo Librandi, Nov 17 2016
(Sage)
def Fine():
f, c, n = 1, 1, 1
yield 0
while True:
yield f
n += 1
c = c * (4*n - 6) // n
f = (c - f) // 2
a = Fine()
(Maxima)
C(n):=binomial(2*n, n)/(n+1);
a(n):=if n<=0 then 0 else if n=1 then 1 else sum(C(n-i-1)*(a(i)+a(i-1)), i, 2, n-1);
(Python)
from itertools import count, islice
def A000957_gen(): # generator of terms
yield from (0, 1, 0)
a, c = 0, 1
for n in count(1):
yield (a:=(c:=c*((n<<2)+2)//(n+2))-a>>1)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
