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.

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

Offset: 0

Author

Witold Tatkiewicz, Aug 07 2019

Keywords

• nonn
• tabl

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.

Examples

			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
		

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.

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.

Programs

Java

See Links section

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 *)

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

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]