A116723 We have one bead labeled i for every i=1, 2, ...; a(n) = number of necklaces that can be made using any subset of the first n beads.

1, 2, 4, 8, 18, 53, 219, 1201, 8055, 62860, 556070, 5488126, 59740688, 710771367, 9174170117, 127661752527, 1904975488573, 30341995265190, 513771331467544, 9215499383109764, 174548332364311774, 3481204991988351785, 72920994844093191807, 1600596371590399672061

Offset: 0

Author

Rodney Stephenson (rod.stephenson(AT)gmail.com), Mar 19 2008

Keywords

• nonn

Comments

Turning the necklace over doesn't count as a different necklace.

For k beads chosen from n distinct ones, we can have n!/(n-k)! possible permutations, then eliminate the cyclic permutations and reversals (2k). The case k=2 is special in that a cyclic permutation is equivalent to a reversal.

Examples

			For example for n=4 we have {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}, {1,2,4,3}, {1,3,2,4}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• Qu Cao, Jin Dong, Song He, and Fan Zhu, On one-loop amplitudes in gauge theories, arXiv:2412.19629 [hep-th], 2024. See p. 4.
• Index entries for sequences related to necklaces

Crossrefs

Row sums of A144151. - Alois P. Heinz, Jun 01 2009

Programs

Maple

a:= proc(n) option remember; `if`(n<4, 2^n, `if`(n=4, 18,
      ((n^3-4*n^2+n)*a(n-1) -(2*n-2)*(n^2-4*n+2)*a(n-2)
       +n*(n-2)*(n-3)*a(n-3)) / ((n-1)*(n-4))))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 22 2016

Mathematica

a[n_] := 1 + n + n(n-1)/2 + Sum[n!/(2k(n-k)!), {k, 3, n}];
a /@ Range[0, 30] (* Jean-François Alcover, Nov 09 2020 *)

PARI

a(n) = 1 + n + n*(n-1)/2 + sum(k=3, n, n!/(2*k*(n-k)!)); \\ Michel Marcus, Nov 09 2020

Formula

a(n) = 1 + n + n(n-1)/2 + Sum_{k=3..n} n!/(2k(n-k)!).

Extensions

More terms from Washington Bomfim, Aug 29 2008