A122525 Triangle read by rows: G(s, rho) = ((s-1)!/s)*Sum_{i=0..s-1} ((s-i)/i!)*(s*rho)^i.

1, 1, 1, 2, 4, 3, 6, 18, 24, 16, 24, 96, 180, 200, 125, 120, 600, 1440, 2160, 2160, 1296, 720, 4320, 12600, 23520, 30870, 28812, 16807, 5040, 35280, 120960, 268800, 430080, 516096, 458752, 262144, 40320, 322560, 1270080, 3265920, 6123600, 8817984, 9920232, 8503056, 4782969

Offset: 1

Author

Arie Harel, Sep 14 2006

Keywords

• nonn
• tabl

Comments

When s is a positive integer and 0 < rho < 1 then C(s,rho):=(s*rho)^s/G(s,rho)/s is the well-known Erlang delay (or the Erlang's C) formula. This measure is a basic formula of queueing theory. The applications of this formula are in diverse systems where queueing phenomena arise, including telecommunications, production, and service systems. The formula gives the steady-state probability of delay in the M/M/s queueing system. The number of servers is denoted by s and the traffic intensity is denoted by rho, 0 < rho < 1, where rho=(arrival rate)/(service rate)/s.

With offset = 0, T(n,n-k) is the number of partial functions on {1,2,...,n} with exactly k recurrent elements for 0 <= k <= n. Row sums = (n+1)^n. - Geoffrey Critzer, Sep 08 2012

Examples

			G(5, rho) = 24 + 96*rho + 180*rho^2 + 200*rho^3 + 125*rho^4. The coefficients (24, 96, 180, 200, 125) give the 5th line of the triangle.
Triangle begins:
      1;
      1,      1;
      2,      4,       3;
      6,     18,      24,      16;
     24,     96,     180,     200,     125;
    120,    600,    1440,    2160,    2160,    1296;
    720,   4320,   12600,   23520,   30870,   28812,   16807;
   5040,  35280,  120960,  268800,  430080,  516096,  458752,  262144;
  40320, 322560, 1270080, 3265920, 6123600, 8817984, 9920232, 8503056, 4782969;
		

References

• Cooper, R. B. 1981, Introduction to Queueing Theory. Second ed., North Holland, New York.
• Harel, A. 1988. Sharp Bounds and Simple Approximations for the Erlang Delay and Loss Formulas. Management Science, Vol. 34, 959-972.
• Harel, A. and P. Zipkin. 1987a. Strong Convexity Results for Queueing Systems. Operations Research, Vol. 35, No. 3, 405-418.
• Harel, A. and P. Zipkin. 1987b. The Convexity of a General Performance Measure for the Multi-Server Queues. Journal of Applied Probability, Vol. 24, 725-736.
• Jagers, A. A. and E. A. van Doorn, 1991. Convexity of functions which are generalizations of the Erlang loss function and the Erlang delay function. SIAM Review. Vol. 33 (2), 281-282.
• Lee, H. L. and M. A. Cohen. 1983. A Note on the Convexity of Performance Measures of M/M/c Queueing Systems. Journal of Applied Probability, Vol. 20, 920-923.
• Medhi, J. 2003. Stochastic Models in Queueing Theory. Second ed., Academic Press, New York.
• Smith, D.R. and W. Whitt. 1981. Resource Sharing for Efficiency in Traffic Systems. Bell System Technical Journal, Vol. 60, No. 1, 39-55.

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• C. W. J. Beenakker, Entropy and singular-value moments of products of truncated random unitary matrices, arXiv:2501.11085 [quant-ph], 2025. See p. 6.
• E. Brockmeyer, H. L. Halstrøm and Arne Jensen, The Life and Works of A.K. Erlang

Crossrefs

Cf. A066324, A137216, A137227.

Programs

Maple

G:= proc(s) G(s):= (s-1)!/s*add((s-i)/i!*(s*rho)^i, i=0..(s-1)) end:
T:= n-> coeff(G(n), rho, k):
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 08 2012

Mathematica

(* First program *)
nn=6; t=Sum[n^(n-1)x^n/n!,{n,1,nn}]; f[list_]:=Select[list,#>0&]; Map[f,Map[Reverse,Range[0,nn]!CoefficientList[Series[Exp[t]/(1-y t),{x,0,nn}],{x,y}]]]//Grid  (* Geoffrey Critzer, Sep 08 2012 *)
(* Second program *)
T[n_, k_]:= Coefficient[Series[((n-1)!/n)*Sum[(n-j)*(n*x)^j/j!, {j,0,n-1}], {x,0,30}], x, k];
Table[T[n, k], {n,10}, {k,0,n-1}]//Flatten (* G. C. Greubel, Jan 06 2022 *)

Sage

def A122525(n,k): return ( (factorial(n-1)/n)*sum((n-j)*(n*x)^j/factorial(j) for j in (0..n-1)) ).series(x, n+1).list()[k]
flatten([[A122525(n,k) for k in (0..n-1)] for n in (1..12)]) # G. C. Greubel, Jan 06 2022

Formula

An equivalent expression for G(s, rho) that is often used is: G(s, rho) = (1-rho)*(s-1)!*Sum_{i=0..s-1} (s^i*rho^i/i!) + rho^s*s^(s-1).

For s > 0 and rho > 0 one can use the expression: G(s, rho) = (exp(s*rho)*s*rho*(1-rho)*(s-1)*Gamma(s-1, s*rho) + rho^s*s^s)/(s*rho).

For s > 0 and rho > 0 one can also use the integral representation G(s, rho) = ((s*rho)^s/s)*Integral_{t=0..oo} rho*s*exp(-rho*s*t)*t*(1+t)^(s-1) dt.

Multiplying the n-th row entries by n+1 results in triangle A066324 in row reversed form. - Peter Bala, Sep 30 2011

Row generating polynomials are given by (1/n)*D^n(1/(1-x*t)) evaluated at x = 0, where D is the operator exp(x)/(1-x)*d/dx. - Peter Bala, Dec 27 2011