
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 6th, 2016, 09:44 PM  #1 
Newbie Joined: Mar 2016 From: Alabama Posts: 18 Thanks: 0  Permutations problem
There is a box containing n marbles. At each move, we are allowed to take 1 to n marbles from the box. Following how many paths in total can we reach any of the possible combinations of marbles in the box? That is, the number of ways to reach 0 marbles + ways to reach 1 marble + ... + ways to reach n marbles (only one way: zero moves). Also, each marble has a unique color, so taking the red marble counts as a different move from taking the green marble even though only 1 marble is taken in either move (Edit: This also makes the combinations unique. The box having only the red marble in it has a different combination of marbles from having only the green marble). Is this actually solvable? Is there even a formula for a sum of permutations? Last edited by zambod; March 6th, 2016 at 09:59 PM. 
March 7th, 2016, 03:22 PM  #2 
Newbie Joined: Dec 2015 From: Connecticut Posts: 21 Thanks: 4 Math Focus: I love to hate all of them equally 
It can be solved, but I wasn't able to do it without a really messy summation. There is a lot more to this problem than just sums of permutations because the permutations may be split among several moves. Here is my solution and (hopefully correct) answer: Set $\displaystyle k$ as the number of marbles that we wish to remove from the box. There are $\binom {n}{k}$ unordered ways to choose these $\displaystyle k$ marbles. Consider our $\displaystyle k$ removed marbles as an ordered sequence, where $\displaystyle a_{i}$ is the $\displaystyle i^{th}$ member of $\displaystyle k$. $\displaystyle k = <a_{1},a_{2},a_{3},...,a_{k}>$ Set $\displaystyle b$ as the number of moves taken to remove our $\displaystyle k$ marbles. We are given the freedom to select any value from $\displaystyle 1$ to $\displaystyle k$ each move. However, we must choose each of the $\displaystyle k$ marbles at some point. Create another sequence, called $\displaystyle c$, also of length $\displaystyle k$. $\displaystyle c = <c_{1},c_{2},c_{3},...,c_{k}>$ Define the removal function $\displaystyle f$ such that the output is the move at which the input is removed: $\displaystyle f(a_{i}) = c_{i}$. For example, if $\displaystyle c_{3} = 5$, then the third marble is taken from the box in the fifth move. Note that all values $\displaystyle 1, 2, 3, … , b$ must appear in $\displaystyle c$ at least once. (Should a value not appear in $\displaystyle c$, then no marbles were taken from the box on that move, which violates the condition that we must remove $\displaystyle 1$ to $\displaystyle n$ marbles each turn.) The purpose of all this alphabet soup has been to metamorphose the problem into something more palpable: instead of removing marbles from boxes, we now are constructing a sequence $\displaystyle c$. Both actions are entirely equivalent. To recap, here are the requisite properties of $\displaystyle c$: • It must have exactly $\displaystyle k$ elements. • All elements must be natural numbers from $\displaystyle 1$ to $\displaystyle b$. • Each natural number from $\displaystyle 1$ to $\displaystyle b$ must appear at least once. • Changing any of the values $\displaystyle c_{1}, c_{2}, c_{3}, … , c_{k}$ yields an entirely distinct path of removal, and must be counted as a separate set of moves. The goal of the problem is to count how many ways we can build $\displaystyle c$, and then multiply that by the amount of ways we can choose $\displaystyle k$. Start off by thinking of $\displaystyle c$ as a sequence of $\displaystyle k$ empty slots. To construct $\displaystyle c$ we must fill in the slots in a manner that satisfies the aforementioned requirements. Start by distributing each value of $\displaystyle 1, 2, 3, … , b$ to the empty slots. There are $\displaystyle k$ available slots for $\displaystyle 1$. There are $\displaystyle k1$ available slots for $\displaystyle 2$. There are $\displaystyle k2$ available slots for $\displaystyle 3$. This continues until we reach $\displaystyle b$, for which there are $\displaystyle kb+1$ slots. The total number of ways to distribute $\displaystyle 1, 2, 3, … , b$ into $\displaystyle c$ is $\displaystyle k(k1)(k2) … (kb+1)$, or $\displaystyle \frac{k!}{(kb)!}$. There are now $\displaystyle kb$ empty slots in $\displaystyle c$. Each of these $\displaystyle kb$ empty slots can be filled with ANY of the values from $\displaystyle 1, 2, 3, … , b$, and an entirely new sequence will be produced. There are $\displaystyle b$ options for the first empty slot, $\displaystyle b$ for the second, $\displaystyle b$ for the third, and so on for all $\displaystyle kb$ empty slots. Therefore, there are $\displaystyle b^{kb}$ distinct ways to complete the sequence $\displaystyle c$. Ultimately, for a given $\displaystyle b$ and $\displaystyle k$, there are $\displaystyle \frac{k!b^{kb}}{(kb)!}$ ways to construct $\displaystyle c$. However, $\displaystyle b$ can take on any value from $\displaystyle 1$ to $\displaystyle k$. We must make a summation of $\displaystyle b$ from $\displaystyle 1$ to $\displaystyle k$ to account for all values of $\displaystyle b$ (this is the nasty summation I referred to in the introduction). We also must account for not only the different values of $\displaystyle k$, but the different ways in which marbles can be chosen for removal. Removing blue and green marbles yields the same $\displaystyle k$ as removing red and yellow marbles, but will ultimately need to be counted separately because they require different paths down the decision tree. Recall from the beginning that there are $\displaystyle \binom {n}{k}$ ways of selecting our $\displaystyle k$ marbles. Multiply the nasty summation by this binomial coefficient. To account for all possible values of $\displaystyle k$, we must take a summation of $\displaystyle k$ from $\displaystyle 1$ to $\displaystyle n$. Our final answer (with an unevaluated summation) looks like this: $\displaystyle \sum_{k=1}^{n} \binom{n}{k} \sum_{b=1}^{k} \frac{k!b^{kb}}{(kb)!}$ Don’t know how to evaluate the summation. Does anybody else? 

Tags 
permutations, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Permutations/combinatorics problem  Sal98  Advanced Statistics  4  June 25th, 2015 10:18 AM 
Problem Solving With Permutations  koolkidx45  Advanced Statistics  1  February 20th, 2012 09:29 AM 
Probability, combinatorics, permutations problem  MasterOfDisaster  Probability and Statistics  3  April 10th, 2011 03:01 PM 
A problem regarding Permutations n Combinations  hello2413  Advanced Statistics  2  March 20th, 2010 10:36 AM 
A problem regarding Permutations n Combinations  hello2413  Number Theory  0  December 31st, 1969 04:00 PM 