Counting the Number of K-Derangements with Applications to Web Crawler Problem

Overview

A k-derangement is a special kind of permutation of n objects, such that no subset of size k from the n objects is invariant. A 1-derangement is a permutation that has no fixed points. Counting the number of 1-derangement on n distinct objects has been well studied, while counting the number of k-derangement in general remains mostly unknown. So far, only the recurrence relation of 2-derangement and the exponential generating function for k=2, 3, 4 and 5 have been proposed. In this research, we express each permutation as cyclic representation and have observed that an integer partition of n is closely related to the k-derangement. We confirm a conjecture that the number of k-derangement is a multiple of k for any k, and give recurrence relations of counting k-derangement for k=2 and 3. In application, based on the recurrence relation of the number of k-derangements, we explore the optimization of distributed web crawlers, an Internet robot that systematically scans and copies the website. In terms of the large website data, web crawlers are designed to search for them, undetected. Hence, we propose the methods of computer simulation and k-derangement to implement the distribution of web crawlers efficiently.

Competition history

• ISEF 2020 Mathematics · Entry MATH017

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.