Chromatic Polynomials 12 – Subfactorials and Subpermutations

In combinatorics, a derangement is an arrangement of objects where no object appears in its original position. Here’s a commonly used example:

A postman is delivering five letters to five mailboxes. He put one letter in each box, but no box contained the right letter. How many ways could he have done this?

We can answer this question with CPs. We use one vertex for each letter, σ₁ - σ₅. Since each letter must be placed in a different mailbox, we have this condition that no two vertices are equal:

Then, we have to specify that vertex n cannot be assigned the value n. We can do this using inclusive terms or exclusive terms:

or

Each approach has its advantages. The exclusive terms are expandable to any size set. That is, exclusive terms can be summed from 1 to Q.

The inclusive term is much faster to evaluate since it doesn’t require any expansion of terms (besides the UniquePositions terms) before summing. Since the inclusive terms are hardcoded to 5 specific values, it doesn’t make sense to sum them from 1 to Q. Instead, they should be summed from 1 – 5:

In general, the function that finds the number of derangements for N items is called a subfactorial, and is denoted with: !n.  The CP above tell us that !5 = 44.

Subpermutations

Factorials and permutations are related. The number of ways to order N items is N!. But if you make an ordered selection of R out of N items, you have a permutation, calculated with P(N,R) = N! / (N-R)!. We can easily see that when R = N, P(N,R) = N!.

It seems intuitive to extend this subfactorials. Let’s say that the mailman is randomly placing 5 letters into 6 slots. How many ways can the letters be placed so that no letter is in the correct slot? Piggybacking off the factorial/permutation relationship, let’s call this a “subpermutation” and denote it with:

!N(S >= N) = the ways to arrange N numbered items into S numbered slots, with no item in the same slot as its number and no more than 1 item per slot.

We may be tempted to re-use the inclusive terms and sum them from 1 to 6 instead of 1 to 5. However, we have explicitly called out the values that each vertex can take.  We would have to update all of those to include the value 6:

Warning:

This exposes a potential problem with using constants in CPs and summing over a constant – you must make sure that they match exactly. If we have the term (1 - δσ₁{1-7}) and we are summing from 1 to 6, we will get the wrong answer! This is because, to a CP, the numbers aren’t numerical values – they are unique members of a set. The summation operation considers only the size of the set of values, not a list of individual values. The summation assumes the two match.

What if we want to see how many ways there are to derange 5 letters into 7 slots, 8 slots, 9 slots etc.  Instead of rewriting our formula every time, we can use the exclusive terms and sum from 1 to Q:

As mentioned before, the exclusive terms take longer to evaluate because they must be expanded first, resulting in more terms to sum. However, this only needs to be calculated once. Once we have the polynomial, we can apply it to any value:

Here are the first few values for subpermutations of 5 items:

!5(5) = 44 ways to derange 5 letters into 5 slots.

!5(6) = 309 ways to derange 5 letters into 6 slots.

!5(7) = 1214 ways to derange 5 letters into 7 slots.

!5(8) = 3539 ways to derange 5 letters into 8 slots.

!5(9) = 8544 ways to derange 5 letters into 9 slots.

!5(10) = 18089 ways to derange 5 letters into 10 slots.

Note: This subpermutation formula is only valid when S >= N.  For S < N, it returns invalid results.

Of course, we can also calculate subpermutation formulas for other numbers of items:

!1(Q) = Q - 1

!2(Q) = Q² - 3Q + 3

!3(Q) = Q³ -6Q² + 14Q - 13

!4(Q) = Q⁴ - 10Q³ + 41Q² - 84Q + 73

!5(Q) = Q⁵ - 15Q⁴ + 95Q³ - 325Q² + 609Q - 501

!6(Q) = Q⁶ - 21Q⁵ + 190Q⁴ - 965Q³ + 2944Q² - 5155Q + 4051

!7(Q) = Q⁷ - 28Q⁶ + 343Q⁵ - 2415Q⁴ + 10689Q³ - 30023Q² + 49790Q - 37633

This exercise in subfactorials and subpermutations shows us two things:

1)     Using inclusive terms and summing over concrete ranges is faster, but produces only a single concrete solution.

2)     Using exclusive terms takes longer to calculate, but only needs to be done once to produce a general solution that can be reused.

Previous Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 11 – Boolean Satisfiability

I keep touting CPs as a language of logic. Let’s see how well that claim holds up by comparing it to a well-established language of logic, Boolean Satisfiability (or “SAT”).SAT IntroductionA SAT expression is an expression containing multiple Boolean variables, e.g. x1, x2, x3, etc., where each variable can be true or false (often “0” and “1” are used in place of false and true). An expression is satisfiable if there are values for its variables which result in the expression evaluating to true.

Next Post:

Chromatic Polynomials 13 - coming soon