OFFSET
1,3
COMMENTS
The formula is derived by an application of the principle of inclusion and exclusion.
In reference to A053871, it is observed that the set of pairings disjoint to a given pairing can be partitioned into 2n-2 equivalent sets according to the 2n-2 pairs containing a given item. So it is seen that each term of that sequence must be divisible by 2n-2, giving the corresponding term of this sequence. However, the formula given here is derived independently.
Hankel transform of a(n+1) is A168467. Binomial transform of a(n+1) is A001147(n+1). - Paul Barry, Jan 26 2011
a(n) is a subset of the set of pairings of the first 2n integers (A001147) in another way: forbidding pairs of the form (2k,2k+1) for all k. - Olivier Gérard, Feb 08 2011
REFERENCES
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, Chapter 3
LINKS
Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).
Célia Biane, Greg Hampikian, Sergey Kirgizov, and Khaydar Nurligareev, Endhered patterns in matchings and RNA, arXiv:2404.18802 [math.CO], 2024. See pp. 8-9.
FORMULA
a(n) = (2n-3)!! - C(n-2,1) * (2n-5)!! + ... +/- C(n-2,n-1)*3!! -/+ 1.
a(n) = (2*n-4)*a(n-1) +(2*n-6)*a(n-2) for n>2. - Gary Detlefs, Jul 11 2010
G.f.: x/(1-2x/(1-3x/(1+x-4x/(1-5x/(1+x-6x/(1-7x/(1+x-8x/(1-... (continued fraction). - Paul Barry, Jan 26 2011
a(n) = Sum_{k=0..n-1} (-1)^(n-k-1)*C(n-1,k)*(2*(k+1))!/(2^(k+1)*(k+1)!). - Paul Barry, Jan 26 2011
Conjecture: a(n) +2*(-n+1)*a(n-1) +2*(-n+2)*a(n-2)=0. - R. J. Mathar, Nov 15 2012
G.f.: x/G(0) where G(k) = 1 - 2*x*(2*k+1) - x^2*(2*k+2)*(2*k+3)/G(k+1) (continued fraction). - Sergei N. Gladkovskii, Jan 13 2013
G.f.: Q(0)-1, where Q(k) = 1 - x*(k+1)/( x*(k+1) - (1 +x)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 21 2013
a(n) ~ 2^(n-1/2) * n^(n-1) / exp(n+1/2). - Vaclav Kotesovec, Feb 04 2014
a(n) = A053871(n)/(2n-2) for n>1.
a(n) * (2n-2) satisfies the recurrence of A053871, so Detlef's conjecture was correct. And if we rewrite Mathar's conjecture as b(n) = 2*(n-1)*b(n-1) +2*(n-2)*b(n-2) it becomes quite clear that Mathar's b(n) = a(n-1). - Sergey Kirgizov, Jun 03 2022
EXAMPLE
a(1) = 0 trivially.
a(2) = 1 since there is a unique pairing disjoint to the canonical pairing, 01 23, and containing any of the 4 pairs not in the canonical pairing.
a(3) = 2 since there are 2 pairings disjoint to the canonical pairing, 01 23 45, and containing the pair 02, not in the canonical pairing: 02 14 35 and 02 15 34.
MAPLE
a:= n-> add((-1)^(n-k-1)*binomial(n-1, k)*(2*(k+1))!/(2^(k+1)*(k+1)!), k=0..n-1):
seq(a(n), n=0..20);
MATHEMATICA
a[n_] := Sum[(-1)^(n-k-2)* Binomial[n-2, k]*(2*(k+1))!/(2^(k+1)*(k+1)!) , {k, 0, n-2}]; a /@ Range[20]
(* Jean-François Alcover, Jul 11 2011, after Maple *)
CoefficientList[Series[-1+1/(E^x*Sqrt[1-2*x]) + Sqrt[2]*DawsonF[1/Sqrt[2]] + Sqrt[-Pi/(2*E)]*Erf[Sqrt[-1/2+x]], {x, 0, 20}], x]*Range[0, 20]! (* Vaclav Kotesovec, Feb 04 2014 *)
PROG
(bc)
define a(n)
{
auto sign, i, s;
s=0; sign = 1;
for ( i=0 ; i<=n-1 ; i++ ) {
s = s + sign * ffac(n-1-i) * c( n-2, i );
sign = sign * -1;
}
return s;
}
/* returns (2n-1)!! */
define ffac( n )
{
if ( n <= 1 ) return 1;
return (2*n-1)* ffac(n-1);
}
/* returns combinations of n things taken i at a time */
define c(n, i)
{
auto j, s;
s=1;
if ( n < 0 ) return 0;
for ( j=0 ; j<i ; j++ ) {
s = s*(n-j)/(j+1);
}
return s;
}
for (j=1; j<66; j++) { print(a(j)); ", "; } /* show terms */
quit
CROSSREFS
KEYWORD
nonn
AUTHOR
Lewis Mammel (l_mammel(AT)att.net), Oct 02 2009
STATUS
approved