OFFSET
0,3
COMMENTS
Consider a hierarchy H(n,L) of n labeled elements {1,2,3,...,n} with up to L=n levels like in the preferential arrangement (A000670). Let | denote a separator between two elements. A hierarchy will be written as a list of elements and level separators.
For example, [1|2|3,4,5] is a hierarchy with n=5 elements in which element 1 is on level l_1, element 2 on level l_2 and elements 3,4,5 on level l_3. Usually the elements can be permuted among the levels.
In the particular hierarchy H(n,L,o), among levels with the same number of elements no permutation of elements is allowed. These "permutation restricted" levels are marked with o for clarification. Thus in hierarchy [1,2|o3|o4] the levels l_2 and l_3 do not exchange elements with each other. We may say that the hierarchies [1,2|o3|o4] and [1,2|o4|o3] are to be considered as equivalent and count as one hierarchy only.
However l_2 and l_3 can swap elements with level l1. Then we can have the 12 hierarchies H(n=4,L=3): [1,2|o3|o4], [1,3|o2|o4],...,[o1|o4|2,3] (see the example section) instead of 36 hierarchies H(n=4,L=3) as in the restricted case (A000670).
EXAMPLE
For H(n=4,L=n,o) we have a(4) = 25 hierarchies:
[[o1|o2|o3|o4]] --> 1;
[[1,2|o3|o4], [1,3|o2|o4], [1,4|o2|o3], [2,3|o1|o4],
[o3|1,2|o4], [o2|1,3|o4], [o2|1,4|o3], [o1|2,3|o4],
[o3|o4|1,2], [o2|o4|1,3], [o2|o3|1,4], [o1|o4|2,3]] --> 12;
[[1,2,3|4], [4,1,2|3], [3,4,1|2], [2,3,4|1], [4|1,2,3], [3|4,1,2], [[2|3,4,1], [1|2,3,4]] --> 8;
[[o1,2|o3,4], [o1,3|o2,4], [o1,4|o2,3]] --> 3;
[[o1,2,3,4]] --> 1;
MAPLE
The Maple program is the same as for the preferential arrangement (A000670) with one exception.
In the factor Fac2 the numerator NumberOfParts (= number of parts of a partition) is replaced by NumberOfDifferentParts (= number of different parts of a partition). This replacement restricts the exchange of elements to levels with different occupation numbers.
with(combinat):
A122404 := proc(n::integer)
local i, k, prttnlst, prttn, NumberOfParts, liste, NumberOfDifferentParts, Fac1, Fac2, F3;
# prttn = an integer partition of n
# E.g. [1, 1, 1, 2] is a partition of n=5 with four parts.
# op(j, prttn) = the j-th part of prttn.
# op(2, op(j, liste)) = multiplicity of the j-th part.
# E.g. in [1, 1, 1, 2] the digit "1" has a multiplicity of 3.
F3 := 0;
for k from 1 to n do
prttnlst := PartitionList(n, k);
NumberOfParts := 0;
NumberOfDifferentParts := 0;
for i from 1 to nops(prttnlst) do
prttn := prttnlst[i];
NumberOfParts := nops(prttn);
liste := convert(prttn, multiset);
NumberOfDifferentParts := nops(liste);
Fac1 := n!/mul(op(j, prttn)!, j=1..NumberOfParts);
Fac2 := (NumberOfDifferentParts!/ mul(op(2, op(j, liste))!, j=1..NumberOfDifferentParts));
F3 := F3 + Fac1*Fac2;
od;
od;
print(F3);
end proc;
PartitionList := proc (n, k)
local East, West;
if n < 1 or k < 1 or n < k then
RETURN([])
elif n = 1 then
RETURN([[1]])
else if n < 2 or k < 2 or n < k then
West := []
else
West := map(proc (x) options operator, arrow;
[op(x), 1] end proc, PartitionList(n-1, k-1)) end if;
if k <= n-k then
East := map(proc (y) options operator, arrow;
map(proc (x) options operator, arrow; x+1 end proc, y) end proc, PartitionList(n-k, k))
else East := [] end if;
RETURN([op(West), op(East)])
end if;
end proc;
A122404 := proc (n) local p, q, k, s; p := combinat:-partition(n); s := 0; for k to nops(p) do q := convert(p[k], multiset); s := s+nops(q)!/mul(q[i][2]!*q[i][1]!^q[i][2], i = 1 .. nops(q)) end do; return n!*s end proc: seq(A122404(n), n=1..30); # Vladeta Jovovic, Sep 17 2007
A122404 := proc (n) local f, s, c, deg, ss, sm; f := mul(1+y*(exp(x^k/k!)-1), k = 1 .. n+1); s := series(f, x, n+1); c := n!*coeff(s, x, n); ss := series(c, y, floor(1/2*sqrt(1+8*n)+1/2)); sm := add(l!*coeff(ss, y, l), l = 1 .. n); return sm end proc: seq(A122404(n), n=1..30); # Vladeta Jovovic, Sep 17 2007
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Wieder, Sep 01 2006
EXTENSIONS
Edited by N. J. A. Sloane, Sep 14 2006
STATUS
approved