|
| |
|
|
A202038
|
|
Hafnian of a +/-1 array.
|
|
14
|
|
|
|
1, -1, -1, 5, 17, -121, -721, 6845, 58337, -698161, -7734241, 111973685, 1526099057, -25947503401, -419784870961, 8200346492525, 153563504618177, -3389281372287841, -72104198836466881, 1774459993676715365, 42270463533824671697
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
a(n) is the Hafnian of the triangular array (a(i,j))_{1<=i<j<=2n} defined by a(i,j) = (-1)^i. The Hafnian is the same as the Pfaffian except without the alternating signs, that is, the Hafnian of the upper triangular array (a(i,j))_{1<=i<j<=2n} is the sum of the products a(i1,j1)*a(i2,j2)*...*a(in,jn) taken over all perfect matchings of [2n] written so that i1<j1, i2<j2, ..., in<jn and i1<i2<...<in.
a(n) is also the total weight of Dyck n-paths with the weight of a Dyck path defined as (-1)^(sum of the upstep heights) times the product of the upstep heights. For example, the Dyck 4-path P = UUDUUDDD has upsteps ending at heights 1,2,2,3 respectively and so weight(P) = (-1)^8 times (1*2*2*3) = +12.
|
|
|
LINKS
|
|
|
|
FORMULA
|
E.g.f.: sqrt(2/(1 + exp(4*x))).
G.f.: 1/(1 + x/(1 - 2 x/(1 + 3 x /(1 - 4 x/(1 + 5 x /(1 - 6 x/ (1 + ...))))))) (continued fraction).
G.f. 1/G(0) where G(k) = 1 + x*(2*k+1)/(1 - (2*k+2)*x/G(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Aug 11 2012
G.f.: 1/(U(0) + x) where U(k)= 1 + x*(2*k+1)*(2*k+2) - x*(2*k+1)*(2*k+2)/(1 + x/U(k+1)) ; (continued fraction, 2-step). - Sergei N. Gladkovskii, Oct 13 2012
G.f.: 1/U(0) where U(k)= 1 + x + x^2*(2*k+1)*(2*k+2)/U(k+1) ; (continued fraction, 1-step). - Sergei N. Gladkovskii, Oct 13 2012
a(n) ~ (cos(n*Pi/2)-sin(n*Pi/2)) * 2^(2*n+3/2) *n^n / (Pi^(n+1/2) * exp(n)). - Vaclav Kotesovec, Oct 08 2013
G.f.: T(0)/(1+x) , where T(k) = 1 - x^2*(2*k+1)*(2*k+2)/( x^2*(2*k+1)*(2*k+2) + (1+x)^2/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 22 2013
a(n) = 4^(n-1)*Sum_{k=0..n-1} (((-1)^(k+1) * (k+1)! * binomial(2*k+2, k+1) * stirling2(n, k+1)) / 2^(3*k+1)), n>0, a(0)=1. - Vladimir Kruchinin, Mar 09 2016
|
|
|
MATHEMATICA
|
u[n_, 0] := If[n==0, 1, 0]; u[n_, m_] /; m==1 := 2^(n - 1); u[n_, m_] /; m==n>=1 := 1; u[n_, m_] /; 1<m<n := u[n, m] = (2m)*u[n - 1, m] + (2n - 2m + 1)*u[n - 1, m - 1]; v[n_] := Sum[(-1)^m u[n, m], {m, 0, n}]; Table[v[n], {n, 0, 20}]
Flatten[{1, Table[4^(n-1) * Sum[(-1)^(k+1) * (k+1)! * Binomial[2*k + 2, k + 1] * StirlingS2[n, k + 1]/2^(3*k + 1), {k, 0, n-1}], {n, 1, 20}]}] (* Vaclav Kotesovec, Mar 09 2016, after Vladimir Kruchinin *)
|
|
|
PROG
|
(Maxima)
a(n):=if n=0 then 1 else 4^(n-1)*sum(((-1)^(k+1)*(k+1)!*binomial(2*k+2, k+1)*stirling2(n, k+1))/2^(3*k+1), k, 0, n-1). /* Vladimir Kruchinin, Mar 09 2016 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
sign
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
