Email from Don Knuth to N. J. A. Sloane, Jan 29 2018 Subject: "Gould numbers" First, I've been looking closely at sequence A040027, which will come up in some significant ways in TAOCP Volume 4B. I believe that these numbers are sufficiently important that they amply deserve to be named. And I believe it's best to name them the "Gould numbers", in honor of Henry Gould (who is about to celebrate his 90th birthday). He is the one who submitted A040027; and his 2007 paper with Quaintance led to subsequent work that's quite interesting. It was nice to see that you put Guy's letters to you from 1968 online; this sequence occurs somewhat obliquely therein, as one shown to him that year by Leo Moser. Significantly, Moser also found the generating function. But since Leo never published it, and since you didn't think enough of the sequence at that time to include it in the book with the M-numbered sequences [The Encyclopedia of Integer Sequences, 1995], I put aside an inclination to name the sequence after him. (BTW, Guy slightly misremembered the generating function; divide that one by e.) Guy wrote that Moser got the idea from Aitken's array. The reference to Aitken's paper in A011971 is slightly incorrect: That journal, Edinburgh Mathematical Notes vol 28 (1933), is now online and the page numbers are not "18-33" but "xviii-xxxiii"! Moser's version of Aitken's array is now A046936. (I think a link to Guy's letter would be an appropriate reference there.) I believe OEIS should have a new sequence, which is the same as A046936 but with the triangle reflected left-to-right (compare A123346 to A011971). Namely, the new sequence is 0 1 1 3 2 1 9 6 4 3 31 22 16 12 9 .... [This is now A298804] Furthermore, it's best to number the subscripts of this sequence from 1, not 0; I mean, the entries are a(n,k) for n>=k>=1. [That numbering is implicit in the comments of A123346. By contrast, A011971 and A046936 use 0-origin --- which is usually better, but NOT in this case!] The reason I think 1-origin wins here is that a(n,k) is the number of set partitions (i.e. equivalence classes) in which (i) 1 is not equivalent to 2, ..., nor k; and (ii) the last part, when parts are ordered by their smallest element, has size 1; (iii) that last part isn't simply "1". (Equivalently, n>1.) It's not difficult to prove this characterization of a(k,n). For example, if we know that there are 22 partitions of {1,2,3,4,5} with 1 inequivalent to 2, and 6 partitions of {1,2,3,4} with 1 inequivalent to 2, then there are 6 partitions of {1,2,3,4,5} with 1 inequivalent to 2 and 1 equivalent to 3. Hence there are 16 with 1 equivalent to neither 2 nor 3. The same property, but leaving out conditions (ii) and (iii), characterizes Pierce's triangular array A123346. I tried, some time ago, to state that characterization in the mirror-image triangle A011971; but it becomes very peculiar, with 0-origin indexing; thus my wording had to be corrected by Thijs van Ommen. When one tries to add conditions (ii) and (iii), in order to characterize the elements of A046936 with 0-origin indexing, the task becomes hopeless! With the 1-origin indexing in A123346, I think one of the comments should therefore be that a(n,k) is the number of equivalence classes of [n] in which 1\neq 2, ..., 1\neq k. In Volume 4A, page 418, I also pointed out that a(n,k) is the number of set partitions in which k is the smallest of its block. And in exercise 7.2.1.5--33, I pointed out that a(n,k) is the number of equivalence relations in which 1\neq 2, 2\neq 3, ..., k-1\neq k. (Those other two characterizations do not work for the new triangle I wish to add.) ------ In summary, I'm suggesting that you do the following things: * Create a new sequence for the triangle above. Use 1-origin indexing, and give the combinatorial characterization of a(n,k). I'll be mentioning this in Section 7.2.2.1 of TAOCP (eventually in Volume 4B). * Add a cross reference to the new sequence in A046936. Also link to Guy's letter. * Add three new interpretations of a(n,k) in A123346. * Fix the reference to Aitkin in A011971. * Call A040027 the Gould numbers. Best regards, Don