A000316 -id:A000316 - cp's OEIS frontend

A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.

1, 0, 1, 10, 297, 13756, 925705, 85394646, 10351036465, 1596005408152, 305104214112561, 70830194649795010, 19629681235869138841, 6401745422388206166420, 2427004973632598297444857, 1058435896607583305978409166, 526149167104704966948064477665

Offset: 0

N. J. A. Sloane

Original definition: Number of permutations with no hits on 2 main diagonals. (Identical to definition of A000316.) - M. F. Hasler, Sep 27 2015
Card-matching numbers (Dinner-Diner matching numbers): A deck has n kinds of cards, 2 of each kind. The deck is shuffled and dealt in to n hands with 2 cards each. A match occurs for every card in the j-th hand of kind j. A(n) is the number of ways of achieving no matches. The probability of no matches is A(n)/((2n)!/2!^n).
Also, Penrice's Christmas gift numbers (see Penrice 1991).
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 3 pure options. - Raimundas Vidunas, Jan 22 2014

			There are 297 ways of achieving zero matches when there are 2 cards of each kind and 4 kinds of card so a(4)=297.
From _Peter Bala_, Jul 08 2014: (Start)
a(3) = 10: the 10 permutations of the multiset {1,1,2,2,3,3} that have no fixed points are
{2,2,3,3,1,1}, {3,3,1,1,2,2}
{2,3,1,3,1,2}, {2,3,1,3,2,1}
{2,3,3,1,1,2}, {2,3,3,1,2,1}
{3,2,1,3,1,2}, {3,2,1,3,2,1}
{3,2,3,1,1,2}, {3,2,3,1,2,1}
(End)

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, pp. 174-178.
R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997, p. 71.
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
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
Shalosh B. Ekhad, Christoph Koutschan, and Doron Zeilberger, There are EXACTLY 1493804444499093354916284290188948031229880469556 Ways to Derange a Standard Deck of Cards (ignoring suits) [and many other such useful facts], arXiv:2101.10147 [math.CO], 2021.
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
P. A. MacMahon, Combinatory Analysis Cambridge: The University Press 1915-1916
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
B. H. Margolius, Dinner-Diner Matching Probabilities
R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411--425, 1997.
L. I. Nicolaescu, Derangements and asymptotics of the Laplace transforms of large powers of a polynomial, New York J. Math. 10 (2004) 117-131.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98 (1991), 617-620.
John Riordan and N. J. A. Sloane, Correspondence, 1974
R. Vidunas, Counting derangements and Nash equilibria, arXiv preprint arXiv:1401.5400 [math.CO], 2014-2016.
Raimundas Vidunas, Counting derangements and Nash equilibria Ann. Comb. 21, No. 1, 131-152 (2017).
Wikipedia, Permutations of multisets
Index entries for sequences related to card matching

Cf. A000166, A008290, A059056-A059071, A033581, A059073.

Row n=2 of A372307.

I:=[0,1]; [n le 2 select I[n] else n*(2*n-1)*Self(n-1)+2*n*(n-1)*Self(n-2)-(2*n-1): n in [1..30]]; // Vincenzo Librandi, Sep 28 2015

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)/2!^n,n=0..18);

RecurrenceTable[{(2*n+3)*a[n+3]==(2*n+5)^2*(n+2)*a[n+2]+(2*n+3)*(n+2)*a[n+1]-2*(2*n+5)*(n+1)*(n+2)*a[n],a[1]==0,a[2]==1,a[3]==10},a,{n,1,25}] (* Vaclav Kotesovec, Aug 31 2012 *)
a[n_] := a[n] = n*(2*n-1)*a[n-1] + 2*n*(n-1)*a[n-2] - (2*n-1); a[0] = 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 04 2013 *)
a[n_] := Sum[(2*(n-m))! / 2^(n-m) Binomial[n, m] Hypergeometric1F1[m-n, 2*(m - n), -4], {m, 0, n}]; Table[a[n], {n, 0, 16}] (* Peter Luschny, Nov 15 2023 *)

a(n) = (2^n*round(2^(n/2+3/4)*Pi^(-1/2)*exp(-2)*n!*besselk(1/2+n,2^(1/2))))/2^n;
vector(15, n, a(n))\\ Altug Alkan, Sep 28 2015

{ A000459(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)! )); } \\ Max Alekseyev, Oct 06 2016

a(n) = A000316(n)/2^n.
a(n) = Sum_{k=0..n} Sum_{m=0..n-k} (-1)^k * n!/(k!*m!*(n-k-m)!) * 2^(2*k+m-n) * (2*n-2*m-k)!. - Max Alekseyev, Oct 06 2016
G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(t-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 coeff(R(x, n, k), x, j) is the coefficient of x^j of the rook polynomial R(x, n, k) = (k!^2*sum(x^j/((k-j)!^2*j!))^n (see Riordan or Stanley).
D-finite with recurrence a(n) = n*(2*n-1)*a(n-1)+2*n*(n-1)*a(n-2)-(2*n-1), a(1) = 0, a(2) = 1.
a(n) = round(2^(n/2 + 3/4)*Pi^(-1/2)*exp(-2)*n!*BesselK(1/2+n,2^(1/2))). - Mark van Hoeij, Oct 30 2011
(2*n+3)*a(n+3)=(2*n+5)^2*(n+2)*a(n+2)+(2*n+3)*(n+2)*a(n+1)-2*(2*n+5)*(n+1)*(n+2)*a(n). - Vaclav Kotesovec, Aug 31 2012
Asymptotic: a(n) ~ n^(2*n)*2^(n+1)*sqrt(Pi*n)/exp(2*n+2), Vaclav Kotesovec, Aug 31 2012
a(n) = (1/2^n)*A000316(n) = int_{0..inf} exp(-x)*(1/2*x^2 - 2*x + 1)^n dx. Asymptotic: a(n) ~ ((2*n)!/2^n)*exp(-2)*( 1 - 1/(2*n) - 23/(96*n^2) + O(1/n^3) ). See Nicolaescu. - Peter Bala, Jul 07 2014
Let S = x_1 + ... + x_n. a(n) equals the coefficient of (x_1*...*x_n)^2 in the expansion of product {i = 1..n} (S - x_i)^2 (MacMahon, Chapter III). - Peter Bala, Jul 08 2014
Conjecture: a(n+k) - a(n) is divisible by k. - Mark van Hoeij, Nov 15 2023

More terms and edited by Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000
Edited by M. F. Hasler, Sep 27 2015
a(0)=1 prepended by Max Alekseyev, Oct 06 2016

A277256 Multi-table menage numbers T(n,k) for n,k >= 1 equals the number of ways to seat the gentlemen from nk married couples at n round tables with 2k seats each such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other; provided that the ladies are already properly seated (i.e., no two ladies sit next to each other).

Original entry on oeis.org

0, 1, 0, 2, 4, 1, 9, 80, 82, 2, 44, 4752, 43390, 4740, 13, 265, 440192, 59216968, 59216648, 439794, 80, 1854, 59245120, 164806652728, 2649391488016, 164806435822, 59216644, 579, 14833, 10930514688, 817056761525488, 312400218967336992, 312400218673012936, 817056406224656, 10927434466, 4738

Offset: 1

Max Alekseyev, Oct 07 2016

			Table T(n,k):
  n=1:  0,      0,            1,                  2, ...
  n=2:  1,      4,           82,               4740, ...
  n=3:  2,     80,        43390,           59216648, ...
  n=4:  9,   4752,     59216968,      2649391488016, ...
  n=5: 44, 440192, 164806652728, 312400218967336992, ...
  ...

Cf. A000179 (row n=1), A000166 (column k=1), A000316 (column k=2), A277257, A277265, A341439.

{ A277256(n,k) = my(m,s,g); m=n*k; s=sqrt(1+4*x+O(x^(m+1))); g=if(k==1,1+z,((1-s)/2)^(2*k)+((1+s)/2)^(2*k))^n; sum(j=0,m,(-1)^j*polcoeff(g,j)*(m-j)!); }

T(n,k) = Sum_{j=0..n*k} (-1)^j * (n*k-j)! * [z^j] F(k,z)^n, where F(1,z) = 1+z and F(k,z) = ((1-sqrt(1+4*z))/2)^(2*k) + ((1+sqrt(1+4*z))/2)^(2*k) for k >= 2. [Corrected by Pontus von Brömssen, Jun 01 2022]

T(n,k) = A341439(n,n*k). - Pontus von Brömssen, May 31 2022

A337302 Number of X-based filling of diagonals in a diagonal Latin square of order n with the main diagonal in ascending order.

Original entry on oeis.org

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

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.

For all t > 0, a(2*t) = a(2*t+1).

			For n=4 there are 4 different X-based fillings of diagonals with main diagonal fixed to [0 1 2 3]:
   0 . . 1   0 . . 1   0 . . 2   0 . . 2
   . 1 0 .   . 1 3 .   . 1 0 .   . 1 3 .
   . 3 2 .   . 0 2 .   . 3 2 .   . 0 2 .
   2 . . 3   2 . . 3   1 . . 3   1 . . 3

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.
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, About the a(2*t)=a(2*t+1) equality (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, A309283, A274171, A337303.

a(n) = A337303(n)/n!.

a(n) = A000316(floor(n/2)). - Andrew Howroyd and Eduard I. Vatutin, Oct 08 2020

More terms from Alois P. Heinz, Oct 08 2020

a(0)=1 prepended by Andrew Howroyd, Oct 09 2020

A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange.

Original entry on oeis.org

1, 0, 4, 80, 4704, 436992, 58897920, 10880501760, 2640513576960, 814928486400000, 311763576754667520, 144816978675459686400, 80294888451877031116800, 52385405443881146567884800, 39727727942688305214337843200, 34656123210118214086941474816000

Offset: 0

Russell Y. Webb, Dec 25 2018

nonn

The sequence is the number of unique arrangements of directed graphs connecting 2*n vertices, where vertices occur in pairs, and meeting the following requirements:
1. Each vertex has an out-degree and in-degree of 1.
2. No edge connects vertices that are paired.
3. Starting with any pair, following the edges of paired vertices connects all vertices.
The requirements were chosen to yield a nice gift exchange between a set of couples. Acknowledgement to the additional members of the initial, inspirational gift exchange group: Cat, Brad, Kim, Ada, Graham, Nolan, and Leah.
The fraction of graphs meeting the requirements is approximately 0.12. Starting with n=2, the fractions are (0.166666667, 0.111111111, 0.116666667, 0.12042328, 0.122959756, 0.124807468). Is there a way to compute the percentage of graphs satisfying the condition in the limit as n approaches infinity?

			For n = 1, there is one pair; a(1) = 0 since requirements 1 and 2 can't be satisfied.
For n = 2, there are two pairs; a(2) = 4 graphs given by these edge destinations:
    ((2, 3), (1, 0))
    ((2, 3), (0, 1))
    ((3, 2), (1, 0))
    ((3, 2), (0, 1)).

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

A322750 does not allow reciprocal connections.
A010050 is the number of graphs (2n)!.
Cf. A000316, A003471.

\\ Here B(n) gives A003471 as vector.
B(n)={my(v=vector(n+1)); v[1]=1; for(n=4, n, my(m = 2-n%2); v[n+1] = v[n]*(n-1) + 2*(n-m)*v[n-2*m+1]); v}
seq(n)={my(v=B(2*n)); Vec(serlaplace(1+log(sum(k=0, n, v[1+2*k]*x^k/k!, O(x*x^n)))))} \\ Andrew Howroyd, Jan 13 2024

from itertools import permutations as perm
def num_connected_by_pairs(assigned, here=0, seen=None):
    seen = (seen, set())[seen is None]
    for proposed in [(here - 1, here), (here, here + 1)][(here % 2) == 0]:
        if proposed not in seen:
            seen.add(proposed)
            num_connected_by_pairs(assigned, assigned[proposed], seen)
    return len(seen)
def valid(assigned, pairs):
    self_give = [assigned[i] == i for i in range(len(assigned))]
    same_pair = [assigned[i] == i + 1 or assigned[i+1] == i for i in range(0, 2*pairs, 2)]
    if pairs == 0 or True in self_give + same_pair:
        return False
    num_connected = [num_connected_by_pairs(assigned, here) for here in range(2, 2*pairs, 2)]
    return min(num_connected) == 2*pairs
print([len([x for x in perm(range(2*pairs)) if valid(x, pairs)]) for pairs in range(0, 6)])

E.g.f.: 1 + log(B(x)) where B(x) is the e.g.f. of A000316. - Andrew Howroyd, Jan 13 2024

a(0) changed to 1 and a(8) onwards from Andrew Howroyd, Jan 13 2024

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

A137801 Number of arrangements of 2n couples into n cars such that each car contains 2 men and 2 women but no couple (cars are labeled).

Original entry on oeis.org

0, 6, 900, 748440, 1559930400, 6928346502000, 58160619655538400, 845986566719614320000, 19957466912796971445888000, 724891264860942581350908960000, 38873628093261330554954970801600000

Offset: 1

Max Alekseyev, Feb 10 2008

nonn

Proof of the formula (in Russian).

Cf. A094047, A137802.

{ a(n) = n! * sum(i=0,n, (-1)^i * sum(j=0,n-i, (2*n)! * (2*n-i-2*j)! / (n-i-j)! / i! / j! / 2^(2*n-2*i-j) ) ) }

a(n) = n! * A137802(n) = n! * SUM[i+j<=n] (-1)^i * (2n)! * (2n-i-2j)! / (n-i-j)! / i! / j! / 2^(2n-2i-j)

a(n) = A000459(n) * (2n)! / 2^n = A000316(n) * (2n)! / 4^n [From Max Alekseyev, Nov 03 2008]

A338084 Number of equivalence classes of X-based filling of diagonals in a diagonal Latin square of order 2n (or 2n+1).

Original entry on oeis.org

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

Offset: 0

Eduard I. Vatutin, Oct 08 2020

Supplemental for A309283.

The number of solutions in an equivalence class with the main diagonal in ascending order is at most 4*2^n*n!. This maximum is only achieved for n >= 5. - Andrew Howroyd, Mar 27 2023

			From _Andrew Howroyd_, Mar 27 2023: (Start)
For n = 5, the following is an example solution in an equivalence class of maximum size. The second square shows the effect of swapping the two diagonals and renumbering so that the main diagonal is still in ascending order.
   0 . . . . . . . . 1    0 . . . . . . . . 1
   . 1 . . . . . . 0 .    . 1 . . . . . . 0 .
   . . 2 . . . . 3 . .    . . 2 . . . . 3 . .
   . . . 3 . . 2 . . .    . . . 3 . . 2 . . .
   . . . . 4 6 . . . .    . . . . 4 9 . . . .
   . . . . 7 5 . . . .    . . . . 6 5 . . . .
   . . . 5 . . 6 . . .    . . . 4 . . 6 . . .
   . . 8 . . . . 7 . .    . . 5 . . . . 7 . .
   . 9 . . . . . . 8 .    . 7 . . . . . . 8 .
   4 . . . . . . . . 9    8 . . . . . . . . 9
(End)

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).

Cf. A000316, A309283.

a(n) >= A000316(n) / (4*2^n*n!). - Andrew Howroyd, Mar 27 2023

cp's OEIS Frontend

A123237 A000316-like neo-Hankel matrix determinant sequence.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A337302 Number of X-based filling of diagonals in a diagonal Latin square of order n with the main diagonal in ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

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

A137801 Number of arrangements of 2n couples into n cars such that each car contains 2 men and 2 women but no couple (cars are labeled).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A338084 Number of equivalence classes of X-based filling of diagonals in a diagonal Latin square of order 2n (or 2n+1).