A007769 -id:A007769 - cp's OEIS frontend

A054499 Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.

1, 1, 2, 5, 17, 79, 554, 5283, 65346, 966156, 16411700, 312700297, 6589356711, 152041845075, 3811786161002, 103171594789775, 2998419746654530, 93127358763431113, 3078376375601255821, 107905191542909828013, 3997887336845307589431

Offset: 0

Christian G. Bower, Apr 06 2000 based on a problem by Wouter Meeussen

Place 2n points equally spaced on a circle. Draw lines to pair up all the points so that each point has exactly one partner. Allow turning over.

			For n=3, there are 5 bracelets with 3 pairs of beads. They are represented by the words aabbcc, aabcbc, aabccb, abacbc, and abcabc. All of the 6!/(2*2*2) = 90 combinations can be derived from these by some combination of relabeling the pairs, rotation, and reflection. So a(3) = 5. - _Michael B. Porter_, Jul 27 2016

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

W. Y.-C. Chen, D. C. Torney, Equivalence classes of matchings and lattice-square designs, Discr. Appl. Math. 145 (3) (2005) 349-357.
Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373 [math.GT], 2016-2017. See p. 252.
A. Khruzin, Enumeration of chord diagrams, arXiv:math/0008209 [math.CO], 2000.
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.
R. J. Mathar, Chord Diagrams A054499 (2018)
R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019)
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233.
Index entries for sequences related to bracelets

Cf. A007769, A104256, A279207, A279208, A003437 (loopless chord diagrams), A322176 (marked chords), A362657, A362658, A362659 (three, four, five instances of each color rather than two), A371305 (Multiset Transf.), A260847 (directed chords).

max = 19;
alpha[p_, q_?EvenQ] := Sum[Binomial[p, 2*k]*q^k*(2*k-1)!!, {k, 0, max}];
alpha[p_, q_?OddQ] := q^(p/2)*(p-1)!!;
a[0] = 1;
a[n_] := 1/4*(Abs[HermiteH[n-1, I/2]] + Abs[HermiteH[n, I/2]] + (2*Sum[Block[{q = (2*n)/p}, alpha[p, q]*EulerPhi[q]], {p, Divisors[ 2*n]}])/(2*n));
Table[a[n], {n, 0, max}] (* Jean-François Alcover, Sep 05 2013, after R. J. Mathar; corrected by Andrey Zabolotskiy, Jul 27 2016 *)

a(n) = (2*A007769(n) + A047974(n) + A047974(n-1))/4 for n > 0.

Corrected and extended by N. J. A. Sloane, Oct 29 2006

a(0)=1 prepended back again by Andrey Zabolotskiy, Jul 27 2016

A132101 a(n) = (A001147(n) + A047974(n))/2.

Original entry on oeis.org

1, 1, 3, 11, 65, 513, 5363, 68219, 1016481, 17243105, 327431363, 6874989963, 158118876449, 3952936627361, 106729080101235, 3095142009014843, 95949394016339393, 3166329948046914369, 110821547820208233731, 4100397266856761733515

Offset: 0

Keith F. Lynch, Oct 31 2007

Also, number of distinct Tsuro tiles which are digonal in shape and have n points per side. Turning over is not allowed. See A132100 for definition and comments.
See the Burns et al. papers for another interpretation.
From Ross Drewe, Mar 16 2008: (Start)
This is also the number of arrangements of n pairs which are equivalent under the joint operation of sequence reversal and permutations of labels. Assume that the elements of n distinct pairs are labeled to show the pair of origin, e.g., [1 1], [2 2]. The number of distinguishable ways of arranging these elements falls as the conditions are made more general:
a(n) = A000680: element order is significant and the labels are distinguishable;
b(n) = A001147: element order is significant but labels are not distinguishable, i.e., all label permutations of a given sequence are equivalent;
c(n) = A132101: element order is weakened (reversal allowed) and all label permutations are equivalent;
d(n) = A047974: reversal allowed, all label permutations are equivalent and equivalence class maps to itself under joint operation.
Those classes that do not map to themselves form reciprocal pairs of classes under the joint operation and their number is r(n). Then c = b - r/2 = b - (b - d)/2 = (b+d)/2. A formula for r(n) is not available, but formulas are available for b(n) = A001147 and d(n) = A047974, allowing an explicit formula for this sequence.
c(n) is useful in extracting structure information without regard to pair ordering (see example). c(n) terms also appear in formulas related to binary operators, e.g., the number of binary operators in a k-valued logic that are invertible in 1 operation.
a(n) = (b(n) + c(n))/2, where b(n) = (2n)!/(2^n * n!) = A001147(n), c(n) = Sum_{k=0..floor(n/2)} n!/((n-2*k)! * k!) = A047974(n).
For 3 pairs, the arrangement A = [112323] is the same as B = [212133] under the permutation of the labels [123] -> [312] plus reversal of the elements, or vice versa. The unique structure common to A and B is {1 intact pair + 2 interleaved pairs}, where the order is not significant (contrast A001147). (End)

			a(2)=3 counts the arrangements [1122], [1212] and [1221]. - _R. J. Mathar_, Oct 18 2019

G. C. Greubel, Table of n, a(n) for n = 0..400
Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts).
Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche, and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, Discrete Applied Mathematics, Volume 161, Issues 10-11, July 2013, Pages 1378-1394.
R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019), Section IV.

Cf. A000680, A001147, A047974, A007769, A054499.

Cf. A132100, A132101, A132102, A132103, A132104, A132105.

R:=PowerSeriesRing(Rationals(), 30);
Coefficients(R!(Laplace( (Exp(x+x^2) + 1/Sqrt(1-2*x))/2 ))); // G. C. Greubel, Jul 12 2024

A132101 := proc(n)
    (A001147(n)+A047974(n))/2 ;
end proc:
seq(A132101(n),n=0..30) ; # R. J. Mathar, Dec 20 2020

Table[((2n-1)!!+I^(-n)*HermiteH[n,I/2])/2,{n,0,30}] (* Jonathan Burns, Apr 05 2016 *)

[(factorial(n)*binomial(2*n,n) + (-2*i)^n*hermite(n,i/2))/2^(n+1) for n in range(31)] # G. C. Greubel, Jul 12 2024

D-finite with recurrence -(n-3)*a(n) +2*(n^2-3*n+1)*a(n-1) -(n-1)*a(n-2) -2*(2*n-5)*(n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Dec 20 2020

E.g.f.: (1/2)*( exp(x+x^2) + 1/sqrt(1-2*x) ). - G. C. Greubel, Jul 12 2024

Entry revised by N. J. A. Sloane, Nov 04 2011

A132100 Number of distinct Tsuro tiles which are square and have n points per side.

Original entry on oeis.org

1, 2, 35, 2688, 508277, 163715822, 79059439095, 53364540054860, 47974697008198313, 55410773910104281242, 79957746695043660483467, 140965507420235075126987480, 298142048193613276717321211805, 745056978435827991570581878537478

Offset: 0

Keith F. Lynch, Oct 31 2007

nonn

Turning over is not allowed, but rotation of the tile is allowed.
In the original Tsuro game the tiles are square and have two points on each side, one third and two thirds of the way along the side and arcs connecting these eight points in various ways.
The shapes of the arcs aren't significant, only which two points they connect is.
Each point is connected to exactly one other point.
There are 35 tiles, agreeing with the entry a(4) = 35 here.
If we vary the shape of the tile and the number of points per side (pps), we get the following table.
....pps:..0....1......2......3......4......5......6......7......8......9.....10
-------------------------------------------------------------------------------
circle....1....0......1......0......2......0......5......0.....18......0....105 (A007769)
monogon...1....0......1......0......3......0.....15......0....105......0....945 (A001147)
digon.....1....1......3.....11.....65....513...5363..68219 .................... (A132101)
triangle..1....0......7......0...3483......0.............0.............0
square....1....2.....35...2688.508277 ......................................... (this entry)
pentagon..1....0....193......0.............0.............0.............0
hexagon...1....5...1799
heptagon..1....0..19311......0.............0.............0.............0
octagon...1...18.254143
9-gon.....1....0.............0.............0.............0.............0
10-gon....1..105
The pps = 2 column is A132102. Blank entries all represent numbers greater than one million.
A monogon is distinct from a circle in that a monogon has not just one side, but also one vertex. Monogons and digons can't exist with straight sides, of course, at least not on a flat plane, but there's no rule that says these tiles have to have straight sides.
If we allow reflections the numbers are smaller (this would be appropriate for a game where the tiles were transparent and could be flipped over):
....pps:..0....1......2......3......4......5......6......7......8......9.....10
-------------------------------------------------------------------------------
circle....1....0......1......0......2......0......5......0.....17......0.....79 (A054499)
monogon...1....0......1......0......3......0.....11......0.....65......0....513 (A132101)
digon.....1....1......3......8.....45....283...2847..34518.511209 ............. (A132103)
triangle..1....0......7......0...1907......0.............0.............0
square....1....2.....30...1447.257107 ......................................... (A132104)
pentagon..1....0....137......0.............0.............0.............0
hexagon...1....5...1065
heptagon..1....0..10307......0.............0.............0.............0
octagon...1...17.130040
9-gon.....1....0.............0.............0.............0.............0
10-gon....1...79
The pps = 2 column is A132105.

Calliope Games, Tsuro
Mike Garrity, Path Tile Games, Jan 07 2012.

Cf. A132101-A132105, A007769, A001147, A054499.

# A(n,m) gives the number of n-sided tiles with m points per side (cf. comments)
# B(n,m) enumerates these tiles, also allowing reflections
with(numtheory): a:=(p,r)->piecewise(p mod 2 = 1,p^(r/2)*doublefactorial(r-1), sum(p^j*binomial(r, 2*j)*doublefactorial(2*j - 1), j = 0 .. floor(r/2)));
A := (n,m)->piecewise(n*m mod 2=1,0,add(phi(p)*a(p,m*n/p),p in divisors(n))/n);
B := (n,m)->A(n,m)/2+piecewise(n*m mod 2=0,piecewise(m mod 2=0,a(2,m*n/2)*2, a(2,m*n/2)+a(2,m*n/2-1))/4,0);
A132100 := m -> A(4,m);[seq(A132100(m),m=1..15)]; # Laurent Tournier, Jul 09 2014

From Laurent Tournier, Jul 09 2014: (Start)
a(m) = ((4m-1)!! + sum_{j=0..m} 2^j binomial(2m,2j) (2j-1)!! + 2 sum_{0<=2j<=m} 4^j binomial(m, 2j) (2j-1)!!)/4
More generally, if A(n,m) is the number of n-sided tiles with m points per side (with nm even),
A(n,m) = 1/n sum_{n=pq} phi(p)*alpha(p,mq), phi = Euler's totient function,
alpha(p,r) = sum_{0 <= 2j <= r} p^j binomial(r,2j) (2j-1)!! if p even,
           = p^(r/2) (r-1)!! if p odd.
If B(n,m) is the number of n-sided tiles with m points per side (with nm even), allowing reflections,
B(n,m) = (A(n,m) + alpha(2,mn/2))/2 if m even,
       = (A(n,m) + alpha(2,mn/2)/2 + alpha(2,mn/2-1)/2)/2 if m odd.
(End)

More terms from Laurent Tournier, Jul 09 2014

A132105 Number of distinct Tsuro tiles which are n-gonal in shape and have 2 points per side.

Original entry on oeis.org

1, 1, 3, 7, 30, 137, 1065, 10307, 130040, 1927853, 32809979, 625303343, 13178378742, 304081128617, 7623562484349, 206343110670031, 5996839161108904, 186254714746749377, 6156752738537004317, 215810382975655205399, 7995774673152799224930

Offset: 0

Keith F. Lynch, Oct 31 2007

nonn

Turning over is allowed.

See A132100 for definition and comments.

Cf. A132100-A132104, A007769, A001147, A054499.

# B(n,m) gives the number of n-sided tiles with m points per side, allowing reflections (cf. comments and formula of A132100)
with(numtheory): a:=(p,r)->piecewise(p mod 2 = 1,p^(r/2)*doublefactorial(r-1), sum(p^j*binomial(r, 2*j)*doublefactorial(2*j - 1), j = 0 .. floor(r/2)));
B := (n,m)->piecewise(n*m mod 2=1,0,add(phi(p)*a(p,m*n/p),p in divisors(n))/(2*n)+
piecewise(m mod 2=0, a(2,m*n/2)*2, a(2,m*n/2)+a(2,m*n/2-1))/4);
A132105 := n -> B(n,2);[seq(A132105(n),n=1..20)]; # Laurent Tournier, Jul 09 2014

More terms from Laurent Tournier, Jul 09 2014

A380615 Triangle read by rows: T(n,k) is the number of sensed combinatorial maps with n edges and k vertices, 1 <= k <= n + 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 8, 5, 2, 18, 38, 34, 14, 3, 105, 275, 288, 154, 42, 6, 902, 2614, 3102, 1959, 705, 140, 14, 9749, 30346, 39242, 27898, 11956, 3142, 473, 34, 127072, 415360, 573654, 446078, 217000, 68544, 13886, 1670, 95, 1915951, 6513999, 9484003, 7911844, 4230802, 1523176, 373188, 60614, 5969, 280

Offset: 0

Andrew Howroyd, Jan 28 2025

By duality, also the number of sensed combinatorial maps with n edges and k faces.

			Triangle begins:
n\k |      1       2       3       4       5      6      7     8   9
----+----------------------------------------------------------------
  0 |      1
  1 |      1,      1
  2 |      2,      2,      1;
  3 |      5,      8,      5,      2;
  4 |     18,     38,     34,     14,      3;
  5 |    105,    275,    288,    154,     42,     6;
  6 |    902,   2614,   3102,   1959,    705,   140,    14;
  7 |   9749,  30346,  39242,  27898,  11956,  3142,   473,   34;
  8 | 127072, 415360, 573654, 446078, 217000, 68544, 13886, 1670, 95;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A170946.
Main diagonal is A002995(n+1).
Second diagonal gives A380237.
Columns 1..3 are A007769, A380618, A380619.
Cf. A053979 (rooted), A379430 (planar), A380616 (unsensed), A380617 (achiral).

InvEulerMTS(p)={my(n=serprec(p, x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i)}
b(k,r)={if(k%2, if(r%2, 0, my(j=r/2); k^j*(2*j)!/(j!*2^j)), sum(j=0, r\2, binomial(r, 2*j)*k^j*(2*j)!/(j!*2^j)))}
C(k,r,y)={my(p=sumdiv(k,d,eulerphi(k/d)*y^d)/k); sum(i=0, r, abs(stirling(r,i,1))*p^i)/r!}
S(n,k,y)={sum(r=0, 2*n\k, if(k*r%2==0, x^(k*r/2)*b(k,r)*C(k,r,y)), O(x*x^n))}
G(n,y='y)={prod(k=1, 2*n, S(n,k,y))}
T(n)={[Vecrev(p/y) | p<-Vec(y+InvEulerMTS(G(n)))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) }

A380626 Array read by antidiagonals: T(n,k) is the number of sensed k-regular combinatorial maps with n vertices, n >= 0, k >= 1.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 2, 3, 1, 0, 1, 0, 7, 0, 1, 0, 1, 5, 29, 36, 11, 1, 0, 1, 0, 174, 0, 365, 0, 1, 0, 1, 18, 1475, 26614, 44106, 5250, 81, 1, 0, 1, 0, 16162, 0, 10107019, 0, 103801, 0, 1, 0, 1, 105, 214215, 102762168, 3703659517, 6605320523, 549530780, 2492164, 1228, 1, 0

Offset: 0

Andrew Howroyd, Jan 29 2025

The combinatorial maps considered are connected, unrooted, unlabeled, may have loops and parallel edges and are of any orientable genus.

			Array begins:
==================================================================
n\k | 1 2  3       4         5          6          7         8 ...
----+-------------------------------------------------------------
  0 | 1 1  1       1         1          1          1         1 ...
  1 | 0 1  0       2         0          5          0        18 ...
  2 | 1 1  3       7        29        174       1475     16162 ...
  3 | 0 1  0      36         0      26614          0 102762168 ...
  4 | 0 1 11     365     44106   10107019 3703659517 ...
  5 | 0 1  0    5250         0 6605320523 ...
  6 | 0 1 81  103801 549530780 ...
  7 | 0 1  0 2492164 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

Columns 2..6 (odd columns with interspersed zeros) are A000012, A129114, A292206, A380627, A380628.
Row n=1 is A007769 (with interspersed zeros).
Cf. A170946, A380622 (rooted), A380629.

InvEulerT(v)={dirdiv(Vec(log(1+x*Ser(v)),-#v), vector(#v,n,1/n))}
D(m,k)={my(g=gcd(m,k)); sumdiv(g, d, my(j=m/d); x^j*eulerphi(d)*k^(j-1)/j)}
G(n,m)={my(t=m*n); prod(k=1, t, my(A=O(x^(t\k+1)), p=serconvol(exp(A + D(m,k)), exp(A + D(2,k)))); sum(r=0, t\k, if(k*r%m==0, r!*polcoef(p,r)/(k^r)*x^(k*r/m)), O(x*x^n)) )}
T(n,k)=if(n==0, 1, InvEulerT(Vec(-1 + G(n,k), -n))[n])

A380629(n) = Sum_{d|2*n} T(d,2*n/d).

A132104 Number of distinct Tsuro tiles which are square and have Q points per side.

Original entry on oeis.org

1, 2, 30, 1447, 257107, 81898020, 39531524384, 26682303327353, 23987350539183237, 27705387002314059046, 39978873351170263411714, 70482753710219315731386411, 149071024096816130023228547735, 372528489217914304271725034290952, 1085920546070218942128273877774286532, 3651950796434146162433577686485443037885

Offset: 0

Keith F. Lynch, Oct 31 2007

nonn

Turning over is allowed.

See A132100 for definition and comments.

Cf. A132100-A132105, A007769, A001147, A054499.

# B(n,m) gives the number of n-sided tiles with m points per side, allowing reflections (cf. comments in A132100)
with(numtheory): a:=(p,r)->piecewise(p mod 2 = 1,p^(r/2)*doublefactorial(r-1), sum(p^j*binomial(r, 2*j)*doublefactorial(2*j - 1), j = 0 .. floor(r/2)));
B := (n,m)->piecewise(n*m mod 2=1,0,add(phi(p)*a(p,m*n/p),p in divisors(n))/(2*n) + piecewise(m mod 2=0, a(2,m*n/2)*2, a(2,m*n/2)+a(2,m*n/2-1))/4);
A132104 := m -> B(4,m);[seq(A132104(m),m=1..15)]; # Laurent Tournier, Jul 09 2014

More terms from Laurent Tournier, Jul 09 2014

A132102 Number of distinct Tsuro tiles which are n-gonal in shape and have 2 points per side.

Original entry on oeis.org

1, 1, 3, 7, 35, 193, 1799, 19311, 254143, 3828921, 65486307, 1249937335, 26353147811, 608142583137, 15247011443103, 412685556939751, 11993674252049647, 372509404162520641, 12313505313357313047, 431620764875678503143, 15991549339008732109899

Offset: 0

Keith F. Lynch, Oct 31 2007

nonn

Turning over is not allowed.
See A132100 for definition and comments.
Even and odd terms can be computed with the help of Burnside Lemma and recursive sequences. - Lionel RAVEL, Sep 18 2013

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

Cf. A001147, A007769, A054499, A132100, A132101, A132103, A132104, A132105.

with(numtheory): a:=(p,q)->piecewise(p mod 2 = 1, p^q*doublefactorial(2*q - 1), sum(p^j*binomial(2*q, 2*j)*doublefactorial(2*j - 1), j = 0 .. q));
A132102 := n->add(phi(p)*a(p,n/p),p in divisors(n))/n;
[seq(A132102(n),n=1..20)]; # Laurent Tournier, Jul 09 2014

a(n)={if(n<1, n==0, sumdiv(n, d, my(m=n/d); eulerphi(d)*sum(j=0, m, (d%2==0 || m-j==0) * binomial(2*m, 2*j) * d^j * (2*j)! / (j!*2^j) ))/n)} \\ Andrew Howroyd, Jan 26 2020

a(n) = (1/n)*Sum_{d|n} phi(d)*alpha(d, n/d), where phi = Euler's totient function,
alpha(p,q) = Sum_{j=0..q} p^j * binomial(2q, 2j) * (2j-1)!! if p even,
= p^q * (2q-1)!! if p odd. (cf. also A132100) - Laurent Tournier, Jul 09 2014

More terms from Lionel RAVEL, Sep 18 2013

a(9) and a(10) corrected, and addition of more terms using formula given above by Laurent Tournier, Jul 09 2014

A132103 Number of distinct Tsuro tiles which are digonal in shape and have Q points per side.

Original entry on oeis.org

1, 1, 3, 8, 45, 283, 2847, 34518, 511209

Offset: 0

Keith F. Lynch, Oct 31 2007

nonn

Turning over is allowed.

See A132100 for definition and comments.

Cf. A132100-A132105, A007769, A001147, A054499.

A279207 Number of analytic chord diagrams with n chords.

Original entry on oeis.org

1, 2, 5, 18, 102, 817, 7641

Offset: 1

N. J. A. Sloane, Dec 23 2016

Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373 [math.AG], 2016. See p. 252.

Cf. A007769, A054499, A279208.

cp's OEIS Frontend

A054499 Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A132101 a(n) = (A001147(n) + A047974(n))/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A132100 Number of distinct Tsuro tiles which are square and have n points per side.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A132105 Number of distinct Tsuro tiles which are n-gonal in shape and have 2 points per side.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A380615 Triangle read by rows: T(n,k) is the number of sensed combinatorial maps with n edges and k vertices, 1 <= k <= n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A380626 Array read by antidiagonals: T(n,k) is the number of sensed k-regular combinatorial maps with n vertices, n >= 0, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A132104 Number of distinct Tsuro tiles which are square and have Q points per side.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A132102 Number of distinct Tsuro tiles which are n-gonal in shape and have 2 points per side.