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.
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
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
My memory has cleared a little about Bell numbers, and I realise that what I had intended to mention earlier concerned their period modulo p, which can be shown to divide (p^p-1)/(p-1); I conjectured that it is exactly that for all p. I expect there are now factorisations available for a few more primes p, but haven't got around to checking on them ... Fred Lunnon On 3/1/06, Schroeppel, Richard <rschroe@sandia.gov> wrote:
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 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). ...
But now I have, and Samuel Wagstaff has taken up the baton at http://homes.cerias.purdue.edu/~ssw/bell/index.html The conjecture (which should perhaps be called Touchard's conjecture) has now been checked for prime p < 103. WFL On 3/13/06, Fred lunnon <fred.lunnon@gmail.com> wrote:
My memory has cleared a little about Bell numbers, and I realise that what I had intended to mention earlier concerned their period modulo p, which can be shown to divide (p^p-1)/(p-1); I conjectured that it is exactly that for all p.
I expect there are now factorisations available for a few more primes p, but haven't got around to checking on them ...
... but if you happen to know an asymptotic formula I'd love if you'd post it.
The EIS entry for the Bell numbers has two: a(n) is asymptotic to n!*(2 Pi r^2 exp(r))^(-1/2) exp(exp(r)-1) / r^n, where r is the positive root of r exp(r) = n. - see e.g. the Odlyzko reference. a(n) is asymptotic to b^n*exp(b-n-1/2)/sqrt(ln(n)) where b satisfies b*ln(b) = n - 1/2 (see Graham, Knuth and Patashnik, Concrete Mathematics, 2nd ed., p. 493) - Benoit Cloitre (abmt(AT)wanadoo.fr), Oct 23 2002 --Michael
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
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
participants (4)
-
dasimov＠earthlink.net -
Fred lunnon -
Michael Kleber -
Schroeppel, Richard