I've been struggling with a certain combinatorics problem for weeks now. Unfortunately, I don't have a proper background in enumerative combinatorics, haven't learned that class yet. I've tried searching around the internet, but either I missed an answer or I couldn't find it.
My question is as follows:
a) Given a set X of n elements, count all possible unique combinations of length m that feature every element from X at least once. m>=n (Repetition is obviously allowed and needed when m>n)
So, if X is for example [1,2,3] and m is 5, I need to obtain the count of all distinguishable configurations of length 5 (order of the configuration matters) that feature 1,2 and 3 at least once.
11223,12312,32112 are all good.
b) Expanding on a, but with added restrictions. Some elements of X are given restrictions that they can't occur in some places of configurations. Count of configurations is needed.
For example, if X is [1,2,3,4,5], n=5, m=7 and the restriction is that 1 and 2 can't appear on the first position, and 4 can't appear on the third, some of the valid combinations would
3412533,4312533, etc. are valid combinations
Count is needed, same as in a.
I tried solving the b case immediately with something like this:
[3,4,5] -> numbers that can appear in the first position
[1,2,3,4,5] -> numbers that can appear in 2nd, 4rd,5th,6th, 7th position
[1,2,3,5] -> numbers that can appear in 3rd position
But I get stuck. I'm assuming that some form of inclusion-exclusion needs to be done here, but I am unable to figure out how. If anyone could give me some pointers, I would be very grateful.