My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum

Thanks Tree1Thanks
  • 1 Post By Brachydactyloid
LinkBack Thread Tools Display Modes
March 6th, 2016, 08:44 PM   #1
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 08:59 PM.
zambod is offline  
March 7th, 2016, 02:22 PM   #2
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 k-1$ available slots for $\displaystyle 2$. There are $\displaystyle k-2$ available slots for $\displaystyle 3$. This continues until we reach $\displaystyle b$, for which there are $\displaystyle k-b+1$ slots. The total number of ways to distribute $\displaystyle 1, 2, 3, … , b$ into $\displaystyle c$ is $\displaystyle k(k-1)(k-2) … (k-b+1)$, or $\displaystyle \frac{k!}{(k-b)!}$.

There are now $\displaystyle k-b$ empty slots in $\displaystyle c$.

Each of these $\displaystyle k-b$ 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 k-b$ empty slots. Therefore, there are $\displaystyle b^{k-b}$ distinct ways to complete the sequence $\displaystyle c$.

Ultimately, for a given $\displaystyle b$ and $\displaystyle k$, there are $\displaystyle \frac{k!b^{k-b}}{(k-b)!}$ 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^{k-b}}{(k-b)!}$

Don’t know how to evaluate the summation. Does anybody else?
Thanks from zambod
Brachydactyloid is offline  

  My Math Forum > High School Math Forum > Probability and Statistics

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 09:18 AM
Problem Solving With Permutations koolkidx45 Advanced Statistics 1 February 20th, 2012 08:29 AM
Probability, combinatorics, permutations problem MasterOfDisaster Probability and Statistics 3 April 10th, 2011 02:01 PM
A problem regarding Permutations n Combinations hello2413 Advanced Statistics 2 March 20th, 2010 09:36 AM
A problem regarding Permutations n Combinations hello2413 Number Theory 0 December 31st, 1969 04:00 PM

Copyright © 2018 My Math Forum. All rights reserved.