|
|
A232598
|
|
T(n,k) = Stirling2(n,k) * OrderedBell(k)
|
|
3
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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.
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).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|