cp's OEIS Frontend

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.

%I A116723 #25 Jan 06 2025 11:58:07
%S A116723 1,2,4,8,18,53,219,1201,8055,62860,556070,5488126,59740688,710771367,
%T A116723 9174170117,127661752527,1904975488573,30341995265190,513771331467544,
%U A116723 9215499383109764,174548332364311774,3481204991988351785,72920994844093191807,1600596371590399672061
%N 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.
%C A116723 Turning the necklace over doesn't count as a different necklace.
%C A116723 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.
%H A116723 Alois P. Heinz, <a href="/A116723/b116723.txt">Table of n, a(n) for n = 0..450</a>
%H A116723 Qu Cao, Jin Dong, Song He, and Fan Zhu, <a href="https://arxiv.org/abs/2412.19629">On one-loop amplitudes in gauge theories</a>, arXiv:2412.19629 [hep-th], 2024. See p. 4.
%H A116723 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A116723 a(n) = 1 + n + n(n-1)/2 + Sum_{k=3..n} n!/(2k(n-k)!).
%e A116723 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}.
%p A116723 a:= proc(n) option remember; `if`(n<4, 2^n, `if`(n=4, 18,
%p A116723       ((n^3-4*n^2+n)*a(n-1) -(2*n-2)*(n^2-4*n+2)*a(n-2)
%p A116723        +n*(n-2)*(n-3)*a(n-3)) / ((n-1)*(n-4))))
%p A116723     end:
%p A116723 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jul 22 2016
%t A116723 a[n_] := 1 + n + n(n-1)/2 + Sum[n!/(2k(n-k)!), {k, 3, n}];
%t A116723 a /@ Range[0, 30] (* _Jean-François Alcover_, Nov 09 2020 *)
%o A116723 (PARI) a(n) = 1 + n + n*(n-1)/2 + sum(k=3, n, n!/(2*k*(n-k)!)); \\ _Michel Marcus_, Nov 09 2020
%Y A116723 Row sums of A144151. - _Alois P. Heinz_, Jun 01 2009
%K A116723 nonn
%O A116723 0,2
%A A116723 Rodney Stephenson (rod.stephenson(AT)gmail.com), Mar 19 2008
%E A116723 More terms from _Washington Bomfim_, Aug 29 2008