Difference between revisions of "Arrangement Restriction Theorem"

(Testimonials)
Line 12: Line 12:
 
==Testimonials==
 
==Testimonials==
  
I like this theorem, but not as much as the Georgeooga-Harryooga Theorem or the Wooga Looga Theorem ~ ilp
+
I like this theorem, but not as much as the [[Georgeooga-Harryooga Theorem]] or the [[Wooga Looga Theorem]] ~ ilp
 +
 
 +
"Very nice theorem but not as impressive as the [[Georgeooga-Harryooga Theorem]]." - [[RedFireTruck]]

Revision as of 14:52, 20 December 2020

The Arrangement Restriction Theorem is discovered by aops-g5-gethsemanea2 and is NOT an alternative to the Georgeooga-Harryooga Theorem because in this theorem the only situation that is not allowed is that all $k$ objects are together.

Definition

If there are $n$ objects to be arranged and $k$ of them should not be beside each other altogether, then the number of ways to arrange them is $n! - (n - k + 1)!k!$.

Proof/Derivation

If there are no restrictions, then we have $n!$. But, if we put $k$ objects beside each other, we have $(n-k+1)!k!$ because we can count the $k$ objects as one object and just rearrange them.

So, by complementary counting, we get $n! - (n - k + 1)!k!$.

Testimonials

I like this theorem, but not as much as the Georgeooga-Harryooga Theorem or the Wooga Looga Theorem ~ ilp

"Very nice theorem but not as impressive as the Georgeooga-Harryooga Theorem." - RedFireTruck