A326411 -id:A326411 - cp's OEIS frontend

A002464 Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

1, 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, 831283558, 11661506218, 175203184374, 2806878055610, 47767457130566, 860568917787402, 16362838542699862, 327460573946510746, 6880329406055690790, 151436547414562736234, 3484423186862152966838

Offset: 0

N. J. A. Sloane

Permutations of 12...n such that none of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).
This sequence is also the solution to the 'toast problem' devised by my house-mates and me as math undergraduates some 27 years ago: Given a toast rack with n slots, how many ways can the slices be removed so that no two consecutive slices are removed from adjacent slots? - David Jones (david.jones(AT)zetnet.co.uk), Oct 24 2003
This sequence was also derived by the late D. P. Robbins. - David Callan, Nov 04 2003
Another interpretation: number of permutations of n containing exactly n different patterns of size n-1. - Olivier Gérard, Nov 05 2007
Number of directed Hamiltonian paths in the complement of the n-path graph P_n. - Andrew Howroyd, Mar 16 2016
There is an obvious connection between the two descriptions of the sequence: Replace the chessboard with a n X n zero-matrix and each king with "1". This matrix will transform the vector (1,2,..,n) into a permutation such that adjacent components do not differ by 1. The reverse is also true: Any such transformation is a solution of the king problem. - Gerhard Kirchner, Feb 10 2017
A formula of Poulet (1919) relates this to A326411: a(n) = T(n+2,1)/(n+2) + 2*T(n+1,1)/(n+1) + T(n,1)/n, where T(i,j) = A326411(i,j). - N. J. A. Sloane, Mar 08 2022
For the number of these permutations without fixed points see A288208. - Wolfdieter Lang, May 22 2025

			a(4) = 2: 2413, 3142.
a(5) = 14 corresponds to these 14 permutations of length 5: 13524, 14253, 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142.

W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.

N. J. A. Sloane, Table of n, a(n) for n = 0..500
M. Abramson and W. O. J. Moser, Permutations without rising or falling w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254.
W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.
Another Roof, A Lifelong Mathematical Obsession, YouTube video, 2023.
Art of Problem Solving Forum, Number of permutative
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, On the poset of King-Non-Attacking permutations, arXiv:1905.02387 [math.CO], 2019.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Counting King Permutations on the Cylinder, arXiv:2001.02948 [math.CO], 2020.
Christoph Bärligea, On the dimension of the Fomin-Kirillov algebra and related algebras, arXiv:2001.04597 [math.QA], 2020.
Robert Brignall, Vít Jelínek, Jan Kynčl, and David Marchant, Zeros of the Möbius function of permutations, arXiv:1810.05449 [math.CO], 2018.
Doug Chatham, Independence and domination on shogiboard graphs, Recreational Mathematics Magazine 4.8 (2017), pp. 25-37.
Doug Chatham, Reflections on the n+k dragon kings problem, Games and Puzzles, Recreational Mathematics Magazine (2018) 5.10, 39-55.
Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373.
Sela Fried, Further results on staircase (cyclic) words, arXiv:2501.11991 [math.CO], 2025. See p. 12.
Sela Fried, Toufik Mansour, and Mark Shattuck, Counting k-ary words by number of adjacency differences of a prescribed size, arXiv:2504.03013 [math.CO], 2025. See p. 2.
Michael Han, Tanya Khovanova, Ella Kim, Evin Liang, Miriam Lubashev, Oleg Polin, Vaibhav Rastogi, Benjamin Taycher, Ada Tsui and Cindy Wei, Fun with Latin Squares, arXiv:2109.01530 [math.HO], 2021.
C. Homberger, Counting Fixed Length Permutation Patterns, Online Journal of Analytic Combinatorics, 7 (2012).
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
Mark Huibregtse, Cristobal Lemus-Vidales, and David Vella, Bootstrap Percolation, Indecomposable Permutations, and the n-Kings problem, arXiv:2508.02030 [math.CO], 2025. See p. 2.
Irving Kaplansky, The asymptotic distribution of runs of consecutive elements, Ann. Math. Statistics, 16 (1945), 200-203
Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], (2013).
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 625-635.
Igor Minevich, Gabe Cunningham, Aditya Karan, and Joshua V. Gyllinsky, Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464, arXiv:2411.02251 [cs.CC], 2024.
O. Patashnik and P. Flajolet, Email to N. J. A. Sloane, Nov 26 1989
P. Poulet, Query 4750: Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117)
P. Poulet, Query 4750: Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 118, 119)
P. Poulet, Query 4750: Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 120, 121)
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.
Josef Rukavicka, Secretary problem and two almost the same consecutive applicants, arXiv:2106.11244 [math.PR], 2021.
A. J. Schwenk, Letter to N. J. A. Sloane, Mar 24 1980 (with enclosure and notes)
L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schroeder problems and the n-kings problem, SIAM J. Discrete Math., 4 (1991), 275-280.
Jason P. Smith, A Formula for the Mobius function of the Permutation Poset Based on a Topological Decomposition, arXiv preprint arXiv:1506.04406 [math.CO], 2015.
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. See Column 3 in the table on page 3.
B. E. Tenner, Mesh patterns with superfluous mesh, arXiv preprint arXiv:1302.1883 [math.CO], 2013.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Path Complement Graph
Eric Weisstein's World of Mathematics, Permutation

Equals 2*A001266(n) for n >= 2. A diagonal of A001100. Cf. A010028.
Cf. A086852, A086853, A086854, A086855, A000130, A000349, A001267, A001268, A010028, A002493.
Cf. A089222, A104698, A288208.
Column k=1 of A333706.

A002464 := proc(n) options remember; if n <= 1 then 1 elif n <= 3 then 0 else (n+1)*A002464(n-1)-(n-2)*A002464(n-2)-(n-5)*A002464(n-3)+(n-3)*A002464(n-4); fi; end;

(* computation from the permutation class *)
g[ L_ ] := Apply[ And, Map[ #>1&, L ] ]; f[ n_ ] := Length[ Select[ Permutations[ Range[ n ] ], g[ Rest[ Abs[ RotateRight[ # ]-# ] ] ]& ] ]; Table[ f[ n ], {n, 1, 8} ] (* Erich Friedman *)
(* or direct computation of terms *)
Table[n! + Sum[(-1)^r*(n-r)!*Sum[2^c *Binomial[r-1,c-1] *Binomial[n-r,c], {c,1,r}], {r,1,n-1}], {n,1,30}] (* Vaclav Kotesovec, Mar 28 2011 *)
(* or from g.f. *)
M = 30; CoefficientList[Sum[n!*x^n*(1-x)^n/(1+x)^n, {n, 0, M}] + O[x]^M, x] (* Jean-François Alcover, Jul 07 2015 *)
CoefficientList[Series[Exp[(1 + x)/((-1 + x) x)] (1 + x) Gamma[0, (1 + x)/((-1 + x) x)]/((-1 + x) x), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 11 2018 *)
RecurrenceTable[{a[n] == (n + 1) a[n - 1] - (n - 2) a[n - 2] - (n - 5) a[n - 3] + (n - 3) a[n - 4], a[0] == a[1] == 1, a[2] == a[3] == 0}, a, {n, 0, 20}] (* Eric W. Weisstein, Apr 11 2018 *)

N = 66;  x = 'x + O('x^N);
gf = sum(n=0,N, n!*(x*(1-x))^n/(1+x)^n );
v = Vec(gf) /* Joerg Arndt, Apr 17 2013 */

from math import factorial, comb
def A002464(n): return factorial(n)+sum((-1 if k&1 else 1)*factorial(n-k)*sum(comb(k-1,t-1)*comb(n-k,t)<Chai Wah Wu, Feb 19 2024

If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).
G.f.: Sum_{n >= 0} n!*x^n*(1-x)^n/(1+x)^n. - Philippe Flajolet
G.f.: e^((1 + x)/((-1 + x) * x)) * (1 + x) * Gamma(0, (1 + x)/((-1 + x) * x))/((-1 + x) * x). - Eric W. Weisstein, May 16 2014
Let S_{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} S_{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; for n >= 4, S[n] = (n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4].
a(n) = n! + Sum_{k=1..n} (-1)^k * Sum_{t=1..k} binomial(k-1,t-1) * binomial(n-k,t) * 2^t * (n-k)!. - Max Alekseyev, Jan 29 2006
a(n) = Sum_{k=0..n} (-1)^(n-k)*k!*b(n,k), where g.f. for b(n,k) is (1-x)/(1-(1+y)*x-y*x^2), cf. A035607. - Vladeta Jovovic, Nov 24 2007
Asymptotic (M. Abramson and W. Moser, 1966): a(n)/n! ~ (1 - 2/n^2 - 10/(3*n^3) - 6/n^4 - 154/(15*n^5) - 88/(9*n^6) + 5336/(105*n^7) + 1612/(3*n^8) + 2098234/(567*n^9) + 36500686/(1575*n^10) + ... )/e^2. - Vaclav Kotesovec, Apr 19 2011, extended Dec 27 2020
Conjecture: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. - John Keith, Nov 02 2020
Proof: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. Since a(n) = Sum_{k=0..n-1} (-1)^k*(n-k)!*Sum_{i=0..k} binomial(n-k,i)*binomial(n-1-i,k-i) (M. Abramson and W. Moser, 1966) which is Sum_{k=1..n} (-1)^(k-1)(n-k+1)!*Sum{i=0..k-1} binomial(n-k+1,i)*binomial(n-1-i,k-1-i) = Sum_{k=1..n} (-1)^(n-k)(k!)*Sum_{i=0..n-k} binomial(k,i)*binomial(n-1-i,n-k-i) = k!*A080246(n-1, k-1) as (-1)^(n-k) = (-1)^(n+k) and binomial(n-1-i,k-1) = binomial(n-1-i,n-k-i). - Alex McGaw, Apr 13 2023
a(n+2) = (n+2)! - Sum_{j=0..n} (-1)^j*(n+1-j)!*2*A104698(n, j), for n >= 0 (Abramson and Moser, p. 1250, (III), N_0(n+2), last line, rewritten). - Wolfdieter Lang, May 14 2025

Merged with the old A001100, Aug 19 2003
Kaplansky reference from David Callan, Oct 29 2003
Tauraso reference from Parthasarathy Nambi, Dec 21 2006
Edited by Jon E. Schoenfield, Jan 31 2015

A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.

Original entry on oeis.org

1, 0, 0, 0, 1, 3, 23, 177, 1553, 14963, 157931, 1814453, 22566237, 302267423, 4340478951, 66541218865, 1084982173641, 18752743351339, 342523093859011, 6593167693927885, 133408305489947029, 2831112931136162775, 62878579846490149375, 1458746608689369440265

Offset: 1

N. J. A. Sloane

Also number of ways of arranging the numbers 1..n in a circle so that adjacent numbers do not differ by 1 mod n. Reversing the direction around the circle does not count as a different solution (cf. A078603).
Also number of ways of seating n people around a circular table so that no one sits next to any of his neighbors in a previous seating order.
Suppose n people are seated at random around a circular table for two meals. Then p(n) = a(n)/((n-1)!/2) is the probability that no two people sit together at both meals.
Number of Hamiltonian cycles in the complement of C_n where C_n is the n-cycle graph. - Andrew Howroyd, Mar 15 2016

			a(6)=3: 135264, 136425, 142635.

P. Poulet, Reply to Query 4750, Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121.
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 = 1..100
B. Aspvall and F. M. Liang, The dinner table problem, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.
Eric Weisstein's World of Mathematics, Cycle Complement Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Index entries for sequences related to shoe lacings

Cf. A000179 (Ménage problem), A078603, A078630, A078631, A242522 (Hamiltonian cycles in complement of path), A006184, left column of A326411.

dinner := proc(n) local j,k,sum; sum := (n-1)!/2 + (-1)^n; for k from 1 to n-1 do for j from 1 to min(n-k,k) do sum := sum+(-1)^k*binomial(k-1,j-1)*binomial(n-k,j)*n/(n-k)*(n-k-1)!/2*2^j; od; od; end;

t = {1, 0, 0, 0, 1, 3, 23}; Do[AppendTo[t, ((n^3 - 8*n^2 + 18*n - 21) t[[-1]] + 4*n*(n - 5) t[[-2]] - 2*(n - 6) (n^2 - 5 n + 3) t[[-3]] + (n^2 - 7*n + 9)  t[[-4]] + (n - 5) (n^2 - 5*n + 3) t[[-5]])/(n^2 - 7*n + 9)], {n, 8, 25}]; t (* T. D. Noe, Jan 04 2012 *)
Join[{1, 0}, RecurrenceTable[{a[3] == 0, a[4] == 0, a[5] == 1, a[6] == 3, a[7] == 23, (n^2 - 7 n + 9) a[n] == (n^3 - 8 n^2 + 18 n - 21) a[n - 1] + 4 n (n - 5) a[n - 2] - 2 (n - 6) (n^2 - 5 n + 3) a[n - 3] + (n^2 - 7 n + 9) a[n - 4] + (n - 5) (n^2 - 5 n + 3) a[n - 5]}, a, {n, 3, 20}]] (* Eric W. Weisstein, Feb 26 2021 *)

D-finite with recurrence (n^2 - 7n + 9)a(n) = (n^3 - 8n^2 + 18n - 21)a(n - 1) + 4n(n - 5)a(n - 2) - 2(n - 6)(n^2 - 5n + 3)a(n - 3) + (n^2 - 7n + 9)a(n - 4) + (n - 5)(n^2 - 5n + 3)a(n - 5), for n >= 8. - Poulet.
p(n) = exp(-2)*(1 + O(1/n)). - Aspvall and Liang.
Asymptotic: a(n)/(n-1)! ~ 1/(2*e^2)*(1 - 4/n + 20/(3n^3) + 58/(3n^4) + 796/(15n^5) + 7858/(45n^6) + 40324/(63n^7) + 140194/(63n^8) + 2444744/(405n^9) + 40680494/(14175n^10) + ...). - Vaclav Kotesovec, Apr 10 2012

Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001

More terms from Sascha Kurz, Mar 22 2002

A231091 Number of distinct (modulo rotation) unicursal star polygons (not necessarily regular, no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 5, 27, 175, 1533, 14361, 151575, 1735869, 21594863, 289365383, 4158887007, 63822480809, 1041820050629, 18027531255745, 329658402237171, 6352776451924233, 128686951765990343, 2733851297673484765, 60781108703102022027, 1411481990523638719737

Offset: 1

Stewart Gordon, Nov 03 2013

For polygons in general see A000939 and A000949, and especially the Golomb-Welch reference. - N. J. A. Sloane, Nov 21 2013

			For n=5, only solution is the regular pentagram.
For n=6, only solution is the unicursal hexagram (see Wikipedia link).
For n=7, two regular heptagrams and three irregular forms are possible.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Stewart Gordon, The five possible stars for n=7 (SVG file)
Wikipedia, Unicursal hexagram

Cf. A000939 (if edges may join adjacent vertices), A000940, A002816 (rotations and reflections counted separately), A326411, A370459 (up to rotations and reflections), A370068 (directed edges).

Cf. A283184.

\\ Requires a370068 from A370068, b(n) is A283184.
b(n)={subst(serlaplace(polcoef((1 - x)/(1 + (1 - 2*y)*x + 2*y*x^2) + O(x*x^n), n)), y, 1)}
a(n)={(if(n%2==0 && n > 2, b(n/2-1)/2) + a370068(n))/2} \\ Andrew Howroyd, Mar 01 2024

a(n) = (A370068(n) + A283184(n/2-1)/2)/2 for even n >= 4; a(n) = A370068(n)/2 for odd n. - Andrew Howroyd, Feb 24 2024

a(15) onwards from Andrew Howroyd, Feb 23 2024

A326390 The number of ways of seating n people around a table for the second time so that k pairs are maintained. T(n,k) read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 0, 6, 0, 0, 16, 0, 8, 10, 0, 50, 50, 0, 10, 36, 144, 180, 240, 108, 0, 12, 322, 980, 1568, 1274, 686, 196, 0, 14, 2832, 8704, 11840, 10240, 4832, 1536, 320, 0, 16, 27954, 81000, 108054, 85050, 43902, 13446, 2970, 486, 0, 18, 299260, 834800, 1071700, 828400, 416200, 141520, 31000, 5200, 700, 0, 20

Offset: 0

Witold Tatkiewicz, Jul 03 2019

Definition requires "pairs" and for n=0 it is assumed that there is 1 way of seating 0 people around a table for the second time so that 0 pairs are maintained and 1 person forms only one pair with him/herself. Therefore T(0,0)=1, T(1,0)=0 and T(1,1)=1.
Sum of each row is equal to n!.
Weighted average of each row using k as weights converges to 2 for large n and is given with following formula: (Sum_{k} T(n,k)*k)/n! = 2/(n-1) + 2 (conjectured).

			Assuming initial order was {1,2,3,4,5} (therefore 1 and 5 forms pair as first and last person are neighbors in case of round table) there are 5 sets of ways of seating them again so that 3 pairs are conserved: {1,2,3,5,4}, {2,3,4,1,5}, {3,4,5,2,1}, {4,5,1,3,2}, {5,1,2,4,3}. Since within each set we allow for rotation ({1,2,3,5,4} and {2,3,5,4,1} are different) and reflection ({1,2,3,5,4} and {4,5,3,2,1} are also different) the total number of ways is 5*2*5 and therefore T(5,3)=50.
Unfolded table with n individuals (rows) forming k pairs (columns):
    0    1    2    3    4    5    6    7
0   1
1   0    1
2   0    0    2
3   0    0    0    6
4   0    0   16    0    8
5  10    0   50   50    0   10
6  36  144  180  240  108    0   12
7 322  980 1568 1274  686  196    0   14

Witold Tatkiewicz, Rows n = 0..17 of triangle, flattened
Witold Tatkiewicz, Link for Java program

Cf. A089222 (column k=0).
Cf. A000142 sum of each row.
Cf. A326397 (disregards reflection symmetry), A326404 (disregards circular symmetry), A326411 (disregards both circular and reflection symmetry).

Java
```
See Links section
```

T(n,n) = 2*n for n > 2;
T(n,n-1) = 0 for n > 1;
T(n,n-2) = n^2*(n-3) for n > 3 (conjectured);
T(n,n-3) = (3/4)*n^4 + 6*n^3 + (2/3)*n^2 - 14*n + 6 for n > 4 (conjectured);
T(n,n-4) = (25/12)*n^5 + (73/6)*n^4 + (5/4)*n^3 - (253/6)*n^2 + (152/3)*n - 24 for n > 5 (conjectured);
T(n,n-5) = (52/15)*n^6 + (77/3)*n^5 + 14*n^4 - (194/3)*n^3 + (4628/15)*n^2 - 273*n + 130 for n > 5 (conjectured);
T(n,n-6) = (707/120)*n^7 + (2093/40)*n^6 + (2009/40)*n^5 - (245/8)*n^4 + (78269/60)*n^3 - (18477/10)*n^2 + (21294/10)*n - 684 for n > 6 (conjectured).

A326397 Triangle T(n,k) read by rows: T(n,k) = number of ways of seating n people around a table for the second time so that k pairs are maintained. Reflected sequences are counted as one.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 0, 3, 0, 0, 8, 0, 4, 5, 0, 25, 25, 0, 5, 18, 72, 90, 120, 54, 0, 6, 161, 490, 784, 637, 343, 98, 0, 7, 1416, 4352, 5920, 5120, 2416, 768, 160, 0, 8, 13977, 40500, 54027, 42525, 21951, 6723, 1485, 243, 0, 9, 149630, 417400, 535850, 414200, 208100, 70760, 15500, 2600, 350, 0, 10, 1737241, 4691654

Offset: 0

Witold Tatkiewicz, Aug 01 2019

Definition requires "pairs" and for n=0 it is assumed that there is 1 way of seating 0 people around a table for the second time so that 0 pairs are maintained and 1 person forms only one pair with him/herself. Therefore T(0,0)=1, T(1,0)=0 and T(1,1)=1.

Weighted average of each row using k as weights converges to 2 for large n and is given by the following formula: (Sum_{k} T(n,k)*k)/(Sum_{k} T(n,k)) = 2/(n-1) + 2 (conjectured).

			Assuming the initial order was {1,2,3,4,5} (therefore 1 and 5 form a pair as first and last person are neighbors in case of round table) there are 5 sets of ways of seating them again so that 3 pairs are conserved: {1,2,3,5,4}, {2,3,4,1,5}, {3,4,5,2,1}, {4,5,1,3,2}, {5,1,2,4,3}. Since within each set we allow for rotation ({1,2,3,5,4} and {2,3,5,4,1} are different) but not reflection ({1,2,3,5,4} and {4,5,3,2,1} are counted as one sequence) the total number of ways is 5*5 and therefore T(5,3)=25.
Unfolded table with n individuals (rows) forming k pairs (columns):
    0    1    2    3    4    5    6    7
0   1
1   0    1
2   0    0    1
3   0    0    0    3
4   0    0    8    0    4
5   5    0   25   25    0    5
6  18   72   90  120   54    0   6
7 161  490  784  637  343   98   0   7

Witold Tatkiewicz, Rows n = 0..17 of triangle, flattened
Witold Tatkiewicz, link for java program

Cf. A001710 sum of each row.

Cf. A326390 (with reflection symmetry), A326404 (with reflection symmetry, but disregards circular symmetry), A326411 (disregards both circular and reflection symmetry).

Java
```
See Links section.
```

T(n,n) = n for n>2.
T(n,n-1) = 0 for n>1.
T(n,n-3) = 1/2*n^3 + 3/4*n^2 - 2 (conjectured);
T(n,n-3) = (2/3)*n^4 + 3*n^3 + (1/3)*n^2 - 7*n + 3 for n > 4 (conjectured);
T(n,n-4) = (25/24)*n^5 + (73/12)*n^4 + (5/8)*n^3 - (253/12)*n^2 + (76/3)*n - 12 for n > 5 (conjectured);
T(n,n-5) = (26/15)*n^6 + (77/6)*n^5 + 7*n^4 - (97/3)*n^3 + (2314/15)*n^2 - 273/2*n + 65 for n > 5 (conjectured);
T(n,n-6) = (707/240)*n^7 + (2093/80)*n^6 + (2009/80)*n^5 - (245/16)*n^4 + (78269/120)*n^3 - (18477/20)*n^2 + (10647/0)*n - 342 for n > 6 (conjectured).

A326404 Triangle T(n,k) read by rows: T(n,k) = number of ways of seating n people around a table for the second time so that k pairs are maintained. Rotated sequences are counted as one.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 4, 0, 2, 2, 0, 10, 10, 0, 2, 6, 24, 30, 40, 18, 0, 2, 46, 140, 224, 182, 98, 28, 0, 2, 354, 1088, 1480, 1280, 604, 192, 40, 0, 2, 3106, 9000, 12006, 9450, 4878, 1494, 330, 54, 0, 2, 29926, 83480, 107170, 82840, 41620, 14152, 3100, 520, 70, 0, 2

Offset: 0

Witold Tatkiewicz, Aug 01 2019

Definition requires "pairs" and for n=0 it is assumed that there is 1 way of seating 0 people around a table for the second time so that 0 pairs are maintained and 1 person forms only one pair with him/herself. Therefore T(0,0)=1, T(1,0)=0 and T(1,1)=1.
Sum of row n is equal to (n-1)! for n > 1.
Conjecture: The weighted average of each row using k as weights converges to 2 for large n and is given by the following formula: (Sum_{k} T(n,k)*k)/(Sum_{k} T(n,k)) = 2/(n-1) + 2.

			Assuming the initial order was {1,2,3,4,5} (therefore 1 and 5 form a pair as the first and last persons are neighbors in the case of a round table) there are 5 sets of ways of seating them again so that 3 pairs are conserved: {1,2,3,5,4}, {2,3,4,1,5}, {3,4,5,2,1}, {4,5,1,3,2}, {5,1,2,4,3}. Since within each set we do not allow for circular symmetry (e.g., {1,2,3,5,4} and its rotation to form {2,3,5,4,1} are counted as one) but we allow reflection ({1,2,3,5,4} and {4,5,3,2,1} are considered distinct), the total number of ways is 5*2 and therefore T(5,3)=10.
Unfolded table with n individuals (rows) forming k pairs (columns):
    0    1    2    3    4    5    6    7
0   1
1   0    1
2   0    0    1
3   0    0    0    2
4   0    0    4    0    2
5   2    0   10   10    0    2
6   6   24   30   40   18    0    2
7  46  140  224  182   98   28    0    2

Witold Tatkiewicz, Rows n = 0..17 of triangle, flattened
Witold Tatkiewicz, Link for Java program.

Cf. A078603 (column k=0).
Sum of n-th row is A000142(n-1) for n > 0.
Cf. A326390 (accounting for rotation and reflection symmetry), A326397 (disregards reflection symmetry but allows rotation), A326411 (disregards both reflection and rotation symmetry).

Java
```
See Links section
```

T(n,n) = 2 for n > 2;
T(n,n-1) = 0 for n > 1.
Conjectures:
T(n,n-2) = n^2 + n - 2 for n > 3;
T(n,n-3) = (4/3)*n^3 + 2*n^2 - (16/3)*n + 2 for n > 4;
T(n,n-4) = (25/12)*n^4 + (23/6)*n^3 - (169/12)*n^2 + (85/6)*n - 6 for n > 5;
T(n,n-5) = (52/15)*n^5 + (25/3)*n^4 - (83/3)*n^3 + (221/3)*n^2 - (299/5)*n + 26 for n > 5;
T(n,n-6) = (707/120)*n^6 + (2037/120)*n^5 - (413/8)*n^4 + (2233/8)*n^3 - (5554/15)*n^2 + (3739/10)*n - 114 for n > 6.

cp's OEIS Frontend

A002464 Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A231091 Number of distinct (modulo rotation) unicursal star polygons (not necessarily regular, no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A326390 The number of ways of seating n people around a table for the second time so that k pairs are maintained. T(n,k) read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Formula

A326397 Triangle T(n,k) read by rows: T(n,k) = number of ways of seating n people around a table for the second time so that k pairs are maintained. Reflected sequences are counted as one.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Formula

A326404 Triangle T(n,k) read by rows: T(n,k) = number of ways of seating n people around a table for the second time so that k pairs are maintained. Rotated sequences are counted as one.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Formula

A370068 Number of nonequivalent directed unicursal star polygons (no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon up to rotations.

Views

Author

Keywords