0,3

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 | be a seperator 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).

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page.

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;

The Maple program is the same as for the preferential arrangement (A000670) with one exception.

In the factor Fac2 the nominator 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)) = multipliticity 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 (vladeta(AT)eunet.rs), 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 (vladeta(AT)eunet.rs), Sep 17 2007

Cf. A000670.

Sequence in context: A036367 A115256 A132963 this_sequence A150670 A150671 A150672

Adjacent sequences: A122401 A122402 A122403 this_sequence A122405 A122406 A122407

nonn

Thomas Wieder (thomas.wieder(AT)t-online.de), Sep 01 2006

Edited by N. J. A. Sloane (njas(AT)research.att.com), Sep 14 2006