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
5
votes
3
answers
158
views
The number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers
For each integer $n$, let $a_n$ be the number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers.
I found (by listing) that $ a_1, a_2, a_3, a_4$ are $1, 2, 5, 15$ ...
- 817
2
votes
0
answers
24
views
Bell numbers - Cardinality of odd number of parts in partitions of the finite set $[n]$.
As it well known, Bell numbers denoted $B_{n}$ counts distinct partitions of the finite set $[n]$. So for example if $n=3$ there are 5 ways to the set $\left\{ a,b,c\right\}$ can be partitioned:
$$\...
- 119
2
votes
1
answer
68
views
Closed-form expression for the infinite sum in Dobiński's formula
In combinatorial mathematics, I learned about Dobiński's formula for the $n$-th Bell number $B_n$, which states that:
Dobiński's formula gives the $n$-th Bell number $B_n$ (i.e., the number of ...
- 2,292
0
votes
0
answers
57
views
number of possible arrangements of n coins
Had this question in a programming class and was meant to be solved using a recursive algorithm. But I was wondering if there was a combinatorics solution.
I tried counting the number of possible ...
- 342
0
votes
0
answers
84
views
number of "equivalence relations" on a set with "n-elements"
I am trying to find a formula for number of equivalence relations on a set with n-elements however I am confused.
I have already encountered the idea of "bell's number" and "Stirling ...
1
vote
0
answers
34
views
On deriving a 'simple' formula for the taylor series of $\exp^{f(x_1,x_2)}$
It is written explicitly in wikipedia, https://en.wikipedia.org/wiki/Bell_polynomials#Generating_function, how one obtains a simple analytic expression for the Taylor series of the exponential of a ...
- 31
3
votes
2
answers
83
views
Given Bell numbers as moments, derive the Poisson distribution
The Poisson distribution (with $\lambda=1$) has probability mass function $\frac{e^{-1}}{k!}$ where $k\in\{0,1,2,\cdots\}$. Its moments are the Bell numbers $B_n$, which count the possible partitions ...
1
vote
0
answers
47
views
Periodicity of Bell numbers modulo $n$
After doing some numerical simulations, I rediscovered that the Bell numbers are periodic modulo $n$, that is to say we have the following identities :
\begin{align}
B_{n+3} &= B_n\mod{2} \\\\
...
- 888
0
votes
1
answer
108
views
Stirling Numbers Exponential Generating Function Induction
I was reading the solution to a question written here, and it uses a fact which can be proved by induction.
The question is to show that an EGF for Stirling Numbers of the second kind with fixed $k$, ...
- 5
1
vote
1
answer
85
views
Closed Form for Geometric-like Finite sum of Bell Polynomials
I'm trying to see if there's a nice closed form expression for the following sum:
$\sum_{k=0}^{M} \cos(\pi k t) B_k(x)$
where $M \in \mathbb{N}$, $t \in (0,1)$, and $x \in \mathbb{R}^+$.
Notation: ...
- 317
0
votes
1
answer
71
views
Calculating factorization for large numbers
My mission is to calculate the factorization of large numbers, for example, from $start=1e11$ to $end=1e12$.
To do that, one approach that I was thinking of is to calculate for each number his ...
- 119
2
votes
1
answer
176
views
Integral representation of Bell Polynomial?
From Wolfram Alpha: https://functions.wolfram.com/IntegerFunctions/BellB/07/01/0001/,
we have an integral representation for Bell numbers as:
$B_n = \frac{2n!}{\pi e} \displaystyle{\int_{0}^{\pi}} e^{...
- 317
2
votes
1
answer
313
views
Extension of the Multivariate Faa di bruno's formula with more than two composite functions
The Faa di bruno formula for one variable (Wikipedia) is
The combinatorial forms in terms of bell polynomials are also included
Similarly, the multivariate formula (Wikipedia) is expressed ...
- 89
2
votes
1
answer
98
views
Closed form for $H(n,k)=\frac{1}{k!}\sum_{j=0}^\infty H(n-k, j)j^k$ where $H(1,k)=\frac{1}{k!}$
Let $H(n,k)$ be defined such that
$$H(1,k)=\frac{1}{k!}\text{, and }H(n,k)=\frac{1}{k!}\sum_{j=0}^\infty H(n-1,j)j^k$$
As pointed out in the comments, I should mention that we must define $0^0=1$ as ...
- 4,472
0
votes
0
answers
64
views
$Li(x)$ function and Bell polynomials
I found one formula connecting the logarithmic integral function, $li(x)$, to polynomials as following:
$$li(x) = \frac{x}{\ln(x)} + \sum_{k=1}^{+\infty} \frac{P_k(\ln(x))}{x^k}$$
where $P_k(x)$ is ...
- 87
1
vote
1
answer
46
views
How to show that $\sum_{l=0}^{\infty} \dfrac{(l+1)^{n-1}}{l!}=\sum_{l=0}^{\infty} \dfrac{l^{n}}{l!}$ (proof of Dobiński's formula)?
I am reading a proof of Dobiński's formula in Béla Bollabás book "The Art of Mathematics" (p. 144). There he uses
$$\frac{1}{e}\sum_{l=0}^{\infty} \dfrac{(l+1)^{n-1}}{l!}=\frac{1}{e}\sum_{l=...
- 889
1
vote
1
answer
186
views
Complete bell polynomial coefficients
I would like to know if it is possible to calculate the coefficient of a given Complete Bell Polynomial 's monomial by its indexes and powers:
$B_{n}(x_1,x_2,...,x_n)= c_n(1,n) x_1^n + c_n((1,n-2),(2,...
8
votes
1
answer
311
views
Strange polynomial analog of the Bell numbers
Let $\vec{x} = (x_0, x_1, x_2, \dots)$ and $\vec{y}=(y_1,y_2,y_3, \dots)$ be two systems of parameters/variables. The Motzkin
polynomials $P_n(\vec{x},\vec{y})$ for $n \geq 0$ are defined by the ...
- 567
3
votes
1
answer
54
views
Sum of Two Arguments in Bell Polynomials of Second Kind [closed]
I understand the complete Bell polynomial $B_n$ satisfies the identity:
$$B_n(x_1+y_1,x_2+y_2,...,x_n+y_n) = \sum_{k=0}^n \left(\matrix{ n \\ k }\right) B_{n-k}(x_1,x_2,..,x_{n-k})\, B_k(y_1,y_2,...,...
- 107
5
votes
0
answers
165
views
Is there a simple lower bound or approximation for the Bell numbers?
I'm not quite certain what descriptors to use to describe the solution I'm looking for, but is there an approximation or useful lower bound for the Bell numbers, for which the amount of terms used in ...
- 270
4
votes
1
answer
308
views
Bell Polynomials
The complete Bell polynomials $B_n(x_1, x_2, \ldots, x_n)$ are defined through the relation
$$\sum_{n=0}^{\infty} B_n(x_1, x_2, \ldots, x_n) \frac{t^n}{n!} =\exp\Big( \sum_{n=1}^{\infty} x_n \frac{t^n}...
- 551
4
votes
1
answer
128
views
Group Action and the Bell Number
I am struggling on solving the inequality related to the group action and Bell numbers.
Let $G$ be a finite group acting on a set $X$ with $m$ elements. Prove that for each $1 \leq r \leq m$, $$\frac{...
- 497
3
votes
1
answer
161
views
Confusion about a factor in a composition of series/Faa di Bruno formula
In the wikipedia article on the Faà di Bruno formula, one considers the composition of two "exponential/Taylor-like" series $\displaystyle f(x)=\sum_{n=1}^\infty {\frac{a_n}{n!}} x^n\; $ ($...
- 3,679
1
vote
0
answers
85
views
Reference request for recurrence relation of the complete Bell polynomials $B_n$
On this wikipedia page there is the following recurrence relation for the complete Bell polynomials $B_n$:
$$B_{n+1}(x_1,...,x_{n+1})=\sum_{i=0}^n\binom{n}{i}B_{n-i}(x_1,...,x_{n-i})x_{i+1}$$
with $...
- 590
1
vote
1
answer
88
views
Bell number, equivalent.
The $n$-th Bell number $B_n$ can be defined by $\displaystyle e^{e^x-1}=\sum_{n=0}^{+\infty}\frac{B_n}{n!}x^n$ or $\displaystyle B_n=\frac 1e\sum_{k=0}^{+\infty}\frac{k^n}{k!}$ or $\displaystyle B_{n+...
- 243
0
votes
1
answer
105
views
Problem about counting partitions
The number $f(n)=B(n)-\sum_{k=1}^n B(n-k) {n \choose k}$ counts certain partitions of $[n]$.Which partitions?
From Wiki, The Bell numbers satisfy a recurrence relation involving binomial coefficients:...
- 695
3
votes
1
answer
271
views
Bell numbers and a card shuffle
A deck of n cards may be 'shuffled' by moving the top card to any (random) position in the deck, and performing this operation n times. Martin Gardner asserts (Scientific American, May 1978) that the ...
- 31
1
vote
1
answer
112
views
Show that $\left| A_n \right| = \sum_{k=1}^{n} (-1)^k \binom{n}{k} B(n - k)$ where $B(n)$ is the nth Bell number.
I am having some trouble solving the following problem:
Let $A_n$ be the set of set partitions of $\{1, . . . , n\}$ without any singleton blocks. Show that $$\left| A_n \right| = \sum_{k=0}^{n} (-1)^...
- 376
2
votes
1
answer
240
views
prove for bell number using induction on n [duplicate]
hi guys I have to prove this equality $$B_n=e^{-1}\sum_{k=0}^{\infty}\frac{k^n}{k!},$$ that is called bell equality only using induction on $n$ . How can i do this? I have tried by substituting the ...
6
votes
3
answers
221
views
Compact formula for the $n$th derivative of $f\left(\sqrt{x+1}\right)$?
I'm interested in a general formula for
$$\frac{d^n}{dx^n}\Big[f\left(\sqrt{x+1}\right)\Big].$$
In particular, Fàa di Bruno's formula gives
$$\frac{d^n}{dx^n}\Big[f\left(\sqrt{x+1}\right)\Big]=\sum_{k=...
- 6,692
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
1
vote
1
answer
167
views
Prove $B_n\le n! $ for Bell numbers
How using induction it can be shown that:
$$B_n\le n! \;\;\;\;\;\;\;\;\;\left( n\in \mathbb N \right)$$
Where $B_n$ is the nth Bell number.
The base case is true, since $$1=B_0\le 0!=1 \;\;\;\;\;...
user715522
4
votes
1
answer
86
views
On the ratio $\frac{F_n}{B_n}$
One of the interesting limits that I came up with is:
$$\lim_{n\to\infty} \frac{F_{n}}{B_{n}}\;\;\;\;\;\;\;\;\;\; \left( n \in \mathbb N^+\right)$$
Where $F_n$ is the nth Fibonacci number and $B_n$...
user715522
4
votes
1
answer
111
views
Dividing 12 people into any number of groups, such that person A and B are not in the same group?
In how many ways can you divide 12 people into any number of groups, such that person A and B are not in the same group?
I am trying to solve this question and so far I am thinking of this in terms ...
- 365
3
votes
1
answer
292
views
Combinatorial proof for Touchard's congruence
Bell number denoted $B_n$ is the number of ways to partition a set with cardinality $n$ into $k$ indistinguishable sets , where $0\le k\le n$
It's known that Bell numbers obey Touchard's Congruence ...
user715522
2
votes
0
answers
118
views
Number of preorder relations on a set related to the open problem about preorder relations
Consider a set $A=\left\{1,2,3\right\}$,I want to count the number of preorder relations on this set, so there is two cases two consider,either the relation is symmetric or it is not, if the relation ...
user715522