login
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.
10

%I #77 Jun 21 2024 15:36:12

%S 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,

%T 70,56,14,1,0,0,1,42,231,294,126,20,1,0,0,0,85,735,1407,924,246,27,1,

%U 0,0,1,170,2290,6363,6027,2400,435,35,1

%N 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.

%C S'_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).

%H Alois P. Heinz, <a href="/A261139/b261139.txt">Rows n = 0..140, flattened</a>

%H John R. Britnell and Mark Wildon, <a href="http://arxiv.org/abs/1507.04803">Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D</a>, arXiv:1507.04803 [math.CO], 2015.

%H D. E. Knuth and O. P. Lossers, <a href="http://www.jstor.org/stable/27642185">Partitions of a circular set</a>, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.

%H Sophie Morier-Genoud, <a href="https://arxiv.org/abs/1907.12790">Counting Coxeter's friezes over a finite field via moduli spaces</a>, arXiv:1907.12790 [math.CO], 2019.

%H Augustine O. Munagi, <a href="https://www.fq.math.ca/Papers1/55-5/Munagi.pdf">Two Applications of the Bijection on Fibonacci Set Partitions</a>, Fibonacci Quart. 55 (2017), no. 5, 144-148. See c(n,k) p. 145 giving shifted triangle.

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

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

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

%F 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

%F 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

%F 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

%F 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

%e Triangle starts:

%e 1;

%e 0, 0;

%e 0, 0, 1;

%e 0, 0, 0, 1;

%e 0, 0, 1, 2, 1;

%e 0, 0, 0, 5, 5, 1;

%e 0, 0, 1, 10, 20, 9, 1;

%e 0, 0, 0, 21, 70, 56, 14, 1;

%e 0, 0, 1, 42, 231, 294, 126, 20, 1;

%e 0, 0, 0, 85, 735, 1407, 924, 246, 27, 1;

%e ...

%p g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),

%p add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1))

%p end:

%p S:= t-> (p-> seq(coeff(p, x, i), i=0..t))(g(t, 0$2)):

%p seq(S(t), t=0..12); # _Alois P. Heinz_, Aug 10 2015

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

%o (PARI)

%o 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!);

%o for(n=0, 10, for(k=0, n, print1( a(n, k), ", "); ); print(); ); \\ _Andrew Howroyd_, Apr 08 2017

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

%Y Row sums give A000296.

%Y Cf. A261137.

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

%K nonn,tabl

%O 0,14

%A _Mark Wildon_, Aug 10 2015