This recurrence offers the intriguing possibility of calculating the Bell sequence with the Chinese Remainder Theorem. The product of primes < N is (very) roughly e^N. (Prime powers don't matter much here.) The asymptotic size of B(N) is rather larger, closer to N^N. So we'd need either additional congruence information or a small error estimate from the asymptotic formula (or more terms?) to continue. This isn't likely to be less work than simply using the recursion. [For the uninitiated, B's pop up in the power series for e^(e^x-1), and the recursion is just dotting the sequence-so-far with a row of binomial coefficients.] Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Fred lunnon Sent: Wed 3/1/2006 6:46 AM To: dasimov@earthlink.net; math-fun Subject: Re: [math-fun] Stirling Numbers? The asymptotic form is certainly known --- somewhere in my paper files lies a-mouldering an ancient copy of the relevant reference --- but until I get to unpack them, it remains inconveniently inaccessible. The Bell numbers B(n) have some nice properties modulo a fixed integer: for example, for prime p they satisfy B(n+p) - B(n+1) - B(n) = 0 (mod p); and for prime powers (E^p - E - 1)^k B(n) = 0 (mod p^k), in umbral notation where E denotes the shift operator E B(n) = B(n+1). For small p, the polynomial E^p - E - 1 is irreducible mod p, so the first recurrence is minimal: I conjecture (wildly) that this situation obtains for all prime p. However the exponent k is not best possible: the optimal exponent is sublinear in k, in an intriguing fashion depending on p. Fred Lunnon On 3/1/06, dasimov@earthlink.net <dasimov@earthlink.net> wrote:
Hah! I hadn't even noticed my post hadn't gone through. After posting I found a recursion formula & calculated the terms up through 8 by hand, which were enough numbers to find the sequence in OEIS.
(So I wrote a follow-up post saying Never mind, I learned that they're Bell numbers. Apparently that post is stuck, too.)
And Jim, thanks for recommending the Rota book, but if you happen to know an asymptotic formula I'd love if you'd post it.
--Dan
I wrote about 10 days ago: << Suppose you want to count all possible partitions of the set X_n = {1,2,...,n}. I.e., you want to know how many [collections of mutually disjoint nonempty subsets of X_n] have union = X_n. . . .
Michael Kleber wrote: << These are the Bell numbers, B(n). A000110 in the EIS, where you can find formulas and references to your heart's content.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun