cp's OEIS Frontend

A165968 Number of pairings disjoint to a given pairing, and containing a given pair not in the given pairing.

%I A165968 #76 Dec 10 2024 11:18:50
%S A165968 0,1,2,10,68,604,6584,85048,1269680,21505552,407414816,8535396256,
%T A165968 195927013952,4890027052480,131842951699328,3818743350945664,
%U A165968 118253903175951104,3898687202158805248,136339489775029813760,5040776996774472673792
%N A165968 Number of pairings disjoint to a given pairing, and containing a given pair not in the given pairing.
%C A165968 The formula is derived by an application of the principle of inclusion and exclusion.
%C A165968 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.
%C A165968 Hankel transform of a(n+1) is A168467. Binomial transform of a(n+1) is A001147(n+1). - _Paul Barry_, Jan 26 2011
%C A165968 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
%D A165968 John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, Chapter 3
%H A165968 Michael De Vlieger, <a href="/A165968/b165968.txt">Table of n, a(n) for n = 1..405</a>
%H A165968 Jean-Luc Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science,  Vol 17, No 3 (2016).
%H A165968 Marilena Barnabei, Niccolò Castronuovo, and Matteo Silimbani, <a href="https://arxiv.org/abs/2412.03449">Hertzsprung patterns on involutions</a>, arXiv:2412.03449 [math.CO], 2024. See p. 10.
%H A165968 Célia Biane, Greg Hampikian, Sergey Kirgizov, and Khaydar Nurligareev, <a href="https://arxiv.org/abs/2404.18802">Endhered patterns in matchings and RNA</a>, arXiv:2404.18802 [math.CO], 2024. See pp. 8-9.
%F A165968 a(n) = (2n-3)!! - C(n-2,1) * (2n-5)!! + ... +/- C(n-2,n-1)*3!! -/+ 1.
%F A165968 a(n) = (2*n-4)*a(n-1) +(2*n-6)*a(n-2) for n>2. - _Gary Detlefs_, Jul 11 2010
%F A165968 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
%F A165968 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
%F A165968 Conjecture: a(n) +2*(-n+1)*a(n-1) +2*(-n+2)*a(n-2)=0. - _R. J. Mathar_, Nov 15 2012
%F A165968 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
%F A165968 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
%F A165968 a(n) ~ 2^(n-1/2) * n^(n-1) / exp(n+1/2). - _Vaclav Kotesovec_, Feb 04 2014
%F A165968 a(n) = A053871(n)/(2n-2) for n>1.
%F A165968 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
%e A165968 a(1) = 0 trivially.
%e A165968 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.
%e A165968 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.
%p A165968 a:= n-> add((-1)^(n-k-1)*binomial(n-1,k)*(2*(k+1))!/(2^(k+1)*(k+1)!), k=0..n-1):
%p A165968 seq(a(n), n=0..20);
%t A165968 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]
%t A165968 (* _Jean-François Alcover_, Jul 11 2011, after Maple *)
%t A165968 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 *)
%o A165968 (bc)
%o A165968 define a(n)
%o A165968 {
%o A165968     auto sign, i,s;
%o A165968     s=0; sign = 1;
%o A165968     for ( i=0 ; i<=n-1 ; i++ ) {
%o A165968         s = s + sign * ffac(n-1-i) * c( n-2, i );
%o A165968         sign = sign * -1;
%o A165968     }
%o A165968     return s;
%o A165968 }
%o A165968 /* returns (2n-1)!! */
%o A165968 define ffac( n )
%o A165968 {
%o A165968     if ( n <= 1 ) return 1;
%o A165968     return  (2*n-1)* ffac(n-1);
%o A165968 }
%o A165968 /* returns combinations of n things taken i at a time */
%o A165968 define c(n,i)
%o A165968 {
%o A165968     auto j,s;
%o A165968     s=1;
%o A165968     if ( n < 0 ) return 0;
%o A165968     for ( j=0 ; j<i ; j++ ) {
%o A165968         s = s*(n-j)/(j+1);
%o A165968     }
%o A165968     return s;
%o A165968 }
%o A165968 for (j=1; j<66; j++)  { print(a(j)); ", "; }  /* show terms */
%o A165968 quit
%Y A165968 Cf. A001147, the double factorial.
%Y A165968 Cf. also A053871.
%Y A165968 Cf. A168467.
%K A165968 nonn
%O A165968 1,3
%A A165968 Lewis Mammel (l_mammel(AT)att.net), Oct 02 2009