Day 1: Partridges in a Pear Tree

We can use generating functions.Hence we want coefficient of x^12 in ((x^2+x^3)^2)*((x+x^2+x^3)^5).Now this is straightforward and we get the coefficient as 65.

First give all the partridges $2,2,1,1,1,1,1$ pears each where we let the first two numbers be for the two particularly important partridges. This satisfies conditions 1 and 2.

Now all we need to do is to distribute the final three pears whilst satisfying condition 3. This can be done in three ways:

• Case 1: Give all three to the same partridge

It is clear that this will cause this partridge to have four or more pears, so this case yields $0$ possibilities.

• Case 2: Give two to one partridge and one to another

We can only give two to one of the $5$ partridges with $1$ at the moment (as $2+2=4$ which is not allowed). Then we can give one to any of the remaining partridges, of which there are $6$ . This case yields $30$ possibilities.

• Case 3: Give one each to three partridges

This is equivalent to choosing 3 out of 7 since any combination will work. So this case yields $35$ possibilities.

There are no other cases and so there are $\boxed{65}$ possible distributions of pears.

First a tutorial on the formula for the number of ways of distributing N objects among K people. The formula is by the way ${N+K-1 \choose K-1}$

Start off with K=2 people, and say N=10.

Let's build an equivalence with 10+1=11 slots where one of them is to be chosen to be a partition slot. After choosing a slot to be a partition, the first block of slots belong to the first person, and the second block of slots belong to the second person.

OOOOOOXOOOO, where X marks the partition slot, this corresponds with $N_1$ =6, $N_2$ =4,

Try to see the correspondence between the number of ways to distribute the objects and the number of ways of choosing the slot.

Next we try K=3 people and N=10.

Now imagine there are 10+2=12 slots and you choose two of them to be partition slot. So once you choose the two slots, for example

OOOOOXOOXOOO, where X marks the partition slot, this corresponds with $N_1$ =5, $N_2$ =2, $N_3$ =3

See that there is a one to one correspondence between choosing the partition slots and the number of ways of distribution.

In general for N objects and K people, you begin with N+K-1 slots and you designate K-1 to be partition slots.

Hope this can convince you of the general formula of ${N+K-1 \choose K-1}$

We will use this formula to solve our problem.

Given the first two constraints, namely:

• Every guest must have at least one pear.
• Two of the guests are particularly important, so they both must have at least two pears.

We can see that the initial distribution is like this 2+2+1+1+1+1+1 (+3extra)

For this problem, we can ignore the initial distribution and assume we are dividing 3 pears among 7 guests who has none to begin with. So the formula for this will be ${3+7-1 \choose 7-1}$ = 84.

Now we consider last constraint, we can list out the cases we don't want.

Group1:

4+2+1+1+1+1+1 (+1 extra) [2 of these]

2+4+1+1+1+1+1 (+1 extra)

Group2:

2+2+4+1+1+1+1 (+0 extra) [5 of these]

2+2+1+4+1+1+1 (+0 extra)

2+2+1+1+4+1+1 (+0 extra)

2+2+1+1+1+4+1 (+0 extra)

2+2+1+1+1+1+4 (+0 extra)

For group 1, the number of ways is equivalent to 1 object distributed among 7 people, ${1+7-1 \choose 7-1}$ = 7. We have 2 of these, so 2*7=14 ways.

For group 2, the number of ways is equivalent to 0 object distributed among 7 people, ${0+7-1 \choose 7-1}$ =1 way obviously. We have 5 of these, so 5*1=5 ways.

Finally, the required number of ways will be: 84-14-5=65 ways.

Because I had been recently working on Discrete Optimization Modelling (with MiniZinc) , I will take a different approach here and instead address what we needed to do if we needed to find enlist those solutions.

Here is the relevant MiniZinc model:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int: pears = 12;
int: guests = 7;

array[1..guests] of var 1..pears: distribution;

constraint
  distribution[1] >= 2
  /\
  distribution[2] >= 2
  ;

constraint
  forall(i in 1..guests)(
    distribution[i] < 4
  )
  ;

constraint
  sum(i in 1..guests)(distribution[i]) == 12
  ;

solve satisfy;

Run it with:

1

./mzn-g12fd --all-solutions /tmp/stable_marriage.mzn 

Here are all the solutions.