login
Maximal number of regions into which space can be divided by n spheres.
9

%I #62 Feb 16 2024 16:57:03

%S 0,2,4,8,16,30,52,84,128,186,260,352,464,598,756,940,1152,1394,1668,

%T 1976,2320,2702,3124,3588,4096,4650,5252,5904,6608,7366,8180,9052,

%U 9984,10978,12036,13160,14352,15614,16948,18356,19840,21402,23044

%N Maximal number of regions into which space can be divided by n spheres.

%C If Y is a 2-subset of an n-set X then, for n >= 2, a(n-2) is equal to the number of 2-subsets and 4-subsets of X having exactly one element in common with Y. - _Milan Janjic_, Dec 28 2007

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 73, Problem 4.

%D A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #45 (First published: San Francisco: Holden-Day, Inc., 1964).

%H T. D. Noe, <a href="/A046127/b046127.txt">Table of n, a(n) for n = 0..1000</a>

%H Mark de Rooij, Dion Woestenburg, and Frank Busing, <a href="https://arxiv.org/abs/2402.07624">Supervised and Unsupervised Mapping of Binary Variables: A proximity perspective</a>, arXiv:2402.07624 [stat.CO], 2024. See p. 33.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SpaceDivisionbySpheres.html">Space Division by Spheres</a>.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).

%F a(n) = f(n,3) where f(n,k) = C(n-1, k) + Sum_{i=0..k} C(n, i) for hyperspheres in R^k.

%F a(n) = n*(n^2 - 3*n + 8)/3.

%F From _Philip C. Ritchey_, Dec 09 2017: (Start)

%F The above identity proved as closed form of the following summation and its corresponding recurrence relation:

%F a(n) = Sum_{i=1..n} (i*(i-3) + 4).

%F a(n) = a(n-1) + n*(n-3) + 4, a(0) = 0. (End)

%F From _Colin Barker_, Jan 28 2012: (Start)

%F a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).

%F G.f.: 2*x*(1 - 2*x + 2*x^2)/(1 - x)^4. (End)

%F a(n) = A033547(n-1) + 2 for n >= 1. - _Jianing Song_, Feb 03 2024

%F E.g.f.: exp(x)*x*(6 + x^2)/3. - _Stefano Spezia_, Feb 15 2024

%t Join[{0},Table[n (n^2-3n+8)/3,{n,50}]] (* _Harvey P. Dale_, Apr 21 2011 *)

%o (Python)

%o def a(n): return n*(n**2 - 3*n + 8)//3 # _Philip C. Ritchey_, Dec 10 2017

%Y Cf. A014206 (dim 2), this sequence (dim 3), A059173 (dim 4), A059174 (dim 5). See also A000124, A000125. A row of A059250.

%Y Cf. A033547.

%K nonn,easy,nice

%O 0,2

%A _Eric W. Weisstein_