Talk:Ordered Bell number

A paper reviewed by...

Why does the article refer to "A paper reviewed by Ellison and Klein" and not "A paper by Archangeli and Langendoen" or whomever wrote the paper in this anthology? That would make more sense. --WiseWoman (talk) 23:04, 3 March 2015 (UTC)

Because that paragraph is about what Ellison & Klein say in their review, not so much about what Archangeli and Langendoen say. —David Eppstein (talk) 23:28, 3 March 2015 (UTC)

Oh, it's clear that the paragraph is about Ellison & Klein's review, and their contributions in sentences 1, 2, and 4 of the paragraph. I was just curious to know who wrote the paper which Ellison & Klein refer to in their review that you refer to in your third sentence. --WiseWoman (talk) 23:58, 3 March 2015 (UTC)

Where is this name from?

This article has a nice historical introduction, but gives no or few explanation about the (curious, indeed) choice of naming this sequence of numbers after E.T.Bell (apparently, it's from a 2005 paper). Isn't the case to go back to the 1974 introduction by Louis Comtet, or to look for some more dignified choice? (btw, "Bell numbers" for the Dobiński's numbers of set partitions seems already quite a local attribution). pma 08:57, 28 January 2021 (UTC)

GA Review

This review is transcluded from Talk:Ordered Bell number/GA1. The edit link for this section can be used to add comments to the review.

Nominator: David Eppstein (talk · contribs) 06:50, 23 November 2023 (UTC)

Reviewer: Bilorv (talk · contribs) 20:47, 11 April 2024 (UTC)

I gather the bulk of the article was written in 2013, but it actually looks like there's been some developments since then. I like this paper (assuming it's reliable) because it has some ideas that can be understood by readers with a very low level of maths, like $2^{n}<a(n)<(n+1)^{n}$ (though $n!$ is a better lower bound that might be worth mentioning in the lead) and that the numbers are odd. It also shows log-convexity.

It looks like the numbers can be generalized to "higher-order Fubini numbers" and "Fubini polynomials", which might be the basis of a section.

Other possible sources (reliability not evaluated): [1], [2], [3], [4], [5]. This and this might not be worth including as they're only passing mentions but it's good to see that the numbers are natural enough to arise practically.

Some other thoughts on the existing content:

• It may be useful to illustrate ties with more than three objects, without enumerating 75 or 541 of them. For instance: $b<f<a,c,d<e,g$. I think in the same example you could show how this is equivalent to partitioning ($\{a,c,d\},\{b\},\{e,g\},\{f\}$ and then ordering (or vice versa, partitioning bfacdeg).
• "which count the number of permutations of n items with k + 1 runs of increasing items" – This makes it sound like $6,3,1,2,4,5$ has a single run of length 4 (so it counts towards $n=6,k=0$), but Eulerian number makes it seem like this is three runs ($n=6,k=2$). If it's the latter, would "pairs of ascending numbers" be clearer? Or "pairs of ordered items", since you talk about "items" rather than "numbers" and we could play this game with descending pairs or letters in alphabetical order etc.
• For clarity I think it would help to follow the numbers by their notation: "Stirling numbers of the second kind $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$" and "Eulerian numbers $\left\langle {\begin{matrix}n\\k\end{matrix}}\right\rangle$".
• I don't get the denominator $1-(e^{x}-1)$: is that supposed to illustrate some step of calculation or that exponential generating functions are typically written in the form $1/(1-f(x))$?
• Can you spell out what P is – e.g. the ith row and jth column is $i \choose j$?
• Is the approximation good for large n (rather than n close to 1)?
• Since it's ambiguous notation (used for e or 10), can you mention the base of the log in prose?
• "For this reason, the ordered Bell numbers count ... the possible outcomes of a multi-candidate election" – I know combinatorics authors like elections, but I feel this muddies the water. It only counts the "outcomes" in the sense of throwing away vote counts and where all orderings matter. I feel that some version of "rankings where ties are allowed" would be clearer even if more abstract (I'm picturing Senior Wrangler to wooden spoon but again this complicates things with marks).
• "by which he means the number of other relations one can form from it by permuting and repeating its arguments (lowering the arity with every repetition)" – On one hand I understood this without having to look it up, but on the other I feel it's not the clearest wording. I wrote down $\{(a,b,c)\in \mathbb {N} ^{3}:{\textrm {gcd}}(a,b)=c\}$ and I understand I can permute it and repeat arguments like ${\textrm {gcd}}(a,c)=b$ and ${\textrm {gcd}}(a,a)=c\}$ (on $\mathbb {N} ^{2}$) (though several of these generate the same relations because of properties like symmetry). I think the parenthetical could be "(though repetition decreases the arity of the relation)" or "other relations (of arity at most n)". I must admit to not understanding the next sentence: by changing $a,b,c$ to $a,a,c$, what weak ordering do I induce?
• I think combination locks belong in or just after the first paragraph of the section as a straightforward interpretation of the original definition.
• I don't know if WikiProject Mathematics has a consensus on reliability of OEIS but I'm not sure I follow citation 13 (as of Special:Permalink/1213893425) at all: what triangle are we talking about and are you relying on the sequence or the comments as the source? One of the comments mentions Wikipedia, which is an issue, but others mention references listed on that page.
• (Not a GA requirement.) The short description says "Number of weak orderings", which doesn't tell a layperson anything. It should be something like "Topic in mathematics".

A spotcheck of inline citations shows no issues. Great work so far but let me know what you think about expanding with further sources. — Bilorv (talk) 20:47, 11 April 2024 (UTC)

Thanks! I'll go through these points one at a time (not necessarily in order) as I find time. Starting with your unbulleted first paragraph: I think the simple bounds $n!\leq a(n)\leq (n+1)^{n-1}$ (tighter than $(n+1)^{n}$) may be worth mentioning somewhere, but we shouldn't put things in the lead that aren't summaries of later material. On the other hand we need a published source and the proof in the paper you link is too ugly for my taste. There's a much nicer proof of the tighter upper bound that follows from Cayley's formula; I've asked here for published references and may add it if I find one. I think the paper you link is reliable; at least, it's listed in MathSciNet and zbMATH. But we don't need to cite every possible paper in this topic; there would be too many. Its other main result is that these numbers are log-convex but I haven't seen much evidence that log-convexity is considered significant. We do have an article on logarithmically concave sequences but it doesn't mention log-convexity and we don't have a separate article on that. —David Eppstein (talk) 15:56, 16 April 2024 (UTC)

Another batch of replies:

Re the other potential sources: I couldn't evaluate most of them because ebscohost login needed. I tried logging into the Wikipedia Library and connecting to the ebsco database first, but still the links didn't work.

Re "may be useful to illustrate ties with more than three objects": this appears to be referring to the lead illustration, showing all weak orders on three objects. This article is about counting all lead orderings, not about the concept of a weak order itself, for which our other article does lead with an image of a single weak order (though maybe not a great image).

Re the gloss of Eulerian number: (6, 3, 1, 2, 4, 5) has three runs of increasing items: (6), (3), and (1, 2, 4, 5). But I can see that the one-element runs are confusing. I changed it to refer to the number of items with a larger successor, and added an inline copy of the notation for the Stirling and Eulerian numbers as you suggested.

Re the denominator $1-(e^{x}-1)$, I don't know why that is there either, which suggests that it's not very informative. It was added last December by another user, AndriusKulikauskas, with the explanation "write out more explicitly". I don't think it was an improvement. Removed.

—David Eppstein (talk) 07:21, 18 April 2024 (UTC)

Huh, I did try testing the links by logging out but I think it's a timeout issue. I think the ScienceDirect works should link [6][7][8] and I was also trying to point to (all on The Wikipedia Library):

• [9]
• "The log-convexity of the Fubini numbers", Transactions on Combinatorics
• "On central fubini-like numbers and polynomials", Miskolc Mathematical Notes

Log-convexity strikes me as a very natural condition so I thought it was of interest, while if I'm reading it right Fubini polynomials are a generalisation that has received a lot of attention (I found lots of results when searching). Maybe the polynomials are notable in their own right but should still get some treatment here. The others seemed like they would fit in "Applications" as well as what is currently there.

On "may be useful to illustrate ties with more than three objects", I think the image is fine but "Weak orderings arrange their elements into a sequence allowing ties" might be clearer with an example (it could be inline). Explaining the connection to Bell numbers in the lead in elementary terms is also possible. With WP:ONEDOWN in mind I think a high schooler could get a lot out of use out of a well-written lead on this topic. I'm not suggesting a ton of wordiness glossing "weak order", "partition" etc., but an example like the one I gave above.

In GA criteria terms it's 1(a) (Wikipedia:Make technical articles understandable) and 3(a) (Broadness) that I'm directing my attention to as I think the other criteria are met. — Bilorv (talk) 10:33, 20 April 2024 (UTC)

Tonight's updates:

Added log-convexity (in the first paragraph of the summation section, since that's how it was proved in the reference I used).

Added a definition and example section with more examples including the connection to ordered partitions that you wanted elaborated.

Expanded the lead with a brief summary of the history section, so now all sections are represented by summarized material in the lead and the lead is longer.

Spelled out in words rather than formulas how $P$ comes from Pascal's triangle.

Searched some more but so far no luck finding a source for the simple and easily-proved bound $a(n)\leq (n+1)^{n-1}$ (via Cayley's formula). —David Eppstein (talk) 06:47, 22 April 2024 (UTC)

Another daily update: I added an anecdote about Knuth and OEIS to the history section, and a paragraph about parking functions to the application section, after finding a source that used parking functions to prove the simple lower and upper bounds I wanted to include. There's also some new text giving some explanation for why you would want to determine the exponential generating function. —David Eppstein (talk) 06:18, 23 April 2024 (UTC)

Re "is the approximation good for large": I added an explanation that (like Stirling) it has multiplicative error close to 1. Re "can you mention the base of the log in prose": it really isn't ambiguous in mathematics articles, but ok, done. Re "outcomes of a multi-candidate election": I agree this is not a great example (not all voting systems produce a meaningful ranking of all candidates, for example); removed. I'm not actually familiar with the tripos outcome system so I didn't try to use that as a replacement.

Also, skipping ahead: "The short description says "Number of weak orderings", which doesn't tell a layperson anything. It should be something like "Topic in mathematics"." I very strongly disagree. There are two main purposes of short descriptions: (1) when you search on mobile you see both titles and short descriptions; (2) some articles' see also sections use short descriptions to gloss their entries. In both cases you don't need a precise rigorous definition of the topic (WP:SDNOTDEF) but the short description does need to add information, relative to the bare title, to help readers figure out which search hit is the one they want or how a see also link might relate to the article listing it. When an article has a title that already suggests it might be mathematical, like "ordered Bell number", a short description like "topic in mathematics" provides precisely zero information to readers. It is unhelpful. You might as well just change all short descriptions of all articles to "Wikipedia article" and make them totally useless everywhere. On the other hand, "number of weak orderings" is short enough to serve as a short description, continues to suggest that the article is mathematical to the uninformed, and also helps inform mathematically-literate readers who aren't familiar with the specific topic to get a rough idea what it is about. Put it another way: imagine the searches one might do that have ordered Bell numbers as one of their hits. Among the people who might make such a search, and the searches they perform, how likely is it that one of these short descriptions will make a meaningful distinction between this topic and the other search results? The short description more likely to make such a distinction (within the character limit) is the better short description. —David Eppstein (talk) 07:20, 24 April 2024 (UTC)

Only one update today: I tried tackling the Kemeny paragraph by removing the technical description and instead attempting to explain it by example. —David Eppstein (talk) 07:34, 25 April 2024 (UTC)