The Combinatorics of Transistor

Question

The video game Transistor features a very interesting ability system. You collect 16 "Functions" which you can use in 16 different slots. What's interesting is that there are 3 types of slots and every Function behaves differently according to which slot you use it in:

• There are 4 Passive Slots.
• There are 4 Active Slots.
• Each Active Slot has 2 Upgrade Slots.

We want to figure out how many different skill sets that gives us.

However, some combinations are equivalent. In particular, within each of those groups of slots, the specific position of a Function doesn't matter. On the other hand, the effect of a Function in an Upgrade Slot does depend on the specific Function used in the parent Active Slot.

Therefore, using hexadecimal digits to stand in for the Functions, the following combinations are all equivalent:

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    2     0     1     3    # Permutation of passive slots.
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     6     4     7    # Permutation of active slots together
Upgrade Slots:   A B   C D   8 9   E F   # with their upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   B A   C D   F E   # Permutation within upgrade slots.

as well as any combination of these rearrangings. Note that in the third case the Upgrade Slots were swapped along with the Active Slots to maintain the same overall effect.

On the other hand, the following combinations are all different from the above set:

Passive Slots:    4     5     6     7    # Passive slots swapped
Active Slots:     0     1     2     3    # with active slots.
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     4     6     7    # Permutation of active slots without
Upgrade Slots:   8 9   A B   C D   E F   # changing upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 A   9 B   C D   E F   # Permutation between different upgrade slots.

By my count that gives you 2,270,268,000 possible (functionally distinct) combinations, assuming all Functions are used.

If you have less than 16 Functions at your disposal, some of the slots will remain empty. However, note that you can't place a Function in an Upgrade Slot if the parent Active Slot is empty.

The Challenge

You're to determine the number of possible configurations depending on how many functions you have. Furthermore, I will generalise the problem slightly by making the number of slots variable, in order to prevent trivial hardcoding solutions.

Write a program or function which, given two positive integers M ≥ 1 and 1 ≤ N ≤ 4M, determines the number of possible (functionally distinct) skill sets assuming exactly N different Functions are used to fill as many as possible of M Passive, M Active and 2M Upgrade Slots.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Your code must be able to handle any input up to and including M = 8 within one minute on a reasonable desktop machine. There is some leeway in this, but it should rule out brute force solutions. In principle it should be no issue to solve any of those inputs in less than a second.

This is code golf, the shortest answer (in bytes) wins.

Test Cases

Each test case is in the form M N => Result.

1 1 => 2
1 2 => 4
1 3 => 9
1 4 => 12
2 1 => 2
2 2 => 6
2 3 => 21
2 4 => 78
2 5 => 270
2 6 => 810
2 7 => 1890
2 8 => 2520
3 1 => 2
3 2 => 6
3 3 => 23
3 4 => 98
3 5 => 460
3 6 => 2210
3 7 => 10290
3 8 => 44520
3 9 => 168840
3 10 => 529200
3 11 => 1247400
3 12 => 1663200
4 1 => 2
4 2 => 6
4 3 => 23
4 4 => 100
4 5 => 490
4 6 => 2630
4 7 => 14875
4 8 => 86030
4 9 => 490140
4 10 => 2652300
4 11 => 13236300
4 12 => 59043600
4 13 => 227026800
4 14 => 718918200
4 15 => 1702701000
4 16 => 2270268000
5 1 => 2
5 2 => 6
5 3 => 23
5 4 => 100
5 5 => 492
5 6 => 2672
5 7 => 15694
5 8 => 98406
5 9 => 644868
5 10 => 4306932
5 11 => 28544670
5 12 => 182702520
5 13 => 1101620520
5 14 => 6122156040
5 15 => 30739428720
5 16 => 136670133600
5 17 => 524885961600
5 18 => 1667284819200
5 19 => 3959801445600
5 20 => 5279735260800
6 1 => 2
6 2 => 6
6 3 => 23
6 4 => 100
6 5 => 492
6 6 => 2674
6 7 => 15750
6 8 => 99862
6 9 => 674016
6 10 => 4787412
6 11 => 35304654
6 12 => 265314588
6 13 => 1989295308
6 14 => 14559228684
6 15 => 101830348620
6 16 => 667943115840
6 17 => 4042651092480
6 18 => 22264427465280
6 19 => 110258471363040
6 20 => 484855688116800
6 21 => 1854067032417600
6 22 => 5894824418683200
6 23 => 14025616720315200
6 24 => 18700822293753600
7 1 => 2
7 2 => 6
7 3 => 23
7 4 => 100
7 5 => 492
7 6 => 2674
7 7 => 15752
7 8 => 99934
7 9 => 676428
7 10 => 4849212
7 11 => 36601554
7 12 => 288486132
7 13 => 2349550632
7 14 => 19504692636
7 15 => 162272450340
7 16 => 1328431104000
7 17 => 10507447510560
7 18 => 78942848624640
7 19 => 554967220167360
7 20 => 3604592589998400
7 21 => 21411337810262400
7 22 => 115428212139240000
7 23 => 561247297649438400
7 24 => 2439121536313862400
7 25 => 9283622495827680000
7 26 => 29520583763711040000
7 27 => 70328449554723360000
7 28 => 93771266072964480000
8 1 => 2
8 2 => 6
8 3 => 23
8 4 => 100
8 5 => 492
8 6 => 2674
8 7 => 15752
8 8 => 99936
8 9 => 676518
8 10 => 4852992
8 11 => 36722169
8 12 => 291621462
8 13 => 2418755196
8 14 => 20834571186
8 15 => 184894557705
8 16 => 1672561326150
8 17 => 15217247948760
8 18 => 137122338089880
8 19 => 1204392465876600
8 20 => 10153538495100000
8 21 => 81007229522419200
8 22 => 604136189949692400
8 23 => 4168645459350372000
8 24 => 26403795950145213600
8 25 => 152700324078982680000
8 26 => 803784718213396920000
8 27 => 3838761204861983400000
8 28 => 16503742828841748480000
8 29 => 62545434470667308160000
8 30 => 198853691115980300400000
8 31 => 474189571122722254800000
8 32 => 632252761496963006400000

These are all the inputs your code has to handle within one minute (each), but it should in principle work for larger inputs. You can use some of the following M = 10 test cases to check that:

10 1 => 2
10 2 => 6
10 3 => 23
10 4 => 100
10 5 => 492
10 6 => 2674
10 7 => 15752
10 8 => 99936
10 9 => 676520
10 10 => 4853104
10 11 => 36727966
10 12 => 291849866
10 13 => 2426074222
10 14 => 21033972388
10 15 => 189645995396
10 16 => 1773525588406
10 17 => 17155884420532
10 18 => 171073929494468
10 19 => 1750412561088334
10 20 => 18258387148774916
10 21 => 192475976310317700
10 22 => 2028834600633220380
10 23 => 21127206177119902860
10 24 => 214639961631544809360
10 25 => 2101478398293813739200
10 26 => 19602967930531817832000
10 27 => 172444768103233181556000
10 28 => 1417975382888905296456000
10 29 => 10820259026484304813416000
10 30 => 76213534343700480310584000
10 31 => 493916052421168703366040000
10 32 => 2941900199368102067135040000
10 33 => 16113144277547868007416960000
10 34 => 81222252655277786422930560000
10 35 => 376309102059179385262246080000
10 36 => 1589579966324953534441910400000
10 37 => 5981477408861097281112374400000
10 38 => 19005991357166148698688124800000
10 39 => 45381652832417130566255318400000
10 40 => 60508870443222840755007091200000

Answer 1

CJam (56 bytes)

q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+

Online demo

This is an optimised version of the reference implementation I wrote for the sandbox. Note: I use N in the code because in a Real Combinatorics Question™ the parameters are \$n\$ and \$k\$, not m and n, but I'll use \$M\$ and \$N\$ in the explanation to avoid further confusion.

Suppose that we assign \$X\$ functions to the passive slots (where obviously \$0 \le X \le M\$). Then we have \$N-X\$ functions left for the active + upgrade slots (and we can choose those functions in \$\frac{N!}{X!(N-X)!}\$ ways). Because the order of the slot constellations is irrelevant, we want to consider each partition of \$N-X\$ into at most \$M\$ parts each of at most \$3\$ exactly once.

Take partition \$λ_0, λ_1, \ldots, λ_k\$. We can assign \$λ_0\$ parts to the first slot constellation, \$λ_1\$ to the second, etc. in \$\frac{(N-X)!}{λ_0! λ_1! ... λ_k!}\$ ways (multinomial), but we need to compensate for two factors. Firstly, if we have \$λ_i = λ_j\$ then the constellations are interchangeable, so we further divide by the factorials of the multiplicities of each part, \$μ_i\$. (E.g. the partition 3 2 2 1 has \$μ_3 = 1\$, \$μ_2 = 2\$, \$μ_1 = 1\$). Secondly, we have a designated "active" slot in each constellation, so for each \$λ_i\$ we multiply by \$λ_i\$ ways to select the active function.

So for each partition the number of distributions of functions is

$$\frac{N!}{X! (λ_0-1)! \ldots (λ_k-1)! μ_1! μ_2! μ_3!}$$

The code above computes the partitions using the same approach as Dennis (it's obvious and short, although not very scalable) and then processes each partition into an array similar to [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3] over which it can lift the factorial function and then fold division.

Answer 2

CJam, 74 67 bytes

q~4@:Mm*:$L|{:+W$\-M),&},f{0-:F1@@{_m!\I-:Nm!/I(m!/*N}fI;Fm!Fe=/}:+

I've verified all test cases on my desktop computer using the Java interpreter. This took 2.2 seconds for 1 ≤ M ≤ 8 and 3.5 minutes for M = 10.

Try this fiddle in the CJam interpreter or verify the first 84 test cases at once.

Idea

In principle, we can fill each active slot and its corresponding upgrade slots with 0, 1, 2 or 3 functions. For 4M slots in total, we take all vectors V of {0, 1, 2, 3}^M and filter out those for which sum(V) > N (more functions in non-passive slots than total functions available) or sum(V) + M < N (not enough passive slots for non-active functions). We sort and deduplicate all kept vectors, since the order of the slot families in not important.

With N functions and V = (x₁, …, x_M) functions in the non-passive parts of the slot families, we calculate the number of combinations as follows:

1. If x₁ = 0, there is only one possibility for that slot family.

   If x₁ = 1, there are N possibilities, since we have N functions, and the function must go in the active slot.

   If x₁ = 2, we must place one function in the active slot and another in an upgrade slot (it doesn't matter which). There are N choices for the active slot and N-1 remaining choices for the upgrade slot, giving a total of N(N-1) combinations.

   If x₁ = 3, there are N choices for the active slot, N - 1 remaining choices for the first upgrade slot and N - 2 for the second upgrade slot. Since the upgrade slots have no order, this counts every combination twice, so there are N(N - 1)(N - 2) unique combinations.

   In any case, there are N! / ((N - x₁)! × (x₁ - 1)! combinations for this family.

2. We have used up x₁ functions, so set N := N - x₁ and repeat step 1 for x₂, then x₃, etc.

3. If V contains duplicates, the product of the above results will have counted all combinations multiple times. For each unique element of V, if it occurs r times in V, there are r! equivalent ways to arrange these slot families, so the result from above must be devided by r!.

4. The final result is the number of unique combinations for that V.

To calculate the total number of unique combinations, all that's left to do is to compute the sum of the results for each V.

Code

q~        e# Read an evaluate all input from STDIN. Pushes M and N.
4@:M      e# Push 4, rotate the M, and formally save it in M.
m*        e# Push {0, 1, 2, 3}^M.
:$        e# Sort each vector.
L|        e# Perform set union with the empty list (deduplicates).
{         e# For each sorted vector:
  :+      e#   Compute the sum of its coordinates.
  W$\-    e#   Subtract the sum from N (bottom of the stack).
  M),&    e#   Push [0 ... M] and intersect.
},        e# If the intersection was not empty, keep the vector.
f{        e# For each kept vector, push N and V; then:
  0-:F    e#   Save the non-zero elements of V in F.
  1@@     e#   Push 1 (accumulator), and rotate N and F on top of it.
  {       e#   For each I in F:
    _m!   e#     Push I and push factorial(I).
    \I-:N e#     Subtract I from N and update N.
    m!/   e#     Divide factorial(N) (original N) by factorial(N) (updated N).
    I(m!/ e#     Divide the quotient by factorial(I - 1).
    *     e#    Multiply the accumulator by the resulting quotient.
    N     e#    Push N for the next iteration.
  }fI     e#
  ;       e#   Pop N.
  Fm!     e#   Push all non-unique permutations of F.
  Fe=     e#   Count the number of times F appears.
  /       e#   Divide the accumulator by the result.
}         e#
:+        e# Add all resulting quotients.