0
$\begingroup$

How many non-ordered quadruples satisfy $a+b+c+d=18$?

I know how to do this if this is ordered quadruples, but in non-ordered quadruples $(1,1,1,15)$ is the same as $(15,1,1,1)$ so you have to account for overcounting. However, you cannot simply divide by $4$! because there are different number of repeated elements in each case. So I am not sure how to proceed.

$\endgroup$
  • $\begingroup$ Your question is equivalent to this one :math.stackexchange.com/questions/169213/… for the case of N=18 and K=4. $\endgroup$ – Micah Apr 7 '14 at 5:57
  • $\begingroup$ @deftfyodor I believe that question you linked to would be equivalent if it was ordered quadruples. I am asking for non-ordered quadruples. $\endgroup$ – 1110101001 Apr 7 '14 at 6:22
4
$\begingroup$

This problem does not have an easy solution and has been explored quite deeply, resulting in some very fascinating results, but I won't go into those too much.

This is equivalent to asking for the number of ways to put $18$ indistinguishable objects into $4$ indistinguishable boxes (which is not easy to solve this way), or the total number of ways to partition $18$ into anywhere between $1$ and $4$ parts (less than $4$ parts implies empty boxes).

The main method I'm showing will be a recursive/summation calculation of the number of partitions, as it is in my opinion and to my knowledge the easiest to both derive and compute, and even this is pretty tedious.


Let $p(n)$ be the number partitions of $n$. Let the number of ways to partition $n$ into $k$ parts be $p_k(n)$.

Assuming you want $a$, $b$, $c$, and $d$ to be positive integers: $p_4(18)$

We can uniquely represent each group of different permutations of a particular quadruple by only counting the one that is ordered from largest to smallest. If we represent these as objects, we can draw diagrams for each partition. For example, this is the diagram for $9 = 4+3+2$: $$ \begin{align} \Box \Box \Box \Box \\ \Box \Box \Box \\ \Box \Box \end{align} $$

Since we're ordering the quadruples from largest to smallest, this means that no row in the diagram should be longer than the ones above it.

Partitioning a number into $k$ parts means we must have $k$ rows, so each row must have at least $1$. If we remove the first of each row, we have a bijection of the general partition of what is left constrained to those rows. In other words, $p_k(n) = \sum\limits_{i=1}^k p_i(n-k)$. Here's the diagram to demonstrate $p_3(9) = \sum\limits_{i=1}^3 p_i(6)$: $$ \begin{align} \Box \Box \Box \blacksquare \\ \Box \Box \blacksquare \\ \Box \blacksquare \end{align} $$

Assuming you want $a$, $b$, $c$, and $d$ to be non-negative integers: $\sum\limits_{i=1}^4 p_i(18) = p_4(22)$

We can break this down further by continuing to chop off these columns to get: $p_k(n) = \sum\limits_{r=1}^{{\lfloor}n/k{\rfloor}} \sum\limits_{i=1}^{k-1} p_i(n-rk)$.

Here are diagrams to visualize $p_3(9) = \sum\limits_{i=1}^2 \Big( p_i(6) + p_i(3) + p_i(0) \Big)$:

$$ \begin{align} \sum\limits_{i=1}^2 p_2(6): \Box \Box \Box \blacksquare \\ \Box \Box \Box \blacksquare \\ \blacksquare \\ \\ \sum\limits_{i=1}^2 p_2(3): \Box \Box \blacksquare \blacksquare \\ \Box \blacksquare \blacksquare \\ \blacksquare \blacksquare \\ \\ \sum\limits_{i=1}^2 p_2(0): \blacksquare \blacksquare \blacksquare \\ \blacksquare \blacksquare \blacksquare \\ \blacksquare \blacksquare \blacksquare \end{align} $$ Last couple of short optimizations: Obviously, $p_k(0) = 1$, $p_1(n) = 1$, $p_n(n) = 1$, and $p_k(n) = 0$ where $k > n$, and it's fairly trivial to show that $p_2(n) = \lfloor\frac{n}{2}\rfloor$.

The number of partitions of an integer $n$ into parts the largest of which is $k$ is equal to the number of partitions of $n$ into exactly $k$ parts. We can easily see this by simply tilting our head clockwise 90 degrees and forming a bijection. $k$ parts counts the rows, and the largest part having $k$ counts the columns.

We can now use what we know to break down $p_4(18)$.

$$ \begin{eqnarray*} p_4(18) &=& \sum\limits_{i=1}^3 \Big( p_i(14) + p_i(10) + p_i(6) + p_i(2) \Big) \\ \sum\limits_{i=1}^3 p_i(2) &=& 2 \\ \sum\limits_{i=1}^3 p_i(6) &=& p_1(6) + p_2(6) + p_3(6) = 1 + 3 + 3 = 7 \\ \sum\limits_{i=1}^3 p_i(10) &=& p_1(10) + p_2(10) + p_3(10) \\ &=& 1 + 5 + \sum\limits_{i=1}^2 \Big( p_i(7) + p_i(4) + p_i(1) \Big) = 6 + 4 + 3 + 1 = 14 \\ \sum\limits_{i=1}^3 p_i(14) &=& p_1(14) + p_2(14) + p_3(14) \\ &=& 1 + 7 + \sum\limits_{i=1}^2 \Big( p_2(11) + p_2(8) + p_2(5) + p_2(2) \Big) = 8 + 6 + 5 + 3 + 2 = 24 \\ p_4(18) &=& 24 + 14 + 7 + 2 = \boxed{47} \end{eqnarray*} $$

You can confirm my results here and read up more about partitions here.

I highly recommend reading through that wiki page, as well as writing a program to calculate these values for you if you have to do more than a couple of these.

EDIT: MJD just posted a very nice clean recursive function that is based off the exact same concept I demonstrated. Go use that if you can.

$\endgroup$
3
$\begingroup$

This is a combinatorics question that is equivalent to asking "How many ways can we place 18 identical balls into 4 identical boxes"? The answer to this is basically the number of ways you can partition the number 18 into 4 parts.

In general, this is a very difficult question, and I'm not sure if it has yet been solved.

$\endgroup$
  • $\begingroup$ Yes, that is exactly what I am asking. So there is no easy way to do this? Do you know of any wikipedia pages/other links that talk about this problem so I can research further? $\endgroup$ – 1110101001 Apr 7 '14 at 6:25
2
$\begingroup$

Define some follow sets

$A=\{(a,b,c,d)\mid 0\le a,b,c,d\le n,\quad a+b+c+d=n\}$ $A_2=\{(a,a,b,c)\mid 0\le a,b,c\le n,\quad a+a+b+c=n\}$ $A_3=\{(a,a,a,b)\mid 0\le a,b\le n,\quad a+a+a+b=n\}$ $A_{22}=\{(a,a,b,b)\mid 0\le a,b\le n,\quad a+a+b+b=n\}$ $A_4=\{(a,a,a,a)\mid 0\le a\le n,\quad a+a+a+a=n\}$

then

$|A|={n+3\choose 3}$

$|A_2|=\left\lfloor\frac{(n+2)^2}{4}\right\rfloor$

$|A_3|=\left\lfloor\frac{n}{3}\right\rfloor+1$

$|A_{22}|=\left(2\left\lfloor\frac{n}{2}\right\rfloor+1-n\right)\left(\frac{n}{2}+1\right)$

$|A_4|=\left\lfloor\frac{n}{4}\right\rfloor-\left\lfloor\frac{n-1}{4}\right\rfloor$

and number of non-ordered quadruples satisfy $a+b+c+d=n$ is $S_n$

$ \displaystyle S_n=\dfrac{|A|+6|A_2|+3|A_{22}|+8|A_3|+6|A_4|}{4!}$

*Example: $n=18$

$|A|={21\choose 3}=1330;\quad |A_2|=\left\lfloor\frac{20^2}{4}\right\rfloor=100;\quad |A_3|=\left\lfloor\frac{18}{3}\right\rfloor+1=7;$

$|A_{22}|=\left(2\left\lfloor\frac{18}{2}\right\rfloor+1-18\right)\left(\frac{18}{2}+1\right)=10;\quad |A_4|=\left\lfloor\frac{18}{4}\right\rfloor -\left\lfloor\frac{17}{4}\right\rfloor=0$

$S_{18}=\dfrac{1330+6.100+3.10+8.7+6.0}{4!}=84$

A001400

$\endgroup$
  • $\begingroup$ $S_{18}=84$ 0,0,0,18; 0,0,1,17; 0,0,2,16; 0,0,3,15; 0,0,4,14; 0,0,5,13; 0,0,6,12; 0,0,7,11; 0,0,8,10; 0,0,9,9; 0,1,1,16; 0,1,2,15; 0,1,3,14; 0,1,4,13; 0,1,5,12; 0,1,6,11; 0,1,7,10; 0,1,8,9; 0,2,2,14; 0,2,3,13; 0,2,4,12; 0,2,5,11; 0,2,6,10; 0,2,7,9; 0,2,8,8; 0,3,3,12; 0,3,4,11; 0,3,5,10; 0,3,6,9; 0,3,7,8; 0,4,4,10; 0,4,5,9; 0,4,6,8; 0,4,7,7; 0,5,5,8; 0,5,6,7; 0,6,6,6; 1,1,1,15; 1,1,2,14; 1,1,3,13; 1,1,4,12; 1,1,5,11; 1,1,6,10; 1,1,7,9; 1,1,8,8; 1,2,2,13; 1,2,3,12; 1,2,4,11; 1,2,5,10; 1,2,6,9; 1,2,7,8; 1,3,3,11; 1,3,4,10; 1,3,5,9; 1,3,6,8; 1,3,7,7; 1,4,4,9; 1,4,5,8; 1,4,6,7; 1,5,5,7; $\endgroup$ – hxthanh Apr 7 '14 at 14:23
  • $\begingroup$ 1,5,6,6; 2,2,2,12; 2,2,3,11; 2,2,4,10; 2,2,5,9; 2,2,6,8; 2,2,7,7; 2,3,3,10; 2,3,4,9; 2,3,5,8; 2,3,6,7; 2,4,4,8; 2,4,5,7; 2,4,6,6; 2,5,5,6; 3,3,3,9; 3,3,4,8; 3,3,5,7; 3,3,6,6; 3,4,4,7; 3,4,5,6; 3,5,5,5; 4,4,4,6; 4,4,5,5. $\endgroup$ – hxthanh Apr 7 '14 at 14:24
2
$\begingroup$

If you do not need a mathematical closed form, there is a simple algorithm to calculate this. Let $P(n, k, m)$ be the number of ways that the integer $n$ can be partitioned into $k$ parts each of size at least $m$. Then we have $$P(n,k,m) = \sum_{i=m}^n P(n-i, k-1, i).$$

The idea here is that since we do not want to count the partitions $18 = 9+6+2+1$ and $18 = 6+2+9+1$ separately, we will require that each partition will be counted only when its parts are in increasing order. So when we form a partition of $18$ into $4$ parts, we must choose some value, say $i$, to be the smallest part. We extract this $i$ from $18$, leaving us with $18-i$. We then want to complete the partition by finding a partition of $18-i$ into 3 parts, each of size at least $i$, so that the parts will be in increasing order. Hence we want $P(18-i, 3, i)$ for each possible initial part $i$ between $m$ (the minimum allowed part size) and $n$ (the obvious maximum).

There are a few base cases for the recursion: $$\begin{align} P(n, 0, m) & = \begin{cases}1, \text{ if $n=0$}\\ 0,\text{ otherwise} \end{cases}\\ P(n, k, m) & = 0 \text{ whenever $n<m$ and $0<k$} \end{align}$$

Then the answer to your question is $P(18,4,1) $, the number of partitions of 18 into exactly 4 parts of size at least 1; the computer tells me this is $47$.

Here is some Haskell code to calculate this function. It would not be much longer in most other languages.

    part n k m
      | k == 0 && n == 0     = 1
      | k == 0 && n > 0      = 0
      | k > 0  && n < m      = 0
      | otherwise            = sum [ part (n-i) (k-1) i | i <- [m..n] ]
$\endgroup$
1
$\begingroup$

The "deep results" cited by @CosmoVibe's answer scare me a bit that the following is dead wrong, but let's take a shot.

As you are interested in the sizes of the parts, you might as well take them as ordered in non-decreasing order. Call the size of partition $k$ $a_k$. The condition that their sizes be non-decreasing means that: \begin{align} a_1: &\quad a_1 \ge 1 \\ a_2: &\quad a_2 \ge a_1 \\ a_3: &\quad a_3 \ge a_2 \\ a_4: &\quad a_4 \ge a_3 \end{align} Define new convenience variables $x_i$: \begin{align} x_1 &= a_1 \\ x_2 &= a_2 - a_1 \\ x_3 &= a_3 - a_2 \\ x_4 &= a_4 - a_3 \end{align} Then we have $x_1 \ge 1$, while the other $x_i \ge 0$. The restriction to have $a_1 + a_2 + a_3 + a_4 = 18$ translates into $4 x_1 + 3 x_2 + 2 x_3 + x_4 = 18$. You can set up this mess as a generating function: $$ [z^{18}] \frac{z^4}{1 - z^4} \cdot \frac{1}{1 - z^3} \cdot \frac{1}{1 - z^2} \cdot \frac{1}{1 - z} = \frac{z^4}{(1 - z)^4 (1 + z)^2 (1 + z^2) (1 + z + z^2)} $$ Certainly not exactly nice, but maxima is up to the task of splitting into partial fractions: \begin{align} \frac{z^4}{1 - z^4} &\cdot \frac{1}{1 - z^3} \cdot \frac{1}{1 - z^2} \cdot \frac{1}{1 - z} \\ &= \frac{1}{24 (1 - z)^4} - \frac{1}{24 (1 - z)^3} - \frac{13}{288 (1 - z)^2} + \frac{1}{32 (1 + z)^2} + \frac{1}{8 (1 + z^2)} - \frac{1}{9 (1 + z + z^2)} \end{align} From here: $$ \frac{1}{24} \binom{-4}{18} (-1)^{18} - \frac{1}{24} \binom{-3}{18} (-1)^{18} - \frac{13}{288} \binom{-2}{18}(-1)^{18} + \frac{1}{32} \binom{-2}{18} + \frac{1}{8} \binom{-1}{9} - \frac{1}{9} [z^{18}] (1 + z + z^2)^{-1} $$ I'll leave the numbers to some brave soul. The last term's denominator can be split using (complex) third roots of 1, or it could be handled as $(1 + z (1 + z))^{-1}$ and a geometric series. The final expression is quite ugly, but doable.

Definitely not easy to generalize...

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.