login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326411 Triangle T(n,k) read by rows: T(n,k) = the number of ways of seating n people around a table for the second time so that k pairs are maintained. Reflected and rotated sequences are counted as one. 8
1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 5, 5, 0, 1, 3, 12, 15, 20, 9, 0, 1, 23, 70, 112, 91, 49, 14, 0, 1, 177, 544, 740, 640, 302, 96, 20, 0, 1, 1553, 4500, 6003, 4725, 2439, 747, 165, 27, 0, 1, 14963, 41740, 53585, 41420, 20810, 7076, 1550, 260, 35, 0, 1 (list; table; graph; refs; listen; history; text; internal format)
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
Cf. A002816 (column k=0).
Row sums: A001710(n-1) = Sum_k T(n,k).
Cf. also A326390 (accounting for rotation and reflection symmetry), A326397 (disregards reflection symmetry but allows rotation), A326407 (disregards rotation symmetry but allows reflection).
See in addition A002464.
Sequence in context: A185249 A075107 A269953 * A348454 A348452 A309163
KEYWORD
nonn,tabl
AUTHOR
Witold Tatkiewicz, Aug 07 2019
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 07:27 EDT 2024. Contains 371265 sequences. (Running on oeis4.)