login
T(n,k) = Stirling2(n,k) * OrderedBell(k)
3

%I #30 Dec 10 2013 02:31:40

%S 1,1,3,1,9,13,1,21,78,75,1,45,325,750,541,1,93,1170,4875,8115,4683,1,

%T 189,3913,26250,75740,98343,47293,1,381,12558,127575,568050,1245678,

%U 1324204,545835,1,765,39325,582750,3760491,12391218,21849366,19650060,7087261

%N T(n,k) = Stirling2(n,k) * OrderedBell(k)

%C T(n,k) is the number of preferential arrangements of the k-part partitions of the set {1...n}.

%C 2*T(n,k) is the number of formulas in first order logic that have an n-place predicate and use k variables, but don't include a negator.

%C 4*T(n,k) is the number of such formulas that may include an negator.

%C The entries T(n,n) are A000670(n), i.e. the ordered Bell numbers.

%H Tilman Piesk, <a href="/A232598/b232598.txt">First 100 rows, flattened</a>

%H Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Preferential_arrangements_of_set_partitions">Preferential arrangements of set partitions</a> (Wikiversity)

%F T(n,k) = A008277(n,k) * A000670(k).

%F T(n,n) = A000670(n).

%F T(n,2) = A068156(n-1).

%F From _Peter Bala_, Nov 27 2013: (Start)

%F E.g.f.: 1/( 2 - exp(x*(exp(t) - 1)) ) = 1 + x*t + (x + 3*x^2)*t^2/2! + (x + 9*x^2 + 13*x^3)*t^3/3! + ....

%F Recurrence equation (for entries not on main diagonal): (n - k)*T(n,k) = C(n,1)*T(n-1,k) - C(n,2)*T(n-2,k) + C(n,3)*T(n-3,k) - ... (End)

%e Let the colon ":" be a separator between two levels. E.g. in {1,2}:{3} the set {1,2} is on the first level, the set {3} is on the second level.

%e Compare descriptions of A083355 and A233357.

%e a(3,1) = 1:

%e {1,2,3}

%e a(3,2) = 9:

%e {1,2}{3}

%e {1,3}{2}

%e {2,3}{1}

%e {1,2}:{3} {3}:{1,2}

%e {1,3}:{2} {2}:{1,3}

%e {2,3}:{1} {1}:{2,3}

%e a(3,3) = 13:

%e {1}{2}{3}

%e {1}{2}:{3} {3}:{1}{2}

%e {1}{3}:{2} {2}:{1}{3}

%e {2}{3}:{1} {1}:{2}{3}

%e {1}:{2}:{3}

%e {1}:{3}:{2}

%e {2}:{1}:{3}

%e {2}:{3}:{1}

%e {3}:{1}:{2}

%e {3}:{2}:{1}

%e Triangle begins:

%e k = 1 2 3 4 5 6 7 8 sums

%e n

%e 1 1 1

%e 2 1 3 4

%e 3 1 9 13 23

%e 4 1 21 78 75 175

%e 5 1 45 325 750 541 1662

%e 6 1 93 1170 4875 8115 4683 18937

%e 7 1 189 3913 26250 75740 98343 47293 251729

%e 8 1 381 12558 127575 568050 1245678 1324204 545835 3824282

%Y A008277 (Stirling2), A000670 (ordered Bell), A068156 (column k=2), A083355 (row sums: number of preferential arrangements), A233357 (number of preferential arrangements by number of levels).

%K nonn,tabl

%O 1,3

%A _Tilman Piesk_, Nov 26 2013