Talk:Ordered Bell number/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

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)

I have changed the first paragraph of the summation section in an attempt to more accessibly explain the first summation formula. I moved combination locks earlier in the applications section. As for the last specific comment, on OEIS: I think it's generally considered reliable, and Wikipedia:Reliable sources/Noticeboard/Archive 420#Is OEIS reliable for this use? agrees. It has a significant level of editorial control and review of submitted content, by the members of a small and selective editorial board; in my experience every addition must pass through two levels of review. As for "what triangle of numbers": when an OEIS entry like [10] describes itself as being a "triangle of numbers", that means that the sequence describes the row-by-row ordering of the triangle. See for instance Pascal's triangle [11] where maybe this pattern is more clear. I have rewritten the footnote in an attempt to clarify this. Next I'll try looking through your suggested additional sources to see whether there's an more expansion that would be appropriate. Re the first one by Qing Zou: we now have better sources both for log-convexity and for tighter simple bounds $n!\leq a(n)\leq (n+1)^{n-1}$ so although it was useful for suggesting those two directions of expansion I don't think it's needed as a source itself. —David Eppstein (talk) 06:33, 28 April 2024 (UTC)

Just a note that I have been following these changes/explanations and I'm happy with them. I think this review should be marked on hold (and probably should have been two weeks ago) but as long as progress is being made I've no desire to set a particular deadline. I may have lower availability in the next fortnight but will prioritise this over other Wikipedia work. Two points: (1) "As has already been mentioned, the ordered Bell numbers count ... ordered multiplicative partitions of squarefree numbers" – am I missing a mention or is this only covered with the same brevity in the lead? (2) The Kemeny paragraph is much simpler now but something feels off about By the "complexity" of a relation he means the number of other relations ... when that's the first mention of "complexity". Could it be: He describes the "complexity" of a relation—the number of other relations ...? — Bilorv (talk) 21:20, 28 April 2024 (UTC)

Thanks! Given the slow pace at which I've been finding time to work on this article I can hardly complain if you also have limited upcoming availability. And I'd rather the revisions be thorough than that they be fast. —David Eppstein (talk) 21:54, 28 April 2024 (UTC)

Re: does this article need further expansion from the many additional sources? Searching Google Scholar for likely phrases like "ordered bell", "fubini number", "number of preferential arrangements" etc finds far too many publications to cite (768, 116, and 126 respectively), many in preprint form, in low-quality journals, or with very few citations. As one of the better recent ones states, "there are many variants of Fubini numbers". As a way of being more selective, I tried looking for the ones with signed reviews on MathSciNet; this finds many fewer hits but did not turn up much more that I thought should be added. As a principled way of seeking missing topics, rather than trusting my own search skills and value judgements, I decided to scan the OEIS entry on these topics to make sure that the main claims for that entry were also repeated here. I don't think we should cover everything OEIS does or remove material it doesn't cover, but OEIS provides an up-to-date survey on the topic and can reasonably be expected to mention its most important aspects. Based on this, I made the following changes:

• Added names (or really descriptions) as "the number of X" (where X is one of the ways of naming weak orders) to the lead.
• Briefly discuss compositions (unlabeled weak orders) in the definition section.
• Added Coxeter complexes to applications. I vaguely recall thinking about adding this long ago and deciding against because it was too technical, but maybe it is important enough to include anyway.

Only partway through, more to come. —David Eppstein (talk) 07:08, 29 April 2024 (UTC)

Ordered multiplicative partitions expanded into its own paragraph in applications, since (as you noticed) we previously had only a call-forward and call-back with no substance. This also provided an opportunity to connect again with the unlabeled weak orders mentioned in definitions. —David Eppstein (talk) 05:31, 30 April 2024 (UTC)

Some more updates:

• The fuss over logs appears to have mostly died down. No significant change to content was in play, just equation formatting. The current version of that part is more concise than the previous one (despite the extra variable), doesn't combine a division with the exponentiation (the part I strenuously objected to because I found it confusing myself), doesn't make invalid mixtures of $\sim$ and $\approx$ (as one suggestion did), and doesn't need binary logarithms (not something I minded but others apparently did).
• IntGrah made some improvements to the links in the approximation formula paragraph. I think they are relevant and not too many.
• I found an explanation for the Eulerian number summation formula in the same source the formula comes from. It turns out to be quite close to the parking function material but explaining the connection might veer too far into original research so for now they're separate and not connected to each other.
• From OEIS (and then another source) I found Ramanujan's use of these numbers to approximate log 2, now at the end of the approximation section
• More additions in the application section involve the moments of a geometric distribution (from OEIS) and calculating resistance in a hypercube (from Pippenger, and Pippenger's main reason for discussing these numbers).
• I made various improvements to wording (especially removing "count the number of" in favor of "count"), footnote ordering (to put them back in numerical order) and reference author and journal linking (including a new article for Toka Diagana).

There might still be a few more points to add from OEIS; I haven't completed my scan of that. —David Eppstein (talk) 07:03, 3 May 2024 (UTC)

@Bilorv: Ok, I think I'm done checking OEIS references, incoming wikilinks, and scholar searches to find more not-already-covered materials. Since the last update, my changes include:

• Adding a conjecture from OEIS that there is a modular identity for every modulus
• Splitting the overlong applications section into subsections involving combinatorial enumeration and other applications
• Adding an application to load balancing in the management of factory workers
• Adding an application to computational origami
• Adding an application to non-commutative algebra
• Adding an application to spam filtering

Not added: a supposed application in certain high-energy physics calculations that I don't understand and can't evaluate the significance of [12] [13]. Anyway, I think I've reached a stable point again, so it's ready for you to look over again. —David Eppstein (talk) 20:45, 4 May 2024 (UTC)