Questions tagged [bell-numbers]

For questions related to the Bell numbers, a sequence of natural numbers that occur in partitioning a finite set.

Filter by
Sorted by
Tagged with
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 ...
sillyQsman's user avatar
3 votes
2 answers
75 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 ...
Andrius Kulikauskas's user avatar
1 vote
0 answers
43 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} \\\\ ...
Zakhurf's user avatar
  • 868
0 votes
1 answer
77 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$, ...
Jeremy's user avatar
  • 5
1 vote
1 answer
78 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: ...
BBadman's user avatar
  • 167
0 votes
1 answer
63 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 ...
linuxbeginner's user avatar
2 votes
1 answer
156 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^{...
BBadman's user avatar
  • 167
2 votes
1 answer
225 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 ...
Kabir Munjal's user avatar
2 votes
1 answer
95 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 ...
Graviton's user avatar
  • 4,480
0 votes
0 answers
54 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 ...
Craw Craw's user avatar
1 vote
1 answer
44 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=...
garondal's user avatar
  • 833
1 vote
1 answer
144 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,...
Antonio Bernardo's user avatar
8 votes
1 answer
300 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 ...
Jeanne Scott's user avatar
3 votes
1 answer
48 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,...,...
CLic's user avatar
  • 107
5 votes
0 answers
137 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 ...
brubsby's user avatar
  • 225
4 votes
1 answer
258 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}...
Andrew's user avatar
  • 541
4 votes
1 answer
120 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{...
Alex Lee's user avatar
  • 387
3 votes
1 answer
156 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\; $ ($...
Noix07's user avatar
  • 3,439
1 vote
0 answers
80 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 $...
TwoStones's user avatar
  • 570
1 vote
1 answer
82 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+...
P.Fazioli's user avatar
  • 243
0 votes
1 answer
101 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:...
spruce's user avatar
  • 695
3 votes
1 answer
258 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 ...
Paul Turner's user avatar
1 vote
1 answer
99 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)^...
Alexis Sandoval's user avatar
2 votes
1 answer
219 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 ...
Alfredo Cozzolini's user avatar
6 votes
3 answers
217 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=...
WillG's user avatar
  • 6,467
2 votes
2 answers
287 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 ...
vesii's user avatar
  • 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.
math-traveler's user avatar
1 vote
3 answers
400 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 ...
math-traveler's user avatar
1 vote
1 answer
201 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 ...
user821980's user avatar
0 votes
1 answer
190 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)^...
Leo SHEN's user avatar
  • 153
1 vote
1 answer
66 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 ...
tryst with freedom's user avatar
1 vote
1 answer
231 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 ...
Scene's user avatar
  • 1,566
2 votes
1 answer
219 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}} \...
Jack's user avatar
  • 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) ...
Forbs's user avatar
  • 311
0 votes
1 answer
78 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
user4164's user avatar
  • 301
1 vote
0 answers
76 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 ...
Omid Yaghoubi's user avatar
1 vote
1 answer
705 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 ...
kubo's user avatar
  • 1,752
1 vote
2 answers
161 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 ...
PanYmermelada's user avatar
0 votes
2 answers
463 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 ...
Natasha's user avatar
  • 131
4 votes
2 answers
944 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-...
Natasha's user avatar
  • 131
1 vote
1 answer
161 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 \;\;\;\;\;...
user avatar
4 votes
1 answer
83 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$...
user avatar
4 votes
1 answer
108 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 ...
skidjoe's user avatar
  • 365
3 votes
1 answer
274 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 ...
user avatar
2 votes
0 answers
107 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 ...
user avatar
2 votes
1 answer
106 views

New wrong recurrence formula for Bell numbers

Bell numbers are the numbers counting the total partitions on a set with $n$ distinct elements. Explanation: Consider a set like $A:=\left\{x_{1},x_{2},...,x_{n}\right\}$ A partial equivalence ...
user avatar
1 vote
1 answer
363 views

generating function for Bell polynomial

How it can be proved that : $$\sum_{n=0}^{ ∞}B_{n}\left(x\right)\frac{t^{n}}{n!}=e^{x\left(e^{t}-1\right)}$$ Where $B_n$ is the $n^{th}$ complete Bell polynomial. I know that $$\sum_{n=k}^{∞ }S\left(...
Absurd's user avatar
  • 369
3 votes
1 answer
541 views

Formula for computing the coefficients of Bell polynomial

I'm working on Bell polynomials and have learned some of its properties, but I've never seen any formula for calculating the coefficient in Bell polynomials. My trying to find these coefficients was ...
Absurd's user avatar
  • 369
2 votes
0 answers
66 views

$\left( k, n \right)$ symmetry?

As background: there are $k!$ strict orders on the set $K = \left\{ 1, \ldots k \right\}$. Under symmetry, each order occurs with probability $\tfrac{1}{k!}$. Now consider the set of weak orders on $...
Colin Rowat's user avatar
2 votes
1 answer
545 views

Generating function for the number of partitions of [n] without singletons.

I know the generating function for the total number of partitions of [n] is given by $$ B(x)=e^{e^x-1}$$ I am struggling to find $V(X)$, the exponential generating function for the number of ...
Mathsguy123's user avatar