A003436 -id:A003436 - cp's OEIS frontend

A278994 Number of simple chord diagrams with n chords, modulo all symmetries.

0, 1, 1, 4, 18, 116, 1060, 13019, 193425, 3313522, 63667788, 1351700744, 31390695708, 791372281393, 21523271532811, 628166776833181, 19582955637428422, 649472761243051940, 22833268501579122332, 848230375982060558217

Offset: 1

N. J. A. Sloane, Dec 07 2016

nonn

E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.

Cf. A003436, A003437, A007474, A278990, A278991, A278992, A278993.

A306419 Number of set partitions of {1, ..., n} whose blocks are all singletons and pairs, not including {1, n} or {i, i + 1} for any i.

Original entry on oeis.org

1, 1, 1, 1, 4, 11, 32, 99, 326, 1123, 4064, 15291, 59924, 242945, 1019584, 4409233, 19648674, 89938705, 422744384, 2035739041, 10039057524, 50610247483, 260704414816, 1370387233859, 7346982653702, 40131663286851, 223238920709024, 1263531826402891, 7273434344119460

Offset: 0

Gus Wiseman, Feb 14 2019

Also the number of spanning subgraphs of the complement of an n-cycle, with no overlapping edges.

I.e., for n >= 3, also the number of matchings in the complement of the cycle graph C_n. - Eric W. Weisstein, Sep 02 2025

			The a(1) = 1 through a(5) = 11 set partitions:
  {{1}}  {{1}{2}}  {{1}{2}{3}}  {{13}{24}}      {{1}{24}{35}}
                                {{1}{24}{3}}    {{13}{24}{5}}
                                {{13}{2}{4}}    {{13}{25}{4}}
                                {{1}{2}{3}{4}}  {{14}{2}{35}}
                                                {{14}{25}{3}}
                                                {{1}{2}{35}{4}}
                                                {{1}{24}{3}{5}}
                                                {{1}{25}{3}{4}}
                                                {{13}{2}{4}{5}}
                                                {{14}{2}{3}{5}}
                                                {{1}{2}{3}{4}{5}}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000085, A000110, A000296, A001006, A001610, A003436 (no singletons), A034807, A170941 (linear case), A278990 (linear case with no singletons), A306417.

stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[stableSets[Complement[Subsets[Range[n],{2}],Sort/@Partition[Range[n],2,1,1]],Intersection[#1,#2]!={}&]],{n,0,10}]
(* Second program: *)
CompoundExpression[
  b[n_] := I^(1 - n) 2^((n - 1)/2) HypergeometricU[(1 - n)/2, 3/2, -1/2],
  Join[{1, 1, 1}, Table[Sum[(-1)^k b[n - 2 k] n (n - 1 - k)!/(k! (n - 2 k)!), {k, 0, n/2}], {n, 3, 20}]]
] (* Eric W. Weisstein, Sep 02 2025 *)

\\ here b(n) is A000085(n)
b(n) = {sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
a(n) = {if(n < 3, n >= 0, sum(k=0, n\2, (-1)^k*b(n-2*k)*n*(n-1-k)!/(k!*(n-2*k)!)))} \\ Andrew Howroyd, Aug 30 2019

a(n) = Sum_{k=0..floor(n/2)} (-1)^k*A034807(n, k)*A000085(n-2*k) for n > 2. - Andrew Howroyd, Aug 30 2019

Terms a(16) and beyond from Andrew Howroyd, Aug 30 2019

A231622 (2n+1)a(n+1) = (4n^2+1)a(n) + (2n+1)a(n-1) with n>1, a(0)=2, a(1)=-1.

Original entry on oeis.org

2, -1, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749, 113184512236563589997407

Offset: 0

Michael Somos, Nov 11 2013

sign

			G.f. = 2 - x + x^2 + 4*x^3 + 31*x^4 + 293*x^5 + 3326*x^6 + 44189*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..403

Cf. A003436.

A231622 := n -> (-1)^n*2*hypergeom([n, -n], [], 1/2):
seq(simplify(A231622(n)),n=0..19); # Peter Luschny, Nov 10 2016

a[ n_] := With[{m = Abs@n}, Boole[m == 0] + (2*m - 1)!! Hypergeometric1F1[ -m, 1 - 2*m, -2]]

{a(n) = n=abs(n); if( n<2, 2 - 3*(n>0), ( a(n-1) * (4*n^2 - 8*n + 5) + a(n-2) * (2*n-1) ) / (2*n-3))}

E.g.f. A(x) satisfies 0 = f(A(x), A'(x), A''(x)) where f(u0, u1, u2) = (3 + 2*x)*u0 + (5 + 2*x)*u1 + (-1 + 4*x^2)*u2.
a(-n) = a(n). a(n) = A003436(n) if n>1.
a(n) = (-1)^n*2*hypergeom([n, -n], [], 1/2). - Peter Luschny, Nov 10 2016

A324445 Number of labeled cyclic chord diagrams with n chords such that the minimal chord length equals one.

Original entry on oeis.org

1, 2, 11, 74, 652, 7069, 90946, 1353554, 22870541, 432424178, 9044698456, 207336529399, 5168830168426, 139221843251594, 4028994710377547, 124670425690921634, 4107486007743301396, 143555848444786921189, 5304751937400100397626, 206646474536314180818218

Offset: 1

Alois P. Heinz, Feb 28 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..404

Column k=1 of A324429.

Cf. A001147, A003436.

a(n) = A001147(n) - A003436(n).

A324446 Number of labeled cyclic chord diagrams with n chords such that the minimal chord length equals two.

Original entry on oeis.org

1, 3, 24, 225, 2489, 32326, 483968, 8211543, 155740501, 3265307342, 74995101843, 1872508994356, 50500982610620, 1463062187672336, 45314261742435296, 1494164679669072424, 52257665502536426741, 1932255827699763531474, 75312621088768346098203

Offset: 2

Alois P. Heinz, Feb 28 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..404

Column k=2 of A324429.

Cf. A003436, A306386.

a(n) = A003436(n) - A306386(n).

A378862 Number of minimum edge covers in the n-cycle complement graph.

Original entry on oeis.org

0, 1, 5, 4, 70, 31, 972, 293, 14476, 3326, 237575, 44189, 4305960, 673471, 85836485, 11588884, 1871150248, 222304897

Offset: 3

Eric W. Weisstein, Dec 09 2024

For even n, the minimum edge covers are perfect matchings. - Andrew Howroyd, Dec 10 2024

Eric Weisstein's World of Mathematics, Cycle Complement Graph.
Eric Weisstein's World of Mathematics, Minimum Edge Cover.

Cf. A003436, A278990, A351587, A356212.

a(2*n) = A003436(n). - Andrew Howroyd, Dec 10 2024

a(2*n+1) = (n-1)*(2*n+1)*A278990(n). - Detlef Meya, Dec 12 2024

a(10)-a(20) from Andrew Howroyd, Dec 10 2024

A305402 A number triangle T(n,k) read by rows for 0<=k<=n, related to the Taylor expansion of f(u, p) = (1/2)(1+1/(sqrt(1-u^2)))exp(p*sqrt(1-u^2)).

Original entry on oeis.org

1, 1, -2, 3, -4, 2, 15, -18, 9, -2, 105, -120, 60, -16, 2, 945, -1050, 525, -150, 25, -2, 10395, -11340, 5670, -1680, 315, -36, 2, 135135, -145530, 72765, -22050, 4410, -588, 49, -2, 2027025, -2162160, 1081080, -332640, 69300, -10080, 1008, -64, 2

Offset: 0

Johannes W. Meijer, May 31 2018

The function f(u, p) = (1/2)*(1+1/(sqrt(1-u^2))) * exp(p*sqrt(1-u^2)) was found while studying the Fresnel-Kirchhoff and the Rayleigh-Sommerfeld theories of diffraction, see the Meijer link.
The Taylor expansion of f(u, p) leads to the number triangle T(n, k), see the example section.
Normalization of the triangle terms, dividing the T(n, k) by T(n-k, 0), leads to A084534.
The row sums equal A003436, n >= 2, respectively A231622, n >= 1.

			The first few terms of the Taylor expansion of f(u; p) are:
f(u, p) = exp(p) * (1 + (1-2*p) * u^2/4 + (3-4*p+2*p^2) * u^4/16 + (15-18*p+9*p^2-2*p^3) * u^6/96 + (105-120*p+60*p^2-16*p^3+2*p^4) * u^8/768 + ... )
The first few rows of the T(n, k) triangle are:
n=0:     1
n=1:     1,     -2
n=2:     3,     -4,    2
n=3:    15,    -18,    9,    -2
n=4:   105,   -120,   60,   -16,   2
n=5:   945,  -1050,  525,  -150,  25,  -2
n=6: 10395, -11340, 5670, -1680, 315, -36, 2

J. W. Goodman, Introduction to Fourier Optics, 1996.
A. Papoulis, Systems and Transforms with Applications in Optics, 1968.

Andrew Howroyd, Rows n=0..50 of triangle, flattened
M. J. Bastiaans, The Wigner distribution function applied to optical signals and systems, Optics Communications, Vol. 25, nr. 1, pp. 26-30, 1978.
H. J. Butterweck, General theory of linear, coherent optical data processing systems, Journal of the Optical Society of America, Vol. 67, nr. 1, pp. 60-70, 1977.
J. W. Meijer, A note on optical diffraction, 1979.

Cf. A003436, A231622, A032184, A084534, A127674, A132062, A001497.
Cf. Related to the left hand columns: A001147, A001193, A261065.
Cf. Related to the right hand columns: A280560, A162395, A006011, A040977, A053347, A054334, A266561.

[[n le 0 select 1 else (-1)^k*2^(k-n+1)*Factorial(2*n-k-1)*Binomial(n, k)/Factorial(n-1): k in [0..n]]: n in [1..10]]; // G. C. Greubel, Nov 08 2018

T := proc(n, k): if n=0 then 1 else (-1)^k*2^(k-n+1)*n*(2*n-k-1)!/(k!*(n-k)!) fi: end: seq(seq(T(n, k), k=0..n), n=0..8);

Table[If[n==0 && k==0,1, (-1)^k*2^(k-n+1)*n*(2*n-k-1)!/(k!*(n-k)!)], {n, 0, 10}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 08 2018 *)

T(n,k) = {if(n==0, 1, (-1)^k*2^(k-n+1)*n*(2*n-k-1)!/(k!*(n-k)!))}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 08 2018

T(n, k) = (-1)^k*2^(k-n+1)*n*(2*n-k-1)!/(k!*(n-k)!), n > 0 and 0 <= k <= n, T(0, 0) = 1.
T(n, k) = (-1)^k*A001147(n-k)*A084534(n, k), n >= 0 and 0 <= k <= n.
T(n, k) = 2^(2*(k-n)+1)*A001147(n-k)*A127674(n, n-k), n > 0 and 0 <= k <= n, T(0, 0) = 1.
T(n, k) = (-1)^k*(A001497(n, k) + A132062(n, k)), n >= 1, T(0,0) = 1.

A316531 a(n) is the maximum number of perfect matchings of a graph with 2n vertices that contains exactly three disjoint perfect matchings.

Original entry on oeis.org

3, 6, 9, 13, 20, 32, 52

Offset: 2

Mario Krenn, Oct 20 2018

Take a cycle graph which has two perfect matchings (PM), and add one PM that is disjoint to it. The number of possible PMs one can add is given by A003436. One ends up with a set of three disjoint perfect matchings (where disjoint means that each edge is an element of maximally one PM), but the graph will have more PMs. This sequence describes the maximum number of PMs that such a graph can have.

Ilya Bogdanov, Graphs with only disjoint perfect matchings, MathOverflow.
Mario Krenn, Xuemei Gu, and Anton Zeilinger, Quantum experiments and graphs: Multiparty states as coherent superpositions of perfect matchings, Physical review letters, 119(24), 240403 (2017).

Cf. A003436.

a(8) from Mario Krenn, Jul 20 2024

A320727 a(n) is the minimal number of perfect matchings of a graph with 2n vertices that contains exactly three disjoint perfect matchings.

Original entry on oeis.org

3, 4, 5, 6, 6, 8, 9

Offset: 2

Mario Krenn, Oct 20 2018

Take a cycle graph which has two perfect matchings (PM), and add one PM that is disjoint to it. The number of possible PMs one can add is given by A003436. One ends up with a set of three disjoint perfect matchings (where disjoint means that each edge is an element of maximally one PM), but the graph will have more PMs. This sequence describes the minimal number of PMs that such a graph can have.

Ilya Bogdanov, Graphs with only disjoint perfect matchings, MathOverflow.
Mario Krenn, Xuemei Gu, and Anton Zeilinger, Quantum experiments and graphs: Multiparty states as coherent superpositions of perfect matchings, Physical review letters, 119(24), 240403 (2017).

Cf. A003436.

a(8) from Mario Krenn, Jul 20 2024

cp's OEIS Frontend

A278994 Number of simple chord diagrams with n chords, modulo all symmetries.

Views

Author

Keywords

Links

Crossrefs

A306419 Number of set partitions of {1, ..., n} whose blocks are all singletons and pairs, not including {1, n} or {i, i + 1} for any i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A231622 (2*n+1)*a(n+1) = (4*n^2+1)*a(n) + (2*n+1)*a(n-1) with n>1, a(0)=2, a(1)=-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A324445 Number of labeled cyclic chord diagrams with n chords such that the minimal chord length equals one.

Views

Author

Keywords

Links

Crossrefs

Formula

A324446 Number of labeled cyclic chord diagrams with n chords such that the minimal chord length equals two.

Views

Author

Keywords

Links

Crossrefs

Formula

A378862 Number of minimum edge covers in the n-cycle complement graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A305402 A number triangle T(n,k) read by rows for 0<=k<=n, related to the Taylor expansion of f(u, p) = (1/2)*(1+1/(sqrt(1-u^2)))*exp(p*sqrt(1-u^2)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A316531 a(n) is the maximum number of perfect matchings of a graph with 2n vertices that contains exactly three disjoint perfect matchings.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A320727 a(n) is the minimal number of perfect matchings of a graph with 2n vertices that contains exactly three disjoint perfect matchings.

Views

A231622 (2n+1)a(n+1) = (4n^2+1)a(n) + (2n+1)a(n-1) with n>1, a(0)=2, a(1)=-1.

A305402 A number triangle T(n,k) read by rows for 0<=k<=n, related to the Taylor expansion of f(u, p) = (1/2)(1+1/(sqrt(1-u^2)))exp(p*sqrt(1-u^2)).