|
%I #59 May 04 2023 06:40:38
%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
%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
|
