KNecklaces

The words of length $n$ over a $k$-letter alphabet up to rotation, represented by the lexicographically-least word in each orbit.

SageMathNecklaces(content)↗SymPynecklaces↗

KNecklaces(n, k)the words of length $n$ over a $k$-letter alphabet up to rotation, represented by the lexicographically-least word in each orbit

Typed signatures

Type	Package	Applies
(integer<0..>, integer<0..>) -> indexed_collection<list<integer>>	combinatorics	always

Domain: Collections

Details

• Count is $\frac{1}{n}\sum_{d \mid n} \varphi(d) \, k^{n/d}$; specializes to BinaryNecklaces at $k=2$.

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(KNecklaces(4, 3)) = 24$

live ↗

In$\mathrm{Count}(\mathrm{KNecklaces}(4, 3))$Out$24$

The first element in enumeration order

live ↗

In$\mathrm{KNecklaces}(4, 3)[1]$Out$\bigl\lbrack1, 1, 1, 1\bigr\rbrack$

Scope #

Exact past $2^{53}$: 3-color necklaces of 41 beads

live ↗

In$\mathrm{Count}(\mathrm{KNecklaces}(41, 3))$Out$889\,585\,277\,491\,970\,403$

Known value · OEIS A001867 b-file

Properties #

The 3-color necklaces of $n$ beads, $n = 0 \dots 17$

live ↗

In$\mathrm{Map}(n↦\mathrm{Count}(\mathrm{KNecklaces}(n, 3)), 0..1..17)$Out$\bigl\lbrack1, 3, 6, 11, 24, 51, 130, 315, 834, 2\,195, 5\,934, 16\,107, 44\,368, 122\,643, 341\,802, 956\,635, 2\,690\,844, 7\,596\,483\bigr\rbrack$

Known value · OEIS A001867

About

Examples	5
Crosswalk	SageMathSymPy

See also: BinaryNecklaces, KLyndonWords