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,3

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.

Links

Tilman Piesk, First 100 rows, flattened

Tilman Piesk, Preferential arrangements of set partitions (Wikiversity)

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)

Example

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

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

Sequence in context: A173020 A334062 A157383 * A174510 A378577 A141237

Adjacent sequences: A232595 A232596 A232597 * A232599 A232600 A232601

Keyword

nonn,tabl

Author

Tilman Piesk, Nov 26 2013

Status

approved