A326411 - OEIS

%I #38 Mar 01 2024 14:15:01

%S 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 91,49,14,0,1,177,544,740,640,302,96,20,0,1,1553,4500,6003,4725,2439,

%U 747,165,27,0,1,14963,41740,53585,41420,20810,7076,1550,260,35,0,1

%N 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 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 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 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 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 P. Poulet, <a href="/A326411/a326411.pdf">Query 4750</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117)

%H 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 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 Witold Tatkiewicz, <a href="https://pastebin.com/ZrBYiK9g">link for java program</a>.

%F It appears that Poulet gives recurrences that generate the whole triangle. - _N. J. A. Sloane_, Mar 09 2022

%F T(n,n) = 1;

%F T(n,n-1) = 0 for n >= 1;

%F T(n,n-2) = n*(n-3)/2 for n >= 4 [Poulet];

%F 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 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 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 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 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 Unfolded table with n individuals (rows) forming k pairs (columns):

%e     0    1    2    3    4    5    6    7

%e 0   1

%e 1   0    1

%e 2   0    0    1

%e 3   0    0    0    1

%e 4   0    0    2    0    1

%e 5   1    0    5    5    0    1

%e 6   3   12   15   20    9    0   1

%e 7  23   70  112   91   49   14   0   1

%p A326411 := proc(n,k)

%p     option remember;

%p     if k > n or k < 0 then

%p         0;

%p     elif k = n then

%p         1;

%p     elif k =0 then

%p         if n < 5 then

%p             0 ;

%p         elif n = 5 then

%p             1 ;

%p         elif n = 6 then

%p             3 ;

%p         elif n = 7 then

%p             23 ;

%p         else

%p             # Poulet eq (6) page 120, shifted n->n-2

%p             -(n^3-8*n^2+18*n-21)*procname(n-1,0)

%p             -4*(n^2-5*n)*procname(n-2,0)

%p             +2*(n^3-11*n^2+33*n-18)*procname(n-3,0)

%p             -(n^2-7*n+9)*procname(n-4,0)

%p             -(n^3-10*n^2+28*n-15)*procname(n-5,0) ;

%p             -%/(n^2-7*n+9) ;

%p         end if;

%p     elif n <= 3 then

%p         0;

%p     else

%p         # Poulet eq (3) page 119

%p         2*(n-k)*procname(n-1,k-1)/(n-1)+2*k*procname(n-1,k)/(n-1)

%p             +(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         %*n/k ;

%p     end if;

%p end proc:

%p for n from 0 to 12 do

%p     for k from 0 to n do

%p         printf("%a ",A326411(n,k)) ;

%p     end do:

%p     printf("\n") ;

%p end do: # _R. J. Mathar_, Mar 17 2022

%t 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     pc = -(n^3 - 8*n^2 + 18*n - 21)*T[n-1, 0]

%t       - 4*(n^2 - 5*n)*T[n - 2, 0]

%t       + 2*(n^3 - 11*n^2 + 33*n - 18)*T[n-3, 0]

%t       - (n^2 - 7*n + 9)*T[n-4, 0]

%t       - (n^3 - 10*n^2 + 28*n - 15)*T[n-5, 0];

%t     -pc/(n^2 - 7*n + 9)], n <= 3, 0, True,

%t    pc = 2*(n-k)*T[n-1, k-1]/(n-1) + 2*k*T[n-1, k]/(n-1) +

%t      (k - 2)*T[n-2, k-2]/(n-2) -

%t      2*(k-1)*T[n-2, k-1]/(n-2) + k*T[n-2, k]/(n-2);

%t     pc*n/k];

%t Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Mar 17 2023, after _R. J. Mathar_ *)

%o (Java) See Links section

%o (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 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 Cf. A002816 (column k=0).

%Y Row sums: A001710(n-1) = Sum_k T(n,k).

%Y Cf. also A326390 (accounting for rotation and reflection symmetry), A326397 (disregards reflection symmetry but allows rotation), A326407 (disregards rotation symmetry but allows reflection).

%Y See in addition A002464.

%K nonn,tabl

%O 0,13

%A _Witold Tatkiewicz_, Aug 07 2019