Ivan Shishkin, Rye (1878)

Problems/CombinatoricsUnreviewed

Number of partitions of a finite set

by Sequoia·
58
Difficulty scaleÉchelle de difficulté

This score reflects both the level of the required concepts and the difficulty of the solution.Ce score tient compte à la fois du niveau des notions nécessaires et de la difficulté de la résolution.

  1. 110First steps / middle schoolPremiers pas / collège
  2. 1125Beginner / high schoolDébutant / lycée
  3. 2650Intermediate / undergraduateIntermédiaire / licence
  4. 5170Advanced / graduateAvancé / master
  5. 7190Expert / specializedExpert / spécialisé
  6. 91100Research levelNiveau recherche
These levels are approximate guides.Ces niveaux sont des repères approximatifs.
·
English
EnglishFrançais
Unreviewed. This problem has not been reviewed by trusted users yet.

We denote by BnB_n the nn-th Bell number, that is, the number of partitions of a set with nn elements. We set B0=1B_0 = 1.

  1. Show that Bn+1=k=0n(nk)BkB_{n+1} = \displaystyle\sum_{k=0}^{n} \binom{n}{k} B_k.

  2. Show that Bnn!B_n\leqslant n! for all n0n\geqslant0. Conclude that the exponential generating function S(x):=n0Bnn!xnS(x) := \sum_{n\geqslant0} \dfrac{B_n}{n!} x^n is defined in a neighborhood of 00.

  3. Show that S(x)=eex1S(x)=\displaystyle e^{e^x-1} for all xx close to 00.

  4. Conclude that Bn=1ek=0+knk!B_n=\displaystyle\frac{1}{e}\sum_{k=0}^{+\infty}\frac{k^n}{k!}.

  5. Deduce the number of equivalence relations that can be considered on a set with nn elements.

I solved itMark it doneAdd to my listKeep it in your list

Solutions

0
Report

For an unclear, ambiguous, or possibly incorrect statement, please use the Discussion tab on the right. Report content that needs moderator intervention, such as dangerous, clearly non-mathematical, or plagiarized content.