|
| |
|
|
A165968
|
|
Number of pairings disjoint to a given pairing, and containing a given pair not in the given pairing.
|
|
3
|
|
|
|
0, 1, 2, 10, 68, 604, 6584, 85048, 1269680, 21505552, 407414816, 8535396256, 195927013952, 4890027052480, 131842951699328, 3818743350945664, 118253903175951104, 3898687202158805248, 136339489775029813760, 5040776996774472673792
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
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
|
|
|
|
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) * (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]
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
|
| |
|
|
