login
Triangle T(n,k) (1 <= k <= n) read by rows: A046936 with rows reversed and offset changed to 1.
4

%I #12 Jan 31 2018 21:51:15

%S 0,1,1,3,2,1,9,6,4,3,31,22,16,12,9,121,90,68,52,40,31,523,402,312,244,

%T 192,152,121

%N Triangle T(n,k) (1 <= k <= n) read by rows: A046936 with rows reversed and offset changed to 1.

%C This is another version of Moser's version (A046936) of Aitken's array (A011971).

%C Although offset 0 is better for A011971 and A046936, for this version offset 1 is more appropriate.

%C Comments from _Don Knuth_, Jan 29 2018 (Start):

%C 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.)

%C 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

%C 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.

%C The same property, but leaving out conditions (ii) and (iii), characterizes Pierce's triangular array A123346. (End)

%H Don Knuth, <a href="/A040027/a040027.txt">Email to N. J. A. Sloane</a>, Jan 29 2018

%e Triangle begins:

%e 0,

%e 1, 1,

%e 3, 2, 1,

%e 9, 6, 4, 3,

%e 31, 22, 16, 12, 9,

%e 121, 90, 68, 52, 40, 31

%e 523, 402, 312, 244, 192, 152, 121

%e ...

%Y Cf. A011971, A040027, A046936, A123346.

%K nonn,tabl,more

%O 1,4

%A _N. J. A. Sloane_, Jan 30 2018, following a suggestion from _Don Knuth_, Jan 29 2018.