A326397 -id:A326397 - 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.

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

Witold Tatkiewicz, Aug 07 2019

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.

			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

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.

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.

Java
```
See Links section
```

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

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

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

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]

A326390 The number of ways of seating n people around a table for the second time so that k pairs are maintained. T(n,k) read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 0, 6, 0, 0, 16, 0, 8, 10, 0, 50, 50, 0, 10, 36, 144, 180, 240, 108, 0, 12, 322, 980, 1568, 1274, 686, 196, 0, 14, 2832, 8704, 11840, 10240, 4832, 1536, 320, 0, 16, 27954, 81000, 108054, 85050, 43902, 13446, 2970, 486, 0, 18, 299260, 834800, 1071700, 828400, 416200, 141520, 31000, 5200, 700, 0, 20

Offset: 0

Witold Tatkiewicz, Jul 03 2019

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.
Sum of each row is equal to n!.
Weighted average of each row using k as weights converges to 2 for large n and is given with following formula: (Sum_{k} T(n,k)*k)/n! = 2/(n-1) + 2 (conjectured).

			Assuming initial order was {1,2,3,4,5} (therefore 1 and 5 forms pair as first and last person are neighbors in case of 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 allow for rotation ({1,2,3,5,4} and {2,3,5,4,1} are different) and reflection ({1,2,3,5,4} and {4,5,3,2,1} are also different) the total number of ways is 5*2*5 and therefore T(5,3)=50.
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    2
3   0    0    0    6
4   0    0   16    0    8
5  10    0   50   50    0   10
6  36  144  180  240  108    0   12
7 322  980 1568 1274  686  196    0   14

Witold Tatkiewicz, Rows n = 0..17 of triangle, flattened
Witold Tatkiewicz, Link for Java program

Cf. A089222 (column k=0).
Cf. A000142 sum of each row.
Cf. A326397 (disregards reflection symmetry), A326404 (disregards circular symmetry), A326411 (disregards both circular and reflection symmetry).

Java
```
See Links section
```

T(n,n) = 2*n for n > 2;
T(n,n-1) = 0 for n > 1;
T(n,n-2) = n^2*(n-3) for n > 3 (conjectured);
T(n,n-3) = (3/4)*n^4 + 6*n^3 + (2/3)*n^2 - 14*n + 6 for n > 4 (conjectured);
T(n,n-4) = (25/12)*n^5 + (73/6)*n^4 + (5/4)*n^3 - (253/6)*n^2 + (152/3)*n - 24 for n > 5 (conjectured);
T(n,n-5) = (52/15)*n^6 + (77/3)*n^5 + 14*n^4 - (194/3)*n^3 + (4628/15)*n^2 - 273*n + 130 for n > 5 (conjectured);
T(n,n-6) = (707/120)*n^7 + (2093/40)*n^6 + (2009/40)*n^5 - (245/8)*n^4 + (78269/60)*n^3 - (18477/10)*n^2 + (21294/10)*n - 684 for n > 6 (conjectured).

A326404 Triangle T(n,k) read by rows: T(n,k) = number of ways of seating n people around a table for the second time so that k pairs are maintained. Rotated sequences are counted as one.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 4, 0, 2, 2, 0, 10, 10, 0, 2, 6, 24, 30, 40, 18, 0, 2, 46, 140, 224, 182, 98, 28, 0, 2, 354, 1088, 1480, 1280, 604, 192, 40, 0, 2, 3106, 9000, 12006, 9450, 4878, 1494, 330, 54, 0, 2, 29926, 83480, 107170, 82840, 41620, 14152, 3100, 520, 70, 0, 2

Offset: 0

Witold Tatkiewicz, Aug 01 2019

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.
Sum of row n is equal to (n-1)! for n > 1.
Conjecture: The weighted average of each row using k as weights converges to 2 for large n and is given by the following formula: (Sum_{k} T(n,k)*k)/(Sum_{k} T(n,k)) = 2/(n-1) + 2.

			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) but we allow reflection ({1,2,3,5,4} and {4,5,3,2,1} are considered distinct), the total number of ways is 5*2 and therefore T(5,3)=10.
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    2
4   0    0    4    0    2
5   2    0   10   10    0    2
6   6   24   30   40   18    0    2
7  46  140  224  182   98   28    0    2

Witold Tatkiewicz, Rows n = 0..17 of triangle, flattened
Witold Tatkiewicz, Link for Java program.

Cf. A078603 (column k=0).
Sum of n-th row is A000142(n-1) for n > 0.
Cf. A326390 (accounting for rotation and reflection symmetry), A326397 (disregards reflection symmetry but allows rotation), A326411 (disregards both reflection and rotation symmetry).

Java
```
See Links section
```

T(n,n) = 2 for n > 2;
T(n,n-1) = 0 for n > 1.
Conjectures:
T(n,n-2) = n^2 + n - 2 for n > 3;
T(n,n-3) = (4/3)*n^3 + 2*n^2 - (16/3)*n + 2 for n > 4;
T(n,n-4) = (25/12)*n^4 + (23/6)*n^3 - (169/12)*n^2 + (85/6)*n - 6 for n > 5;
T(n,n-5) = (52/15)*n^5 + (25/3)*n^4 - (83/3)*n^3 + (221/3)*n^2 - (299/5)*n + 26 for n > 5;
T(n,n-6) = (707/120)*n^6 + (2037/120)*n^5 - (413/8)*n^4 + (2233/8)*n^3 - (5554/15)*n^2 + (3739/10)*n - 114 for n > 6.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Maple

Mathematica

PARI

Formula

A326390 The number of ways of seating n people around a table for the second time so that k pairs are maintained. T(n,k) read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Formula

A326404 Triangle T(n,k) read by rows: T(n,k) = number of ways of seating n people around a table for the second time so that k pairs are maintained. Rotated sequences are counted as one.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Formula