4
$\begingroup$

Consider the set $A = [a,b,c,d,e,f,g,h] = [1,2,3,4,5,6,7,8]$.

Find the number of permutations of $A$ that satisfy the equation:

$$a + 2b + 3c + 4d + 5e + 6f+ 7g + 8h = 160$$

No computer allowed.

Note: The question is based on the (unsolved) n. 344 problem - recreational math contest corner - "Sapere" magazine - Hoepli editions - year 1938 - printed in Italy. Nowadays,if we want the result,a computer instantly gives correctly 1066 permutations. A math value or interest of the question, I think, is to find an elementary way to enumerate the permutations that solve the equation, only using permutations's properties or combinatoric techniques. Early days' matter?

$\endgroup$
  • 1
    $\begingroup$ Could you explain how you asked this question without a computer? :P (Seriously, though--we like to see questions where the questioner has documented their effort in the question statement. Please edit your post to include your own work.) $\endgroup$ – apnorton Apr 29 '14 at 13:58
  • 1
    $\begingroup$ You don't need a computer to check every case. $\endgroup$ – evil999man Apr 29 '14 at 14:08
  • $\begingroup$ Are all a,b... distinct? $\endgroup$ – evil999man Apr 29 '14 at 14:16
  • 2
    $\begingroup$ Whoever voted to close this question because “it does not appear to be about math” should be ashamed of themselves. $\endgroup$ – MJD Apr 29 '14 at 14:16
  • 3
    $\begingroup$ You may not be aware, but the custom on this site is to phrase questions as questions ("How many permutations satisfy..." or "How can we count the number of permutations that..."). Many users find it impolite to ask questions in the imperative mood ("Find the number of..."). Moreover, it gives the impression that the problem here has merely been transcribed from somewhere else. $\endgroup$ – Carl Mummert May 4 '14 at 18:00
4
$\begingroup$

For the record I would like to point out that this problem has a solution using multiset cycle indices. Suppose we have $q$ distinct positive integer values $\{v_k\}_{k=1}^q$ and a set of multiplicities $\{b_k\}_{k=1}^q$ and we want to know how many permutations $\pi$ solve the equation $$\sum_{k=1}^q v_{\pi(k)} b_k = n$$ then the answer is given by the coefficient of a subsituted multiset cycle index $$[z^n] \mathfrak{M}_{b_1, b_2, \ldots b_k} \left(\sum_{k=1}^q z^{v_k}\right).$$

In your particular case you want the value $$[z^{160}] \mathfrak{M}_{1,2,3,\ldots 8}(z+z^2+z^3+\cdots+z^8).$$

These cycle indices can be calculated at a lower cost complexity (considerably lower) than iterating over all $q!$ permutations. Learn more at this link introducing multiset cycle indices.

Addendum Thu May 1 21:24:10 CEST 2014. I am adding material to this question on request (personal communication).

A conjecture (I). The sequence of the number of terms in the substituted cycle index for the problem where the multiplicities are $1,2,\ldots q$ before coefficient extraction is $$1, 2, 4, 11, 21, 36, 57, 85, 121,\ldots$$ which is OEIS A126972 and has closed form $$1+{q+1\choose 3}$$ This is extremely good news since the count is polynomial in $q$ (cubic) as opposed to $q!.$ Actually thinking about it we see that this formula represents the fact that $$\sum_{k=1}^q k^2 - \sum_{k=1}^q k (q+1-k) = {q+1\choose 3}.$$

A conjecture (II). On the other hand the number of terms in the cycle index for the operator $\mathfrak{M}_{1,2,\ldots, q}$ gives the sequence $$1, 2, 5, 13, 36,\ldots$$ which does not have enough terms to be identified (there is a challenge for the reader!). The number of terms in the cycle index being bound by the partition function we can nonetheless affirm that its growth is asymptotically strictly less than $q!.$ (Remark, added later: this number does not require the actual cycle index coefficients to be calculated, but only a count of partition shapes derivable from $[1,2,3,\ldots,q]$, which is easy, consult the OEIS hit below.)

Example. We do the case $q=4$ in order to make it easier to understand what is going on. The cycle index of the multiset operator $\mathfrak{M}_{1,2,3,4}$ is given by $$a_{{1}}a_{{2}}a_{{3}}a_{{4}}-a_{{1}}a_{{2}}a_{{7}}-a_{{1}}a_{{3}}a_{{6}}-a_ {{1}}a_{{4}}a_{{5}}-a_{{2}}a_{{3}}a_{{5}}-a_{{2}}{a_{{4}}}^{2}-{a_{{3}}}^{2 }a_{{4}}+2\,a_{{1}}a_{{9}}\\+2\,a_{{2}}a_{{8}}+3\,a_{{3}}a_{{7}}+3\,a_{{4}}a_ {{6}}+{a_{{5}}}^{2}-6\,a_{{10}}.$$ Substituting $z+z^2+z^3+z^4$ into this cycle index we obtain $$ \left( {z}^{4}+{z}^{3}+{z}^{2}+z \right) \left( {z}^{8}+{z}^{6}+{z}^{4}+{ z}^{2} \right) \left( {z}^{12}+{z}^{9}+{z}^{6}+{z}^{3} \right) \left( {z} ^{16}+{z}^{12}+{z}^{8}+{z}^{4} \right) \\- \left( {z}^{4}+{z}^{3}+{z}^{2}+z \right) \left( {z}^{8}+{z}^{6}+{z}^{4}+{z}^{2} \right) \left( {z}^{28}+{ z}^{21}+{z}^{14}+{z}^{7} \right) \\- \left( {z}^{4}+{z}^{3}+{z}^{2}+z \right) \left( {z}^{12}+{z}^{9}+{z}^{6}+{z}^{3} \right) \left( {z}^{24}+ {z}^{18}+{z}^{12}+{z}^{6} \right) \\- \left( {z}^{4}+{z}^{3}+{z}^{2}+z \right) \left( {z}^{16}+{z}^{12}+{z}^{8}+{z}^{4} \right) \left( {z}^{20} +{z}^{15}+{z}^{10}+{z}^{5} \right) \\- \left( {z}^{8}+{z}^{6}+{z}^{4}+{z}^{2} \right) \left( {z}^{12}+{z}^{9}+{z}^{6}+{z}^{3} \right) \left( {z}^{20}+ {z}^{15}+{z}^{10}+{z}^{5} \right) \\- \left( {z}^{8}+{z}^{6}+{z}^{4}+{z}^{2} \right) \left( {z}^{16}+{z}^{12}+{z}^{8}+{z}^{4} \right) ^{2}\\- \left( {z} ^{12}+{z}^{9}+{z}^{6}+{z}^{3} \right) ^{2} \left( {z}^{16}+{z}^{12}+{z}^{8} +{z}^{4} \right) \\+2\, \left( {z}^{4}+{z}^{3}+{z}^{2}+z \right) \left( {z}^ {36}+{z}^{27}+{z}^{18}+{z}^{9} \right) \\+2\, \left( {z}^{8}+{z}^{6}+{z}^{4}+ {z}^{2} \right) \left( {z}^{32}+{z}^{24}+{z}^{16}+{z}^{8} \right) \\+3\, \left( {z}^{12}+{z}^{9}+{z}^{6}+{z}^{3} \right) \left( {z}^{28}+{z}^{21}+ {z}^{14}+{z}^{7} \right)\\ +3\, \left( {z}^{16}+{z}^{12}+{z}^{8}+{z}^{4} \right) \left( {z}^{24}+{z}^{18}+{z}^{12}+{z}^{6} \right) \\+ \left( {z}^{ 20}+{z}^{15}+{z}^{10}+{z}^{5} \right) ^{2}\\ -6\left(z^{40}+z^{30}+z^{20}+z^{10}\right).$$ Expanding this cycle index we obtain the generating function $${z}^{30}+3\,{z}^{29}+{z}^{28}+4\,{z}^{27}+2\,{z}^{26}+2\,{z}^{25}+2\,{z}^{ 24}+4\,{z}^{23}+{z}^{22}+3\,{z}^{21}+{z}^{20}$$ where $dz^p$ represents the fact that the value $p$ was obtained as a solution $d$ times.

Addendum, part II. Re-writing some software of mine I was able to compute the multiset cycle index for the operator $\mathfrak{M}_{1,2,3,4,5,6}$ and get another value for the sequence of terms in the cycle index, obtaining $$ 1, 2, 5, 13, 36, 109,\ldots$$ This gave a perfect match with OEIS A066723. The OEIS entry just repeats the definition from our problem above and does not give asymptotics which we leave to the reader (looks like an interesting challenge). This multiset cycle index gives the generating function for $q=6$ which is $${z}^{91}+5\,{z}^{90}+6\,{z}^{89}+9\,{z}^{88}+16\,{z}^{87}+12\,{z}^{86}+14\,{z}^ {85}+24\,{z}^{84}+20\,{z}^{83}+21\,{z}^{82}\\+23\,{z}^{81}+28\,{z}^{80}+24\,{z}^{ 79}+34\,{z}^{78}+20\,{z}^{77}+32\,{z}^{76}+42\,{z}^{75}+29\,{z}^{74}+29\,{z}^{ 73}\\+42\,{z}^{72}+32\,{z}^{71}+20\,{z}^{70}+34\,{z}^{69}+24\,{z}^{68}+28\,{z}^{ 67}+23\,{z}^{66}+21\,{z}^{65}\\+20\,{z}^{64}+24\,{z}^{63}+14\,{z}^{62}+12\,{z}^{ 61}+16\,{z}^{60}+9\,{z}^{59}+6\,{z}^{58}+5\,{z}^{57}+{z}^{56}.$$

$\endgroup$
2
$\begingroup$

Here is another way of going about the task.

The maximum value of the sum is $$1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2=204$$ and the target value is $44$ less than this.

A transposition switching $a$ and $b$ reduces the total by $$a^2+b^2-ab-ba=\frac 12\left((a-b)^2+(b-a)^2\right)[=(a-b)^2]$$ Note we want the first form here and not the simplest, as will appear later.

The $3$-cycle $(abc)$ reduces the total by $$a^2+b^2+c^2-ab-bc-ca=\frac 12\left((a-b)^2+(b-c)^2+(c-a)^2\right)$$ and $(abcd)$ by $$\frac 12\left((a-b)^2+(b-c)^2+(c-d)^2+(d-a)^2\right)$$and now the pattern is clear.

So we are first looking for decompositions of $2\cdot 44=88$ into sums of up to eight squares, the greatest of which is $\leq49$, and then converting the sum of squares into a cycle decomposition, if possible.

So, for example $88=5\cdot 4^2+2\cdot 2^2$, giving us $7$ squares, which in theory allows a decomposition as a $2$-cycle and a $5$-cycle - but we can't have a $5$-cycle where all the elements have the same parity. The other alternatives are $3,4$ and $2,2,3$. The $3$-cycle is constrained to have differences $2,2,4$ and is all odd or all even - i.e. $(1,3,5), (2,4,6), (3,5,7), (4,6,8)$. The remaining part has to provide four differences equal to $4$ and this is only possible with two transpositions $(1,5)(3,7)$ if the $3$-cycle contains even numbers and $(2,6)(4,8)$ otherwise. [correction] Note that the inverses of the four three cycles also work. So this decomposition gives us eight possible permutations.

It is now a question of being systematic, as there are only a few possibilities.


Looking at a simpler example $$a+2b+3c+4d=27$$ the greatest possible sum is $1+4+9+16=30$ the difference is $3$ so we are looking at up to four squares which sum to $2\cdot 3=6$. The only possibility is $1+1+4$ representing differences of $1,1,2$.

We now need to divide this into two subsets with the same sum - $1+1=2$. This is because we start on one number, have some ups and downs and end back where we started. So the ups have to equal the downs. Three squares means a $3$-cycle. The $2$ is either $|3-1|$ or $|4-2|$. So we have the cycles $(312), (132), (423), (243)$. It depends which way you are used to reading cycles, but the solutions are then $(2,3,1,4), (3,1,2,4), (1,3,4,2), (1,4,2,3)$

__

Note also that the number of cases for the original problem is intermediate for doing this by hand. The number of odd squares is a multiple of four. I get (to illustrate some of the complexities - care is required):

$7,6,1,1,1$ with $7+1=6+1+1$ representing a $5$-cycle and $7=6+1; 1=1$ representing a $3$-cycle and a transposition. The first of these requires differences of $6$ and $7$ so $8\to 1\to 7$ or $1\to 8\to 2$ or the reverse, and the differences of $1$ don't fit in to make a cycle, so you need the transposition e.g. $(34)$

$7,5,3,2,1$ with $7+2=5+3+1$ ($5$-cycle e.g. $(18354)$ - others are possible)

$7,5,3,1,1,1,1,1$ with $7+3=5+1+1+1+1+1$: $7+1+1+1=5+3+1+1$: $7+1+1=5+3+1;1=1$: $7+1=5+3;1=1;1=1$ (this is a four-cycle and two transpositions of adjacent numbers e.g. $(1856)(??)(??)$ but nothing goes with $7$ or $(1834)(??)(??)$ and nothing goes with $2$ so no solution)

$7,5,2,2,2,1,1$ with $7+2+1=5+2+2+1$: $7+2=5+2+2; 1=1$: $7+1=5+2+1; 2=2$: $7=5+2;2+1=2+1$: $7=5+2; 2=2; 1=1$

Taking $7=5+2; 2+1=2+1$ we have a 3-cycle and a 4-cycle. $7=|8-1|$ is the only possibility, so we have $(186), (183), (813), (816)$ and taking the first of these we need to realise the $1+2=1+2$ note that $7$ can't fit into this pattern , so $2$ has to go somewhere (+1 or +2) and so we get $(2354)$ or $(2453)$, and similarly for the others.

$7,4,4,2,1,1,1$ gives $7+2+1=4+4+1+1$ (from which $2=1+1$ or $1=1$ can be extracted) and $7+1+1+1=4+4+2$ e.g. for this last $(1867345)$ or $(1845673)$ (not exhaustive)

My full list is (copying screwed the spacing) - I'm adding [n] to show the number I've found of each type (corrections welcome):

$$ \begin{array}{ccccccccl} 7 & 6 & 1 & 1 & 1 & & & & \text{[16]} \\ 7 & 5 & 3 & 2 & 1 & & & & \text{[10]} \\ 7 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & \text{[4]} \\[2ex] 7 & 5 & 2 & 2 & 2 & 1 & 1 & & \text{[28]} \\[2ex] 7 & 4 & 4 & 2 & 1 & 1 & 1 & & \text{[32]} \\ 7 & 4 & 3 & 3 & 2 & 1 & & & \\ 7 & 4 & 3 & 2 & 2 & 2 & 1 & 1 & \\[2ex] 7 & 3 & 3 & 3 & 3 & 1 & 1 & 1 & \\[2ex] 7 & 3 & 3 & 3 & 2 & 2 & 2 & & \\ 6 & 6 & 4 & & & & & & \text{(impossible)} \\ 6 & 6 & 3 & 2 & 1 & 1 & 1 & & \\ 6 & 6 & 2 & 2 & 2 & 2 & & & \text{[8]} \\ 6 & 5 & 5 & 1 & 1 & & & & \text{(impossible)} \\ 6 & 5 & 4 & 3 & 1 & 1 & & & \\ 6 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & \\[2ex] 6 & 5 & 3 & 3 & 3 & & & & \text{(clearly impossible mod $3$)} \\ 6 & 5 & 3 & 3 & 2 & 2 & 1 & & \\ 6 & 4 & 4 & 4 & 2 & & & & \text{[16]} \\ 6 & 4 & 4 & 4 & 1 & 1 & 1 & 1 & \\[2ex] 6 & 4 & 4 & 3 & 3 & 1 & 1 & & \\ 6 & 4 & 4 & 2 & 2 & 2 & 2 & 2 & \\[2ex] 6 & 4 & 3 & 3 & 3 & 3 & & & \text{(impossible)} \\ 6 & 4 & 3 & 3 & 3 & 2 & 2 & 1 & \\[2ex] 5 & 5 & 5 & 3 & 2 & & & & \text{[20]} \\ 5 & 5 & 5 & 3 & 1 & 1 & 1 & 1 & \\[2ex] 5 & 5 & 4 & 4 & 2 & 1 & 1 & & \\ 5 & 5 & 4 & 3 & 3 & 2 & & & \\[2ex] 5 & 5 & 4 & 3 & 2 & 2 & 2 & 1 & \\[2ex] 5 & 5 & 3 & 3 & 3 & 3 & 1 & 1 & \\[2ex] 5 & 4 & 4 & 4 & 3 & 2 & 1 & 1 & \\[2ex] 5 & 4 & 4 & 3 & 3 & 3 & 2 & & \\ 5 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & \\[2ex] 4 & 4 & 4 & 4 & 4 & 2 & 2 & & \text{[8]} \\[2ex] \end{array} $$

$\endgroup$
  • $\begingroup$ I have tried formatting your table. Please give it a quick check for obvious errors. $\endgroup$ – MJD May 5 '14 at 14:26
  • $\begingroup$ @MJD Thanks. If I spot anything I'll correct it. $\endgroup$ – Mark Bennet May 5 '14 at 14:32
1
$\begingroup$

What is the coefficient of $x^{160}$ in $(\sum_{i=1}^{8}x^i)^{36}$?

Note that $36=\sum_{i=1}^{8} i$

Further hints: hover to see.

Use formula for $GP$ and taylor expansion of denominator.

$\endgroup$
  • $\begingroup$ Are you sure this doesn't overcount? AFAICT this might include terms corresponding to such solutions where one of the variables is zero, or $>8$, or some are equal? $\endgroup$ – Jyrki Lahtonen May 4 '14 at 16:31

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.