A294201 Irregular triangle read by rows: T(n,k) is the number of k-partitions of {1..3n} that are invariant under a permutation consisting of n 3-cycles (1 <= k <= 3n).

1, 0, 1, 1, 1, 3, 2, 0, 1, 1, 3, 10, 12, 3, 9, 3, 0, 1, 1, 7, 33, 59, 30, 67, 42, 6, 18, 4, 0, 1, 1, 15, 106, 270, 216, 465, 420, 120, 235, 100, 10, 30, 5, 0, 1, 1, 31, 333, 1187, 1365, 3112, 3675, 1596, 2700, 1655, 330, 605, 195, 15, 45, 6, 0, 1

Offset

1,6

Comments

T(n,k) = coefficient of x^k for A(3,n)(x) in Gilbert and Riordan's article. - Robert A. Russell, Jun 13 2018

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1395

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Formula

T(n,k) = [n==0 & k==0] + [n>0 & k>0] * (k*T(n-1,k) + T(n-1,k-1) + T(n-1,k-3)). - Robert A. Russell, Jun 13 2018

T(n,k) = n!*[x^n*y^k] exp(Sum_{d|3} y^d*(exp(d*x) - 1)/d). - Andrew Howroyd, Sep 20 2019

Example

Triangle begins:
  1,  0,   1;
  1,  1,   3,   2,   0,   1;
  1,  3,  10,  12,   3,   9,   3,   0,   1;
  1,  7,  33,  59,  30,  67,  42,   6,  18,   4,  0,  1;
  1, 15, 106, 270, 216, 465, 420, 120, 235, 100, 10, 30, 5, 0, 1;
  ...
Case n=2: Without loss of generality the permutation of two 3-cycles can be taken as (123)(456). The second row is [1, 1, 3, 2, 0, 1] because the set partitions that are invariant under this permutation in increasing order of number of parts are {{1, 2, 3, 4, 5, 6}}; {{1, 2, 3}, {4, 5, 6}}; {{1, 4}, {2, 5}, {3, 6}}, {{1, 5}, {2, 6}, {3, 4}}, {{1, 6}, {2, 4}, {3, 5}}; {{1, 2, 3}, {4}, {5}, {6}}, {{1}, {2}, {3}, {4, 5, 6}}, {{1}, {2}, {3}, {4}, {5}, {6}}.

Maple

T:= proc(n, k) option remember; `if`([n, k]=[0, 0], 1, 0)+
     `if`(n>0 and k>0, k*T(n-1, k)+T(n-1, k-1)+T(n-1, k-3), 0)
    end:
seq(seq(T(n, k), k=1..3*n), n=1..8);  # Alois P. Heinz, Sep 20 2019

Mathematica

T[n_, k_] := T[n, k] = If[n>0 && k>0, k T[n-1, k] + T[n-1, k-1] + T[n-1, k-3], Boole[n==0 && k==0]] (* modification of Gilbert & Riordan recursion *)
Table[T[n, k], {n, 1, 10}, {k, 1, 3n}] // Flatten (* Robert A. Russell, Jun 13 2018 *)

Prog

(PARI) \\ see A056391 for Polya enumeration functions
T(n, k)={my(ci=PermCycleIndex(CylinderPerms(3, n)[2])); StructsByCycleIndex(ci, k) - if(k>1, StructsByCycleIndex(ci, k-1))}
for (n=1, 6, for(k=1, 3*n, print1(T(n, k), ", ")); print);
(PARI)
G(n)={Vec(-1+serlaplace(exp(sumdiv(3, d, y^d*(exp(d*x + O(x*x^n))-1)/d))))}
{ my(A=G(6)); for(n=1, #A, print(Vecrev(A[n]/y))) } \\ Andrew Howroyd, Sep 20 2019

Crossrefs

Row sums are A002874.

Column k=3 gives A053156.

Maximum row values are A294202.

Unrelated to A002875.

Cf. A002872, A002873, A293181.

Sequence in context: A280265 A292795 A295028 * A079618 A151844 A286223

Adjacent sequences: A294198 A294199 A294200 * A294202 A294203 A294204

Keyword

nonn,tabf

Author

Andrew Howroyd, Oct 24 2017

Status

approved