Questions tagged [bell-numbers]
For questions related to the Bell numbers, a sequence of natural numbers that occur in partitioning a finite set.
86
questions
2
votes
2
answers
313
views
How many different equivalence relations with exactly two different equivalence classes are there on a set with $n$ elements
I came across with this topic. It looks straight forward for $5$ elements, but what if I want to find how many different equivalence relations with exactly two different equivalence classes are there ...
- 1,979
4
votes
2
answers
1k
views
$F(n)$ is number of ways to partition set of $n$ without singleton blocks. Prove that $B(n) = F(n) + F(n+1)$
In this case $B(n)$ is $n$-th Bell number.
To be honest, I would really love to know if there is a combinatorial proof for that. If there is not, other proofs are appreciated too.
- 983
1
vote
3
answers
503
views
How to prove that $B(n) < n!$ for all $n \geq 3$ where $B(n)$ is $n$-th Bell number
When I approached this problem I thought that it can be easily solved by applying induction. However something went completely wrong and I haven’t managed to prove it by induction.
Maybe there is some ...
- 983
1
vote
1
answer
202
views
Constructing a bijection to show that the number of equivalence relations on a finite set is equal to the bell numbers.
It is said that the Bell numbers count the number of partitions of a finite set. How can we prove that what they count is actually the number of partitions? I don't want to take it as a definition; I ...
- 121
0
votes
1
answer
196
views
Relation between Bell number and $F(n)$ the number of partitions of $[n]$ without singeton blocks
Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks.
Prove that
$$\lim_{n\to\infty}\frac{F(n)}{B(n)}=0$$
According to this question, we can know
$$F(n+1)=\sum_{i=0}^{n-1}(-1)^...
- 153
1
vote
1
answer
74
views
What does it mean to evaluate the 'inputs' of the Bell polynomial?
In page 218 of this pdf, the author says if we set $x_i = 1$, we are simply counting the number of partitions of {1,2,3..m} and he says that
$B_{m,k} (1,1,1,1,1..) = mSk$
where $ mSk$ is the Stirling ...
1
vote
1
answer
235
views
Number of unordered factorizations of a non-square-free positive integer
I recently discovered that the number of multiplicative partitions of some integer $n$ with $i$ prime factors is given by the Bell number $B_i$, provided that $n$ is a square-free integer. So, is ...
- 1,611
2
votes
1
answer
232
views
Exponential generating function with Stirling numbers
I want to prove in particular this result-
$$
\newcommand{\gkpSII}[2]{{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}}}
\sum_{k \geq 0} \gkpSII{2k}{j} \frac{\log(q)^k}{k!} =
\frac{1}{\sqrt{2\pi}} \...
- 63
3
votes
1
answer
78
views
representation through special numbers
Let $n,r\in N$ and let $S(n,m)$ represent Stirling's number of the second kind. It is known that $\sum_{m=0}^n S(n,m)m!=F_n$ is a Fubini number. Is it possible to represent (or estimate from above) ...
- 311
0
votes
1
answer
85
views
Literature on bounds of Fubini's numbers
If anybody can suggest where I can find a literature for a known upper and lower bounds on Fubini numbers https://en.wikipedia.org/wiki/Ordered_Bell_number
- 301
1
vote
0
answers
78
views
Is the number of sub-boolean algebra of a set with size n , Bell(n)?
In boolean algebra (P(S),+,.,’) we must have S as 1 and {} as 0 in every possible sub-boolean algebra to hold id elements.
We must have S-x for every subset x⊆S to hold complements.
It seems like ...
- 313
1
vote
1
answer
872
views
Proof Bell-Number $B(n)=\sum_{k=0}^{n-1}\binom{n-1}{k}B(k)$
Let's say that $B(n)$ (the Bell number) is the number of ways to split $\{1, \ldots ,n\}$ in non-empty blocks. Prove that, for $n \geq 1$:
$$B(n)=\sum_{k=0}^{n-1}\binom{n-1}{k}B(k)$$
I don't really ...
- 2,067
1
vote
2
answers
185
views
An approximation of the ordered Bell numbers
So my problem is the following: I have $n$ ice-cream flavors and I must rank them, allowing that I can place more than one flavor in some ranks. So for example if I have 4 flavors, I can put in the ...
0
votes
2
answers
494
views
Interesting ways to show that there are infinitely many equivalence relations on an infinite set (including Bell numbers).
I am trying to answer the question "Is there infinitely many equivalence relations on any infinite set?"
My intuition says yes, and when I try to prove this, I feel like my reasoning is not ...
- 131
4
votes
2
answers
1k
views
Can you help with this proof that the $n$-th Bell number is bounded by $n!$ for all natural numbers $n$?
I am trying to prove that an upper bound for the nth Bell number is n factorial. I am trying to do this by induction. Firstly, the nth Bell number is given by:
$B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-...
- 131