A122404 Number of preferential arrangements of n labeled elements where the exchange of elements among the levels is restricted to levels of different occupation numbers.

0, 1, 2, 8, 25, 102, 619, 3012, 17210, 100980, 796797, 5350138, 41054864, 313424464, 2545451783, 23433207732, 206742504343, 1964483722070, 18932563920493, 189888762507928, 1933963299246176, 21213419239538308, 230266075236104673, 2633055815662413522

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

Links

Table of n, a(n) for n=0..23.

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

Cf. A000670.

Sequence in context: A036367 A115256 A132963 * A150670 A150671 A150672

Adjacent sequences: A122401 A122402 A122403 * A122405 A122406 A122407

Keyword

nonn

Author

Thomas Wieder, Sep 01 2006

Extensions

Edited by N. J. A. Sloane, Sep 14 2006

Status

approved