A286030 - OEIS

%I #37 Oct 10 2018 10:02:37

%S 1,1,2,1,6,2,1,8,6,12,1,10,20,20,30,1,12,30,30,20,120,30,1,14,42,42,

%T 70,210,140,210,1,16,56,56,112,336,70,560,420,560,1,18,72,72,168,504,

%U 252,1008,756,630,2520,560

%N Irregular triangle T(n,k) read by rows: Let S be a 3-member set of integers {f,g,h} where f >= g >= h >= 0 and f+g+h = n. Let S(n,k) be an irregular triangle composed of all S listed in reverse lexicographic order by row n. Then T(n,k) = n!*Q/(3*f!*g!*h!), where Q is the number of permutations of S(n,k). (See "Comments" and "Examples" for additional explanation.)

%C See "Example" below for the starting construction of S(n,k) and T(n,k).

%C To understand S(n,k) and Q, consider example S(5,k), i.e., f+g+h = 5, and S(n,k) are listed in reverse lexicographic order. So S(5,k) = {5,0,0}, {4,1,0}, {3,2,0}, {3,1,1}, {2,2,1} k=1..5, respectively. Q is the number of permutations of S(n,k). So Q=3 when S(n,k) = {5,0,0}, {3,1,1} and {2,2,1}; and Q=6 when S(n,k) = {4,1,0} and {3,2,0}.

%C In general, by definition: Q=1 when all members of S(n,k) are equal, Q=3 when S(n,k) contains a pair, and Q=6 when none of the members of S(n,k) is equal.

%C Suppose three equally-matched players are playing a tournament of n games; and for each game there is one winner and two losers. Then S(n,k) is the "overall win record" (where player order does not matter) after n games. Let p be the probability that any S(n,k) occurs after n games. Then p = T(n,k)/3^(n-1). (See also "Example" section.)

%C Generally, when S(n,k) is a z-member set {f,g,h,i..,y}, then Q is the number of permutations of S(n,k), T(n,k) = n!*Q/(z*f!*g!*h!..*y!) and p = T(n,k)/z^(n-1). So when z=2 we get A008314. (Observation prompted by query from Linda Rogers.)

%C For triangle T(n,k):

%C Row sums are 3^(n-1).

%C Row lengths are A001399(n).

%C Final terms in each row are A199127(n).

%C For n >= 3: T(n,2) = 2*n.

%C For n >= 5: T(n,3) = T(n,4) = A002378(n-1) (oblong numbers).

%C For n >= 6: T(n,6) = A007531(n).

%C For n >= 8: T(n,9) = A033487(n-3).

%H Nicolas Behr, Pawel Sobocinski, <a href="https://arxiv.org/abs/1807.00785">Rule Algebras for Adhesive Categories</a>, arXiv:1807.00785 [cs.LO], 2018, also <a href="https://doi.org/10.4230/LIPIcs.CSL.2018.11">LIPIcs 27th EACSL Annual Conference on Computer Science Logic</a> (CSL 2018), Vol. 119, pp. 11:1-11:21.

%e Triangle T(n,k) begins:

%e n/k 1    2    3    4    5   6    7     8    9    10    11    12    13    14

%e 1:  1

%e 2:  1,   2

%e 3:  1,   6,   2

%e 4:  1,   8,   6,  12

%e 5:  1,  10,  20,  20,  30

%e 6:  1,  12,  30,  30,  20, 120,  30

%e 7:  1,  14,  42,  42,  70, 210, 140,  210

%e 8:  1,  16,  56,  56, 112, 336,  70,  560,  420, 560

%e 9:  1,  18,  72,  72, 168, 504, 252, 1008,  756, 630, 2520, 560

%e 10: 1,  20,  90,  90, 240, 720, 420, 1680, 1260, 252, 2520, 5040, 3150, 4200

%e Triangle S(n,k) begins:

%e n/k    1        2        3        4        5        6        7

%e 1:  {1,0,0}

%e 2:  {2,0,0}  {1,1,0}

%e 3:  {3,0,0}  {2,1,0}  {1,1,1}

%e 4:  {4,0,0}  {3,1,0}  {2,2,0}  {2,1,1}

%e 5:  {5,0,0}  {4,1,0}  {3,2,0}  {3,1,1}  {2,2,1}

%e 6:  {6,0,0}  {5,1,0}  {4,2,0}  {4,1,1}  {3,3,0}  {3,2,1}  {2,2,2}

%e T(4,3) = 6 because n=4 and S(4,3) = {2,2,0}; so Q=3 and 3*4!/(3*2!*2!*0!) = 6. Therefore p = 6/27 = 2/9 that the overall win record = {2,2,0} after playing 4 tournament games.

%Y Cf. A001399, A002378, A007531, A008314, A033487, A199127.

%Y Cf. A000041 (partition numbers).

%K nonn,tabf

%O 1,3

%A _Bob Selcoe_, Apr 30 2017