OFFSET
0,13
COMMENTS
Poulet (1919) arrives at this triangle of numbers by considering n-sided polygons whose vertices lie on a circle. Call a side of such a polygon simple if its endpoints are adjacent on the circle. Then T(n,k) is the number of such polygons with k simple sides. There is also a connection with A002464 (see that entry). - N. J. A. Sloane, Mar 08 2022
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.
The weighted average of each row using k as weights converges to 2 for large n and appears to be given by (Sum_{k} k*T(n,k))/n! = 2/(n-1) + 2.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50; rows 0..17 from Witold Tatkiewicz)
P. Poulet, Query 4750, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117)
P. Poulet, Query 4750, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 118, 119)
P. Poulet, Query 4750, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 120, 121)
Witold Tatkiewicz, link for java program.
FORMULA
It appears that Poulet gives recurrences that generate the whole triangle. - N. J. A. Sloane, Mar 09 2022
T(n,n) = 1;
T(n,n-1) = 0 for n >= 1;
T(n,n-2) = n*(n-3)/2 for n >= 4 [Poulet];
T(n,n-3) = n*(n-4)*(2*n-7)/3 for n >= 4 [Poulet, corrected by N. J. A. Sloane, Mar 09 2022]
T(n,n-4) = (25/24)*n^4 + (23/12)*n^3 - (169/24)*n^2 + (85/12)*n - 3 for n > 5 (conjectured); [see Poulet]
T(n,n-5) = (26/15)*n^5 + (25/6)*n^4 - (83/6)*n^3 + (221/6)*n^2 - (299/10)*n + 13 for n > 5 (conjectured); [see Poulet]
T(n,n-6) = (707/240)*n^6 + (2037/240)*n^5 - (413/16)*n^4 + (2233/16)*n^3 - (2777/15)*n^2 + (3739/20)*n - 57 for n > 6 (conjectured). [See Poulet]
EXAMPLE
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) nor reflection ({1,2,3,5,4} and {4,5,3,2,1} are also counted as one), the total number of ways is 5 and therefore T(5,3)=5.
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 1
4 0 0 2 0 1
5 1 0 5 5 0 1
6 3 12 15 20 9 0 1
7 23 70 112 91 49 14 0 1
MAPLE
A326411 := proc(n, k)
option remember;
if k > n or k < 0 then
0;
elif k = n then
1;
elif k =0 then
if n < 5 then
0 ;
elif n = 5 then
1 ;
elif n = 6 then
3 ;
elif n = 7 then
23 ;
else
# Poulet eq (6) page 120, shifted n->n-2
-(n^3-8*n^2+18*n-21)*procname(n-1, 0)
-4*(n^2-5*n)*procname(n-2, 0)
+2*(n^3-11*n^2+33*n-18)*procname(n-3, 0)
-(n^2-7*n+9)*procname(n-4, 0)
-(n^3-10*n^2+28*n-15)*procname(n-5, 0) ;
-%/(n^2-7*n+9) ;
end if;
elif n <= 3 then
0;
else
# Poulet eq (3) page 119
2*(n-k)*procname(n-1, k-1)/(n-1)+2*k*procname(n-1, k)/(n-1)
+(k-2)*procname(n-2, k-2)/(n-2) - 2*(k-1)*procname(n-2, k-1)/(n-2) + k*procname(n-2, k)/(n-2) ;
%*n/k ;
end if;
end proc:
for n from 0 to 12 do
for k from 0 to n do
printf("%a ", A326411(n, k)) ;
end do:
printf("\n") ;
end do: # R. J. Mathar, Mar 17 2022
MATHEMATICA
T[n_, k_] := T[n, k] = Which[k > n || k < 0, 0, k == n, 1, k == 0, Which[n<5, 0, n == 5, 1, n == 6, 3, n == 7, 23, True,
pc = -(n^3 - 8*n^2 + 18*n - 21)*T[n-1, 0]
- 4*(n^2 - 5*n)*T[n - 2, 0]
+ 2*(n^3 - 11*n^2 + 33*n - 18)*T[n-3, 0]
- (n^2 - 7*n + 9)*T[n-4, 0]
- (n^3 - 10*n^2 + 28*n - 15)*T[n-5, 0];
-pc/(n^2 - 7*n + 9)], n <= 3, 0, True,
pc = 2*(n-k)*T[n-1, k-1]/(n-1) + 2*k*T[n-1, k]/(n-1) +
(k - 2)*T[n-2, k-2]/(n-2) -
2*(k-1)*T[n-2, k-1]/(n-2) + k*T[n-2, k]/(n-2);
pc*n/k];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 17 2023, after R. J. Mathar *)
PROG
(Java) See Links section
(PARI) Q(n, k)={k*subst(serlaplace(polcoef((1 - 2*x -x^2)/((1 + x)*(1 + (1 - y)*x + y*x^2)) + O(x^n), n-1)), y, k)}
row(n)={Vec(if(n<3, 1, (Q(n, y/(y-1))/2 + (-1)^n)*(y-1)^n), -n-1)} \\ Andrew Howroyd, Mar 01 2024
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Witold Tatkiewicz, Aug 07 2019
STATUS
approved