A375219 T(n,k) is the number of permutations of the multiset {1, 1, 1, 2, 2, 2, ..., n, n, n} with k occurrences of fixed triples (j,j,j), where T(n,k), n >= 2, 0 <= k <= n-2 is a triangle read by rows.

19, 1622, 57, 362997, 6488, 114, 166336604, 1814985, 16220, 190, 136221590695, 998019624, 5444955, 32440, 285, 181552310074386, 953551134865, 3493068684, 12704895, 56770, 399, 367942716863474473, 1452418480595088, 3814204539460, 9314849824, 25409790, 90832, 532

Offset: 2

Author

Hugo Pfoertner, Aug 08 2024

Keywords

• nonn
• tabl

Comments

Trivially, T(n,n) = 1 and T(n,n-1) = 0.

Examples

			The triangle begins
         19;
       1622,      57;
     362997,    6488,   114,
  166336604, 1814985, 16220, 190;
.
T(2,0) = 19: the permutations of {1,1,1,2,2,2} with no fixed triples are
[1,1,2,1,2,2], [1,1,2,2,1,2], [1,1,2,2,2,1], [1,2,1,1,2,2], [1,2,1,2,1,2], [1,2,1,2,2,1], [1,2,2,1,1,2], [1,2,2,1,2,1], [1,2,2,2,1,1], [2,1,1,1,2,2], [2,1,1,2,1,2], [2,1,1,2,2,1], [2,1,2,1,1,2], [2,1,2,1,2,1], [2,1,2,2,1,1], [2,2,1,1,1,2], [2,2,1,1,2,1], [2,2,1,2,1,1], [2,2,2,1,1,1].
		

Crossrefs

Cf. A014606.

Cf. A374980, A375223 (columns 0 and 1 in a similar triangle for the multiset {1, 1, 2, 2, ..., n, n}).

Programs

PARI

mima (x, n1=1, i2=-oo) = {my (n2, n=#x, mi=x[n1], ma=mi); n2=if (i2<=0, n, min(n,i2)); for (i=n1+1, n2, if (x[i]ma, ma=x[i]))); [mi,ma]};
\\ returns row n of triangle, bsize is the block size in the multiset.
a375219(n, bsize=3) = {my (p=vector(bsize*n, i, 1+(i-1)\bsize), r=s=vector(n), m=vector(n-1)); forperm (p, q, for (b=1, n, my (bm=bsize*(b-1), j=mima(q, bm+1, bm+bsize)); r[b]=j[1]; s[b]=j[2]); my (rs=vector(n, i, r[i]==i && s[i]==i)); for (k=0 ,n-2, m[k+1]+=vecsum(rs)==k)); m}

Formula

Sum_{j=0..n-2} T(n,j) = (3*n)!/(6^n) - 1 = A014606(n) - 1.

Extensions

More terms (three rows) from Alois P. Heinz, Aug 16 2024