1,2

(1) Bryce Duncan and I found the sequence {b(n)} while studying a graph invariant we call the Bell number. For a simple graph G = (V,E), we define B(G) to be the number of partitions P of V in which each block of P is an independent set of G. The sequence b(n) considered here results from choosing V = {1, 2, ..., n} and E = {(i,j) : |i - j| > 2. (The classical Bell numbers B(n) come from the edgeless graph on n vertices.)

(2) The constant r in the formula is the dominant root of the characteristic equation of a linear homogeneous recurrence relation that also defines {b(n)}. (This recurrence relation, along with initial conditions, appears in the Mathematica program given below. The formula for b(n) is analogous to one version of the Binet formula for the Fibonacci numbers, namely F(n) = the integer nearest to (1/sqrt[5]) p^n where p is the golden mean. The shifted Fibonacci numbers F(n+1) are also graphical Bell numbers: replace the condition |i - j| > 2 with |i - j| > 1 to obtain them.

(3) Bell numbers for simple graphs satisfy the deletion-contraction identity B(G) = B(G\e) - B(G/e), but not the product identity B(G union H) = B(G)B(H) for disjoint graphs G and H. However, we do have B(B join H) = B(G)B(H) for the join of graphs G and H. The join graph G join H results from adding to their disjoint union, all possible edges that join a vertex of G to a vertex of H.

Herbert S. Wilf, Generatingfunctiononogy (2nd Edition), Academic Press 1990, pp. 1 - 10 and pp. 20 - 23.

Arthur T. Benjamin and Jennifer J. Quinn, Proofs that Really Count, Dolciani Mathematical Expositions (MAA), (2003), p. 1. (A relevant combinatorial interpretation of Fibonacci numbers.)

b(n) = the integer nearest to s r^n, where r = 2.0659948920 ... and s = 0.53979687305... . (More information in comment (2).)

b(4) = 10, with set partitions {{1},{2},{3}, {4}}; {{1,2}, {3}, {4}};

{{1,3}, {2}, {4}}; {{1}, {2,3}, {4}}; {{1}, {2,4}, {3}}; {{1}, {2}, {3,4}};

{{1,2,3}, {4}}; {{1}, {2,3,4}}; {{1,2}, {3,4}} and {{1,3}, {2,4}}.

b[1] = 1; b[2] = 2; b[3] = 5; b[4] = 10 b[n_] := b[n] = b[n-1] + b[n-2] + 2 b[n-3] + b[n-4] Table[b[n], {n, 1, 30}]

Cf. A000110, A000045.

Sequence in context: A049938 A002460 A006836 this_sequence A051109 A124146 A032468

Adjacent sequences: A129844 A129845 A129846 this_sequence A129848 A129849 A129850

nonn

Rhodes Peele (rpeele(AT)mail.aum.edu), May 22 2007