Problem 1393. A (wrong) place for everything, and everything in its (wrong) place
You have an equal number of cups and balls, each labelled from one to N. You randomly place one ball in each cup. Determine the number of possible combinations such that no balls are in the cup with a matching number. For example, if you have three balls and three cups, there are two valid solutions:
- 2, 3, 1
- 3, 1, 2
The following permutations do not meet the criteria for the reasons listed:
- 1, 2, 3 (all three balls are in the correct cups)
- 1, 3, 2 (ball 1 is in cup 1)
- 3, 2, 1 (ball 2 is in cup 2)
- 2, 1, 3 (ball 3 is in cup 3)
Good luck!
Solution Stats
Problem Comments
-
2 Comments
I think that with this kind of problem, you can process in two steps.
A first easy problem with small N (to test perms for example). And a harder problem with big N, which
oblige to find another algorithm.
http://oeis.org/A000166
Solution Comments
Show commentsProblem Recent Solvers54
Suggested Problems
-
Extract leading non-zero digit
2132 Solvers
-
Remove the polynomials that have positive real elements of their roots.
1670 Solvers
-
How to find the position of an element in a vector without using the find function
2722 Solvers
-
Create a Multiplication table matrix...
481 Solvers
-
Check that number is whole number
4303 Solvers
More from this Author80
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!