C compositions of $N$ balls grouped in k types given first and/or last offset ...

Question

You have $C$ compositions of $N$ balls indistinguishably colored as $k$ different kinds:

$$N = n_1 + n_2 + n_3 ... + n_k$$

https://en.wikipedia.org/wiki/Composition_(combinatorics)

The total number of arrangements of those compositions is given by the multinomial coefficient as:

$$\frac{N!}{((n_1!)(n_2!)(n_3!) ... (n_k!))}$$

Now, say that in addition to the condition about the total number of balls N and the particular composition (the order of the k groups matters), you include the first and/or last offset of each kind of ball.

That would drastically reduce the total number of possible arrangements, but, what would that number be?

Any generating algorithm to the possible arrangements?

I haven't found much regarding that last condition to those kinds of problems in combinatorics. Do you know of a solution to them? Any hint sbout how to approach a solution (even if partial)?

Any papers or books about those problems you would suggest?

lbrtchx

Answer 1

Here is a first draft of a raw algorithmic solution to the enumeration of the possible arrangements of the combinatoric problem I posted.

Given:

1) N: total number of items ((substrings of) characters in a file, DNA segments, marked up objects (colored balls)...)

2) K: number of klasses in which $1 come

3) C: composition of weights of $2 (order matters when it comes to the klasses of items)

N = n1 + n2 + n3 + ... + nk, with ni > 0

there are slots in the N-length string which can be set and those which are fixed.

• if ni = 1, that spot is fixed by the first (, last and only) item (K1 is the number of such lone item klasses)
• if ni = 2, the two spots are fixed by the first and last item (K2 is the number of such paired items klasses)
• if ni > 2, the first and last item are fixed, but the rest (ni - 2) ones may be set in all not fixed slots from the klass' first to the last one (K2+ is the number items in such klasses)
• there may also be forcibly fixed items (between the first and last one) due to gaps between the first offsets of contiguous klasses if the offsets of the first characters of other klasses are greater. (KFi is the number of such items for each klass i)

The total number of settable slots will then be:

NS = N - (K1 + 2*K2 + 2*K2+ + sum(i)(KFi))

There will then be ranges where certain klasses of items can be set (after the first and before the last); so, slots can be only occupied by certain klasses of items. Ranges may overlap.

The value of the multinomial coefficient given such conditions is greatly reduced and there are the extreme cases in which:

a) all items are forcibly fixed so NS=1

b) the first offset of all klasses crowd the head and the last the tail of the possible slots so that there are no forceful fixing of characters occur and the ranges are largest ((reduced form of the) multinomial coefficient will work then).

Then the greedy assumption is made that items the appeared first are more likely to reappear again and in this way all possible arrangements are enumerated.

I am not claiming this is a most perfect algorithmic idea and I thought of it as I taught today. Most probably, silly flaws and shortcomings slipped into my thinking.

Be mercilessly helpful at pointing out to me ways to improve this raw algorithm.

I will post within a week an implementation of such an algorithm with edge cases and stress testing runs.

Thank you, Allie, for editing my post.

lbrtchx