Pad every number with leading zeros to obtain exactly decimal digits. Its digits are a solution of in nonnegative integers. Conversely every such solution is a valid digit string, since no individual digit can exceed ; its digit sum also excludes the number zero. The stars and bars count therefore givesFor , , so . Thus , with an explicit Big O notation constant and threshold .
Let be the set of permutations fixing object . If a specified collection of objects is fixed, the remaining objects can be arranged in ways. There are such collections. Applying the inclusion-exclusion principle to exclude all fixed objects givesFor , the terms and cancel. Thus the number of derangements is , interpreting the remaining sum as empty when . The full inclusion-exclusion formula also gives .
There are choices for the first position, then choices for the second, and so on down to one choice. The multiplication principle therefore gives permutations. This also agrees with the empty permutation convention .
Put . By distributivity, and . Consequently,Here we used associativity, distributivity, and idempotence of set intersection and set union. The equality holds for every , so : is an idempotent function.
There are unlisted articles, also show them or only show them.