cp's OEIS Frontend

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.

%I A326411 #38 Mar 01 2024 14:15:01
%S A326411 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,
%T A326411 91,49,14,0,1,177,544,740,640,302,96,20,0,1,1553,4500,6003,4725,2439,
%U A326411 747,165,27,0,1,14963,41740,53585,41420,20810,7076,1550,260,35,0,1
%N 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.
%C A326411 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
%C A326411 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.
%C A326411 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.
%H A326411 Andrew Howroyd, <a href="/A326411/b326411.txt">Table of n, a(n) for n = 0..1325</a> (rows 0..50; rows 0..17 from Witold Tatkiewicz)
%H A326411 P. Poulet, <a href="/A326411/a326411.pdf">Query 4750</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117)
%H A326411 P. Poulet, <a href="/A326411/a326411_1.pdf">Query 4750</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 118, 119)
%H A326411 P. Poulet, <a href="/A326411/a326411_2.pdf">Query 4750</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 120, 121)
%H A326411 Witold Tatkiewicz, <a href="https://pastebin.com/ZrBYiK9g">link for java program</a>.
%F A326411 It appears that Poulet gives recurrences that generate the whole triangle. - _N. J. A. Sloane_, Mar 09 2022
%F A326411 T(n,n) = 1;
%F A326411 T(n,n-1) = 0 for n >= 1;
%F A326411 T(n,n-2) = n*(n-3)/2 for n >= 4 [Poulet];
%F A326411 T(n,n-3) = n*(n-4)*(2*n-7)/3 for n >= 4 [Poulet, corrected by _N. J. A. Sloane_, Mar 09 2022]
%F A326411 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]
%F A326411 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]
%F A326411 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]
%e A326411 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.
%e A326411 Unfolded table with n individuals (rows) forming k pairs (columns):
%e A326411     0    1    2    3    4    5    6    7
%e A326411 0   1
%e A326411 1   0    1
%e A326411 2   0    0    1
%e A326411 3   0    0    0    1
%e A326411 4   0    0    2    0    1
%e A326411 5   1    0    5    5    0    1
%e A326411 6   3   12   15   20    9    0   1
%e A326411 7  23   70  112   91   49   14   0   1
%p A326411 A326411 := proc(n,k)
%p A326411     option remember;
%p A326411     if k > n or k < 0 then
%p A326411         0;
%p A326411     elif k = n then
%p A326411         1;
%p A326411     elif k =0 then
%p A326411         if n < 5 then
%p A326411             0 ;
%p A326411         elif n = 5 then
%p A326411             1 ;
%p A326411         elif n = 6 then
%p A326411             3 ;
%p A326411         elif n = 7 then
%p A326411             23 ;
%p A326411         else
%p A326411             # Poulet eq (6) page 120, shifted n->n-2
%p A326411             -(n^3-8*n^2+18*n-21)*procname(n-1,0)
%p A326411             -4*(n^2-5*n)*procname(n-2,0)
%p A326411             +2*(n^3-11*n^2+33*n-18)*procname(n-3,0)
%p A326411             -(n^2-7*n+9)*procname(n-4,0)
%p A326411             -(n^3-10*n^2+28*n-15)*procname(n-5,0) ;
%p A326411             -%/(n^2-7*n+9) ;
%p A326411         end if;
%p A326411     elif n <= 3 then
%p A326411         0;
%p A326411     else
%p A326411         # Poulet eq (3) page 119
%p A326411         2*(n-k)*procname(n-1,k-1)/(n-1)+2*k*procname(n-1,k)/(n-1)
%p A326411             +(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) ;
%p A326411         %*n/k ;
%p A326411     end if;
%p A326411 end proc:
%p A326411 for n from 0 to 12 do
%p A326411     for k from 0 to n do
%p A326411         printf("%a ",A326411(n,k)) ;
%p A326411     end do:
%p A326411     printf("\n") ;
%p A326411 end do: # _R. J. Mathar_, Mar 17 2022
%t A326411 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,
%t A326411     pc = -(n^3 - 8*n^2 + 18*n - 21)*T[n-1, 0]
%t A326411       - 4*(n^2 - 5*n)*T[n - 2, 0]
%t A326411       + 2*(n^3 - 11*n^2 + 33*n - 18)*T[n-3, 0]
%t A326411       - (n^2 - 7*n + 9)*T[n-4, 0]
%t A326411       - (n^3 - 10*n^2 + 28*n - 15)*T[n-5, 0];
%t A326411     -pc/(n^2 - 7*n + 9)], n <= 3, 0, True,
%t A326411    pc = 2*(n-k)*T[n-1, k-1]/(n-1) + 2*k*T[n-1, k]/(n-1) +
%t A326411      (k - 2)*T[n-2, k-2]/(n-2) -
%t A326411      2*(k-1)*T[n-2, k-1]/(n-2) + k*T[n-2, k]/(n-2);
%t A326411     pc*n/k];
%t A326411 Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Mar 17 2023, after _R. J. Mathar_ *)
%o A326411 (Java) See Links section
%o A326411 (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)}
%o A326411 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
%Y A326411 Cf. A002816 (column k=0).
%Y A326411 Row sums: A001710(n-1) = Sum_k T(n,k).
%Y A326411 Cf. also A326390 (accounting for rotation and reflection symmetry), A326397 (disregards reflection symmetry but allows rotation), A326407 (disregards rotation symmetry but allows reflection).
%Y A326411 See in addition A002464.
%K A326411 nonn,tabl
%O A326411 0,13
%A A326411 _Witold Tatkiewicz_, Aug 07 2019