A261139 S'_t(n) is the number of set partitions of {1,2,...,t} into exactly n parts such that no part contains both 1 and t or both i and i+1 for some i with 1 <= i < t; triangle S'_t(n), t >= 0, 0 <= n <= t, read by rows.

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 0, 5, 5, 1, 0, 0, 1, 10, 20, 9, 1, 0, 0, 0, 21, 70, 56, 14, 1, 0, 0, 1, 42, 231, 294, 126, 20, 1, 0, 0, 0, 85, 735, 1407, 924, 246, 27, 1, 0, 0, 1, 170, 2290, 6363, 6027, 2400, 435, 35, 1

Offset: 0

Author

Mark Wildon, Aug 10 2015

Keywords

• nonn
• tabl

Comments

S'A261137%20may%20be%20defined%20by%20B'_t(n)%20=%20Sum">t(n) is the number of sequences of t non-identity top-to-random shuffles of a deck of n cards that move each card at some time, and overall leave the deck invariant. (See link below.) A261137 may be defined by B'_t(n) = Sum{m=0..n} S'_t(m).

Examples

			Triangle starts:
  1;
  0, 0;
  0, 0, 1;
  0, 0, 0,  1;
  0, 0, 1,  2,   1;
  0, 0, 0,  5,   5,    1;
  0, 0, 1, 10,  20,    9,   1;
  0, 0, 0, 21,  70,   56,  14,   1;
  0, 0, 1, 42, 231,  294, 126,  20,  1;
  0, 0, 0, 85, 735, 1407, 924, 246, 27,  1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
• D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.
• Sophie Morier-Genoud, Counting Coxeter's friezes over a finite field via moduli spaces, arXiv:1907.12790 [math.CO], 2019.
• Augustine O. Munagi, Two Applications of the Bijection on Fibonacci Set Partitions, Fibonacci Quart. 55 (2017), no. 5, 144-148. See c(n,k) p. 145 giving shifted triangle.

Crossrefs

Columns n=3,4 give: A000975, A243869.

Row sums give A000296.

Cf. A261137.

The same as A105794, except for the first two columns.

Programs

Maple

g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),
       add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1))
    end:
S:= t-> (p-> seq(coeff(p, x, i), i=0..t))(g(t, 0$2)):
seq(S(t), t=0..12);  # Alois P. Heinz, Aug 10 2015

Mathematica

StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}]; T[0, 0] = 1; T[, 0] = T[, 1] = 0; T[n_, k_] := SeriesCoefficient[ StirPrimedGF[k, x], {x, 0, n}]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* script completed by Jean-François Alcover, Jan 31 2016 *)

PARI

a(n,k)=if(k==0, n==0, sum(j=0, k, binomial(k, j) * (-1)^(k-j) * ((j-1)^n + (-1)^n * (j-1))) / k!);
for(n=0, 10, for(k=0, n, print1( a(n, k), ", "); ); print(); ); \\ Andrew Howroyd, Apr 08 2017

Formula

G.f. for column n > 1: x^n/((1+x)*Product_{j=1..n-1} (1-j*x)).

S'_t(n) ~ (n-1)^t/n! as t tends to infinity.

Recurrence: S't(n) = S'{t-1}(n-1) + (n-1)*S'_{t-1}(n) for n >= 3.

S't(n) = (1/n!) * Sum{j=0..n} (-1)^(n-j) * binomial(n, j) * ((j-1)^t + (-1)^t * (j-1)) for t>0. - Andrew Howroyd, Apr 08 2017

Sum_{n=0..t} (n-1)*S'{t-1}(n) + n*S'{t-2}(n) = A000296(t) for t >= 3. - Yuchun Ji, Feb 23 2021

T(m, k) = Sum_{i=k..m} Stirling2(i-1, k-1)*(-1)^(i+m), for k >= 2. (See Peter Bala's original formula at A105794 dated Jul 10 2013.) - Igor Victorovich Statsenko, May 31 2024

T(m, k) = (Sum_{i=0..m} Stirling2(i, k)*binomial(m,i)*(-1)^(m-i))*I(m,k), where I(m,k) = (1-Sum_{i=0..m} Stirling1(k, i))^(m+k) for k >= 0. (See Peter Bala's original formula at A105794 dated Jul 10 2013.) - Igor Victorovich Statsenko, Jun 01 2024