A337302 -id:A337302 - cp's OEIS frontend

A000316 Two decks each have n kinds of cards, 2 of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. a(n) is the number of ways of achieving no matches.

1, 0, 4, 80, 4752, 440192, 59245120, 10930514688, 2649865335040, 817154768973824, 312426715251262464, 145060238642780180480, 80403174342119992692736, 52443098500204184915312640, 39764049487996490505336537088

Offset: 0

N. J. A. Sloane

Each deck contains 2n cards.
The probability of no matches is a(n)/(2n)!.
n couples meet for a party and they exchange gifts. Each of the 2n writes their name on a piece of paper and puts it into a hat. They take turns drawing names and give their gift to the person whose name they drew. If anyone draws either their own name or the name of their partner, everyone puts the name they have drawn back into the hat and everyone draws anew. a(n) is the number of different permissible drawings. - Dan Dima, Dec 17 2006
(2n)! / a(n) is the expected number of deck shuffles until no matches occur. a(n) / (2n)! is the probability for a permissible drawing to be achieved. (2n)! / a(n) is the expected number of drawings before a permissible drawing is achieved. As n goes to infinity (2n)! / a(n) will strictly decrease very slowly to e^2 ~ 7.38906 (starting from n > 2) - Dan Dima, Dec 17 2006
a(n) equals the permanent of the (2n)X(2n) matrix with 0's along the main diagonal and the antidiagonal, and 1's everywhere else. - John M. Campbell, Jul 11 2011
Also, number of permutations p of (1,...,2n) such that round(p(k)/2) != round(k/2) for all k=1,...,2n (where half-integers are rounded up). - M. F. Hasler, Sep 30 2015

			There are 80 ways of achieving zero matches when there are 2 cards of each kind and 3 kinds of card so a(3)=80.
Among the 24 (multiset) permutations of {1,1',2,2'}, only {2,2',1,1'}, {2',2,1,1'}, {2,2',1',1} and {2',2,1',1} have no fixed points, thus a(2)=4.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 187.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
L. I. Nicolaescu, Derangements and asymptotics of the Laplace transforms of large powers of a polynomial, New York J. Math. 10 (2004) 117-131.
John Riordan and N. J. A. Sloane, Correspondence, 1974
E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).
Index entries for sequences related to card matching

Cf. A000166, A000459, A337302.

p := (x,k)->k!^2*sum(x^j/((k-j)!^2*j!),j=0..k); R := (x,n,k)->p(x,k)^n; f := (t,n,k)->sum(coeff(R(x,n,k),x,j)*(t-1)^j*(n*k-j)!,j=0..n*k); seq(f(0,n,2), n=0..18);

(* b = A000459 *)
b[n_] := b[n] = Switch[n, 0, 1, 1, 0, 2, 1, _, n(2n-1) b[n-1] + 2n(n-1) b[n-2] - (2n-1)];
a[n_] := b[n] * 2^n;
Array[a, 14] (* Jean-François Alcover, Oct 30 2019 *)

a(n)=if(n==0, 1, round(2^(n/2+3/4)/Pi^.5*exp(-2)*n!*besselk(1/2+n,2^.5))<M. F. Hasler, Sep 27 2015

\\ Illustration of the multiset-fixed-point interpretation
count(n,c=ceil(vector(n,i,i)/2))=sum(k=1,n!,!setsearch(Set(ceil(Vec(numtoperm(n,k))/2)-c),0))
a(n) = count(2*n) \\ M. F. Hasler, Sep 30 2015

a(n) = A000459(n)*2^n.
G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(-1)^j*(n*k-j)! where n is the number of kinds of cards, k is the number of cards of each kind (2 in this case) and R(x, n, k) is the rook polynomial given by R(x, n, k)=(k!^2*Sum_{j=0..k} x^j/((k-j)!^2*j!))^n (see Riordan). coeff(R(x, n, k), x, j) indicates the coefficient for x^j of the rook polynomial.
From Dan Dima, Dec 17 2006: (Start)
a(n) = n! * Sum_{a,b >= 0, a+b <= n} (-1)^b * 2^(a+2*b) * (2*n-2*a-b)! / (a! * b! * (n-a-b)!).
a(n) = n * a(n-1) + n! * 4^n * Sum_{a=0..n} (-1)^a / (a! * 2^a). (End)
a(n) = 2^n * round(2^(n/2 + 3/4)*Pi^(-1/2)*exp(-2)*n!*BesselK(1/2+n,2^(1/2))) for n > 0. - Mark van Hoeij, Oct 30 2011
Recurrence: (2*n-3)*a(n) = 2*(n-1)*(2*n-1)^2*a(n-1) + 4*(n-1)*(2*n-3)*a(n-2) - 16*(n-2)*(n-1)*(2*n-1)*a(n-3). - Vaclav Kotesovec, Aug 07 2013
From Peter Bala, Jul 07 2014: (Start)
a(n) = Integral_{x>=0} exp(-x)*(x^2 - 4*x + 2)^n dx. Cf. A000166(n) = Integral_{x>=0} exp(-x)*(x - 1)^n dx.
Asymptotic: a(n) ~ (2*n)!*exp(-2)*( 1 - 1/(2*n) - 23/(96*n^2) + O(1/n^3) ). See Nicolaescu. (End)

Formulae, more terms etc. from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000
Edited by M. F. Hasler, Sep 27 2015 and N. J. A. Sloane, Oct 02 2015
a(0)=1 prepended by Andrew Howroyd, Oct 09 2020

A309283 Number of equivalence classes of X-based filling of diagonals in a diagonal Latin square of order n.

Original entry on oeis.org

1, 1, 0, 0, 2, 2, 3, 3, 20, 20, 67, 67, 596, 596

Offset: 0

Eduard I. Vatutin, Jul 06 2020

Used for getting strong canonical forms (SCFs) of the diagonal Latin squares and for fast enumerating of the diagonal Latin squares based on equivalence classes.
K1 = |C[1]|*f[1] + |C[2]|*f[2] + ... + |C[m]|*f[m],
K2 = K1 * n!,
where m = a(n), number of equivalence classes for X-based filling of diagonals in a diagonal Latin square of order n;
C[i], corresponding equivalence classes with cardinalities |C[i]|, 1 <= i <= m;
f[i], the number of diagonal Latin squares corresponds to the each item from equivalence class C[i], 1 <= i <= m;
K1 = A274171(n), number of diagonal Latin squares of order n with fixed first row;
K2 = A274806(n), number of diagonal Latin squares of order n.
For all t>0 a(2*t) = a(2*t+1). - Eduard I. Vatutin, Aug 21 2020
a(14) >= 5225, a(15) >= 5225. - Natalia Makarova, Sep 12 2020
The number of solutions in an equivalence class with the main diagonal in ascending order is at most 4*2^r*r! where r = floor(n/2). This maximum is achieved for orders n >= 10. - Andrew Howroyd, Mar 27 2023

			For order n=4 there are a(4)=2 equivalence classes. First of them C[1] includes two X-based fillings of diagonals
   0..1  0..2
   .13.  .10.
   .02.  .32.
   2..3  1..3
and second C[2] also includes two X-based fillings of diagonals
   0..1  0..2
   .10.  .13.
   .32.  .02.
   2..3  1..3
It is easy to see that f[1] = 0 and f[2] = 1, so K1(4) = A274171(4) = 2*0 + 2*1 = 2 and K2(4) = A274806(4) = K1(4) * 4! = 2 * 24 = 48.

S. Kochemazov, O. Zaikin, E. Vatutin, and A. Belyshev, Enumerating Diagonal Latin Squares of Order Up to 9, Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2.
Natalia Makarova, All 67 rules for SN DLS of order 11
Natalia Makarova and Harry White, About unique diagonals for SN DLS of order 14 and 15
E. I. Vatutin, About the number of strong normalized lines of diagonal Latin squares of orders 1-10 (in Russian).
E. I. Vatutin, About the number of strong normalized lines of diagonal Latin squares of order 11 (in Russian).
E. I. Vatutin, About the a(2*t)=a(2*t+1) equality (in Russian).
E. I. Vatutin, About the number of equivalence classes of X-based filling of diagonals in a diagonal Latin squares of order 12 (in Russian).
E. I. Vatutin, About the number of equivalence classes of X-based filling of diagonals in a diagonal Latin squares of order 13 (in Russian).
E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A274171, A274806, A337302, A338084.

a(n) = A338084(floor(n/2)).

a(11) added by Eduard I. Vatutin, Aug 21 2020
a(12)-a(13) by Harry White, added by Natalia Makarova, Sep 12 2020
a(0)=1 prepended by Andrew Howroyd, Oct 31 2020

A337303 Number of X-based filling of diagonals in a diagonal Latin square of order n.

Original entry on oeis.org

1, 1, 0, 0, 96, 480, 57600, 403200, 191600640, 1724405760, 1597368729600, 17571056025600, 28378507272192000, 368920594538496000, 952903592436341145600, 14293553886545117184000, 55442575636536644075520000, 942523785821122949283840000, 5231730206388249282710863872000

Offset: 0

Eduard I. Vatutin, Aug 22 2020

nonn

Used for getting strong canonical forms (SCFs) of the diagonal Latin squares and for fast enumerating of the diagonal Latin squares based on equivalence classes.

			One of the 96 X-based fillings of diagonals of a diagonal Latin square for order n=4:
1 . . 0
. 0 1 .
. 3 2 .
2 . . 3

Andrew Howroyd, Table of n, a(n) for n = 0..100
S. Kochemazov, O. Zaikin, E. Vatutin E., and A. Belyshev, Enumerating Diagonal Latin Squares of Order Up to 9, Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2.
E. I. Vatutin, About the number of X-based fillings of diagonals in a diagonal Latin squares of orders 1-15 (in Russian).
E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A000316, A000459, A309283, A274171, A337302.

\\ here b(n) is A000459.
b(n) = {sum(m=0, n, sum(k=0, n-m, (-1)^k * binomial(n, k) * binomial(n-k, m) * 2^(2*k+m-n) * (2*n-2*m-k)! )); }
a(n) = {2^(n\2) * b(n\2) * n!} \\ Andrew Howroyd, Mar 26 2023

a(n) = A337302(n)*n!.

a(n) = n!*A000316(floor(n/2)). - Andrew Howroyd, Mar 26 2023

a(0)=1 prepended and terms a(16) and beyond from Andrew Howroyd, Mar 26 2023

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A309283 Number of equivalence classes of X-based filling of diagonals in a diagonal Latin square of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A337303 Number of X-based filling of diagonals in a diagonal Latin square of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions