Difference between revisions of "Arrangement Restriction Theorem"

Line 1: Line 1:
The <b>Arrangement Restriction Theorem</b> is discovered by [[User:aops-g5-gethsemanea2|aops-g5-gethsemanea2]] and is (maybe) an alternative to the [[Georgeooga-Harryooga Theorem]].
+
The <b>Arrangement Restriction Theorem</b> is discovered by [[User:aops-g5-gethsemanea2|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 <math>k</math> objects are together.
  
 
==Definition==
 
==Definition==

Revision as of 09:10, 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!$.