0
$\begingroup$

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.

For example:

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.

$\endgroup$

migrated from mathoverflow.net Feb 12 '17 at 9:27

This question came from our site for professional mathematicians.

  • $\begingroup$ The first problem is the well-known problem of counting surjections. $\endgroup$ – Ira Gessel Feb 11 '17 at 20:03
1
$\begingroup$

This question is better suited for math.stackexchange.

For a) count all combinations using at most all of X elements. Then subtract off all combinations using all but one of the X elements. You can develop a recursive relation on the number of elements from the set which will lead to the right inclusion-exclusion formula.

For b) there are two approaches, and I am too ignorant to provide all the details. The first is a case analysis. You say first that all of the elements appear in the unconstrained part. Then you count those combinations easily. Then you say all but one of the elements appear in the unconstrained part. Now you break into cases depending on where the last element is allowed to appear. Continue this development by restricting the number of elements appearing in the unconstrained part. Add up the totals.

The second way is to encode using generating functions. I do not know the details, but they look something like this. Represent each position by a polynomial. Multiply the polynomials together. Look at the coefficients of the monomials of interest. For example, your encoding may involve looking at the coefficients associated with x^{12345}, with x^{23154}, and maybe 118 other powers. Add those up.

Gerhard "Not A Student Of Combinatorics" Paseman, 2017.02.11.

$\endgroup$
  • $\begingroup$ I think I figured the generating function approach. Finally progress. Thank you very much! $\endgroup$ – plagueis Feb 12 '17 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy