Misaddressed letters problem with mathematica

  • Mathematica
  • Thread starter raulitopomper
  • Start date
  • Tags
    Mathematica
In summary, the formula for solving a recurrence problem with Mathematica is: N(n)=(n-1)[N(n-2)+N(n-3)+N(n-4)+...]]
  • #1
raulitopomper
4
0
Hi I'm trying to solve this famous problem with Mathematica:

"How many ways can a math professor incorrectly address Christmas cards so that no card gets to the originally intended recipient"

I found a recurrence formula but don`t know how to implement it in Mathematica, this is the formula:
N(n)=(n-1)[N(n-2)+(n-2)[N(n-3)+(n-3)[N(n-4)+(n-4)[...]]]]

thank you
 
Physics news on Phys.org
  • #2
If you provide a URL for where you found that formula then perhaps someone can help you solve this.
 
  • #3
I found the solution by my self, anyway I found the way to do it! just have to realize that
(n-2)[N(n-3)+(n-3)[N(n-4)+(n-4)[...]]]]=N(n-1)
in any case, would it be any way to introduce in mathematica a recurrence formula with a for or do loop?? so in case a large number of products or sums appear it can be done? thanks
 
  • #4
Given your observation, it turns into a 2-term recurrence that Mathematica can solve in terms of incomplete Euler Gamma functions (I use A instead of N, since N is a built-in symbol):
Code:
In[1]:= RSolve[A[n]==(n-1)(A[n-2]+A[n-1]),A[n],n]
Out[1]= {{A[n]->C[1] n!+(2 C[2] n! (-E+Gamma[1+n,-1]/Gamma[1+n]))/E}}
C[1] and C[2] are related to the initial conditions. From the problem stated it should be that A[1]=0, A[2]=1 so that
Code:
In[2]:= RSolve[A[n]==(n-1)(A[n-2]+A[n-1])&&A[1]==0&&A[2]==1,A[n],n]
Out[2]= {{A[n]->(Gamma[1+n] Gamma[2,-1]-Gamma[1+n,-1])/(2 Gamma[2,-1]-Gamma[3,-1])}}
or, using traditional notation (TraditionalForm)
[TEX]A(n) = \frac{\Gamma (2,-1) \Gamma (n+1)-\Gamma (n+1,-1)}{2 \Gamma (2,-1)-\Gamma (3,-1)}[/TEX]

If you don't want to use the closed form solution, you can implement the recursion using
Code:
In[3]:= A[1]=0;A[2]=1;A[n_]:=A[n]=(n-1)(A[n-2]+A[n-1])
Where I have used http://en.wikipedia.org/wiki/Memoization" [Broken] to prevent the exponential growth in the calculation of the lower terms.

You can check that it give the same results as the closed form solution
Code:
In[4]:= ASoln[n_]:=(Gamma[2,-1] Gamma[n+1]-Gamma[n+1,-1])/(2 Gamma[2,-1]-Gamma[3,-1])
In[5]:= And@@Table[A[i]==ASoln[i],{i,1,200}]//FunctionExpand//FullSimplify
Out[5]= True
the above is a tiny bit slow because the simplification of the incomplete gamma functions is slow.

Finally, your original formula can be implemented as
Code:
B[0] = 1;
In[6]:= B[n_]:=B[n]=Sum[Product[(n-j), {j, 1, i}] B[n-i-1], {i, 1, n}]
The product term in the above is just the Pochhammer symbol - or rising factorial.

You can test it with
Code:
In[7]:= And@@Table[B[n]==A[n], {n, 1, 200}]
Out[7]= True
 
Last edited by a moderator:
  • #5
Or you could use the formula N(n)=floor(n!/e+1/2). Check wikipedia on derangements.
 
  • #6
That's if you want to treat the question as more than a simple Mathematica example!
 

What is the "Misaddressed Letters Problem"?

The Misaddressed Letters Problem is a mathematical puzzle that involves a group of letters being incorrectly addressed and needing to be redistributed to their correct recipients. It is often used as an example in computer science and coding to demonstrate the use of algorithms and data structures.

How can Mathematica be used to solve the Misaddressed Letters Problem?

Mathematica is a powerful computational software that can be used to solve a variety of mathematical problems, including the Misaddressed Letters Problem. It provides a variety of built-in functions and algorithms that can be used to efficiently solve the problem and find the optimal solution.

What are the key steps to solving the Misaddressed Letters Problem with Mathematica?

The key steps to solving the Misaddressed Letters Problem with Mathematica include defining the initial state of the letters, creating a rule-based function to redistribute the letters, and using built-in functions such as NestWhile and Position to implement the function and find the optimal solution.

What are some potential challenges when solving the Misaddressed Letters Problem with Mathematica?

One potential challenge when solving the Misaddressed Letters Problem with Mathematica is determining the most efficient way to redistribute the letters. This may require some trial and error and optimization of the rule-based function. Another challenge may be dealing with large datasets and finding ways to optimize the code for faster computation.

Are there any real-life applications of the Misaddressed Letters Problem and its solution with Mathematica?

While the Misaddressed Letters Problem is primarily used as a mathematical puzzle, the concept of redistributing incorrectly addressed items can be applied to real-life situations, such as organizing and optimizing mail delivery routes or sorting packages in a warehouse. Additionally, the use of Mathematica to efficiently solve this problem can be applied to a variety of other optimization problems in different industries.

Similar threads

Replies
3
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
6
Views
5K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
435
Back
Top