A232598 T(n,k) = Stirling2(n,k) * OrderedBell(k).

1, 1, 3, 1, 9, 13, 1, 21, 78, 75, 1, 45, 325, 750, 541, 1, 93, 1170, 4875, 8115, 4683, 1, 189, 3913, 26250, 75740, 98343, 47293, 1, 381, 12558, 127575, 568050, 1245678, 1324204, 545835, 1, 765, 39325, 582750, 3760491, 12391218, 21849366, 19650060, 7087261

Offset: 1

Author

Tilman Piesk, Nov 26 2013

Keywords

• nonn
• tabl

Comments

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

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.

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

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

Examples

			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.
Compare descriptions of A083355 and A233357.
a(3,1) = 1:
{1,2,3}
a(3,2) = 9:
{1,2}{3}
{1,3}{2}
{2,3}{1}
{1,2}:{3}   {3}:{1,2}
{1,3}:{2}   {2}:{1,3}
{2,3}:{1}   {1}:{2,3}
a(3,3) = 13:
{1}{2}{3}
{1}{2}:{3}   {3}:{1}{2}
{1}{3}:{2}   {2}:{1}{3}
{2}{3}:{1}   {1}:{2}{3}
{1}:{2}:{3}
{1}:{3}:{2}
{2}:{1}:{3}
{2}:{3}:{1}
{3}:{1}:{2}
{3}:{2}:{1}
Triangle begins:
     k = 1   2     3      4      5       6       7      8          sums
n
1        1                                                            1
2        1   3                                                        4
3        1   9    13                                                 23
4        1  21    78     75                                         175
5        1  45   325    750    541                                 1662
6        1  93  1170   4875   8115    4683                        18937
7        1 189  3913  26250  75740   98343   47293               251729
8        1 381 12558 127575 568050 1245678 1324204 545835       3824282
		

Links

• Tilman Piesk, First 100 rows, flattened
• Tilman Piesk, Preferential arrangements of set partitions (Wikiversity)

Crossrefs

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).

Formula

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

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

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

From Peter Bala, Nov 27 2013: (Start)

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! + ....

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)