login
Triangle read by rows: T(n,k) is the number of partitions of the set {1,2,...,n} having exactly k blocks that contain both odd and even entries (0<=k<=floor(n/2)).
12

%I #24 Jul 23 2024 14:46:04

%S 1,1,1,1,2,3,4,9,2,10,30,12,25,100,72,6,75,370,372,60,225,1369,1922,

%T 600,24,780,5587,9920,4500,360,2704,22801,51200,33750,5400,120,10556,

%U 101774,273920,234000,55800,2520,41209,454276,1465472,1622400,576600,52920,720

%N Triangle read by rows: T(n,k) is the number of partitions of the set {1,2,...,n} having exactly k blocks that contain both odd and even entries (0<=k<=floor(n/2)).

%C Row n has 1+floor(n/2) terms. Row sums are the Bell numbers (A000110). T(n,0)=A124419(n).

%H Alois P. Heinz, <a href="/A124418/b124418.txt">Rows n = 0..200, flattened</a>

%F The generating polynomial of row n is P[n](x)=Q[n](1,1,x), where the polynomials Q[n]=Q[n](t,s,x) are defined by Q[0]=1; Q[n]=t*dQ[n-1]/dt + x*dQ[n-1]/ds + x*dQ[n-1]/dx + t*Q[n-1] if n is odd and Q[n]=x*dQ[n-1]/dt + s*dQ[n-1]/ds + x*dQ[n-1]/dx + s*Q[n-1] if n is even.

%F Conjecture: T(n,k) = k!*A049020([n/2],k)*A049020([(n+1)/2],k) where A049020(n,k)=Sum_{i=0..n} S2(n,i)*C(i,k) and S2(n,k)=(1/k!)*Sum_{j=0..k} (-1)^(k-j)*C(k,j)*j^n (the Stirling numbers of 2nd kind). - _Paul D. Hanna_, Nov 08 2006

%F Sum_{k=0..floor(n/2)} = k * A362495(n). - _Alois P. Heinz_, Jun 05 2023

%e T(4,1) = 9 because we have 1234, 134|2, 1|234, 124|3, 14|2|3, 1|2|34, 123|4, 1|23|4 and 12|3|4.

%e Triangle starts:

%e 1;

%e 1;

%e 1, 1;

%e 2, 3;

%e 4, 9, 2;

%e 10, 30, 12;

%e 25, 100, 72, 6;

%e ...

%p Q[0]:=1: for n from 1 to 13 do if n mod 2 = 1 then Q[n]:=expand(t*diff(Q[n-1],t)+x*diff(Q[n-1],s)+x*diff(Q[n-1],x)+t*Q[n-1]) else Q[n]:=expand(x*diff(Q[n-1],t)+s*diff(Q[n-1],s)+x*diff(Q[n-1],x)+s*Q[n-1]) fi od: for n from 0 to 13 do P[n]:=sort(subs({t=1,s=1},Q[n])) od: for n from 0 to 13 do seq(coeff(P[n],x,j),j=0..floor(n/2)) od; # yields sequence in triangular form

%p # second Maple program:

%p with(combinat):

%p T:= proc(n, k) local g, u; g:= floor(n/2); u:=ceil(n/2);

%p add(binomial(g, i)*stirling2(i, k)*bell(g-i), i=k..g)*

%p add(binomial(u, i)*stirling2(i, k)*bell(u-i), i=k..u)*k!

%p end:

%p seq(seq(T(n,k), k=0..floor(n/2)), n=0..15); # _Alois P. Heinz_, Oct 23 2013

%t T[n_, k_] := Module[{g = Floor[n/2], u = Ceiling[n/2]}, Sum[Binomial[g, i] * StirlingS2[i, k]*BellB[g-i], {i, k, g}]*Sum[Binomial[u, i]*StirlingS2[i, k] * BellB[u-i], {i, k, u}]*k!]; Table[Table[T[n, k], {k, 0, Floor[n/2]}], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, Feb 20 2015, after _Alois P. Heinz_ *)

%o (PARI) {T(n,k)=if(k<0||k>n,0, k!*(n\2)!*((n+1)\2)!*polcoeff(polcoeff(exp((1+y)*(exp(x+x*O(x^n))-1)),n\2),k) *polcoeff(polcoeff(exp((1+y)*(exp(x+x*O(x^n))-1)),(n+1)\2),k))} \\ _Paul D. Hanna_, Nov 08 2006

%Y Cf. A000110, A124419, A124420, A124421, A124422, A124423.

%Y Cf. A124526, A362495.

%Y T(2n,n) gives A000142.

%K nonn,tabf

%O 0,5

%A _Emeric Deutsch_, Oct 31 2006