OFFSET
0,8
COMMENTS
The array is a generalization of the number of involutions of permutations on n letters, A000085, also known as 'telephone numbers'. According to Bednarz et al. the telephone number interpretation "is due to John Riordan, who noticed that T(n, 1) is the number of connection patterns in a telephone system with n subscribers."
In graph theory, the n-th telephone number is the total number of matchings of a complete graph K_n (see the Wikipedia entry). Assuming a network with k possibilities of connections leads to a network that can be modeled by a complete multigraph K(n, k). The total number of connection patterns in such a network is given by T(n, k).
REFERENCES
John Riordan, Introduction to Combinatorial Analysis, Dover (2002).
LINKS
Urszula Bednarz and Małgorzata Wołowiec-Musiał, On a new generalization of telephone numbers, Turkish Journal of Mathematics: Vol. 43: No. 3, (2019).
Wikipedia, Telephone numbers.
FORMULA
T(n, k) = Sum_{j=0..n, j even} binomial(n, j) * (j - 1)!! * k^(j/2).
T(n, k) = T(n, k-1) + n*(k-1)*T(n, k-2) for n >= 2, T(n, 0) = T(n, 1) = 1.
T(n, k) = i^(-n) * (2*k)^(n/2) * KummerU(-n/2, 1/2, -1/(2*k))) for k >= 1, and T(n, 0) = 1.
EXAMPLE
Array T(n, k) starts:
[n\k] 0 1 2 3 4 5 6 7
--------------------------------------------------------------
[0] 1, 1, 1, 1, 1, 1, 1, 1, ... [A000012]
[1] 1, 1, 1, 1, 1, 1, 1, 1, ... [A000012]
[2] 1, 2, 3, 4, 5, 6, 7, 8, ... [A000027]
[3] 1, 4, 7, 10, 13, 16, 19, 22, ... [A016777]
[4] 1, 10, 25, 46, 73, 106, 145, 190, ... [A100536]
[5] 1, 26, 81, 166, 281, 426, 601, 806, ...
[6] 1, 76, 331, 856, 1741, 3076, 4951, 7456, ...
[7] 1, 232, 1303, 3844, 8485, 15856, 26587, 41308, ...
[8] 1, 764, 5937, 21820, 57233, 123516, 234529, 406652, ...
[9] 1, 2620, 26785, 114076, 328753, 757756, 1510705, 2719900, ...
MAPLE
T := (n, k) -> add(binomial(n, j)*doublefactorial(j-1)*k^(j/2), j = 0..n, 2):
for n from 0 to 9 do lprint(seq(T(n, k), k = 0..7)) od;
T := (n, k) -> ifelse(k=0, 1, I^(-n)*(2*k)^(n/2)*KummerU(-n/2, 1/2, -1/(2*k))):
seq(seq(simplify(T(n-k, k)), k = 0..n), n = 0..10);
T := proc(n, k) exp(x + (k/2)*x^2): series(%, x, 16): n!*coeff(%, x, n) end:
seq(lprint(seq(simplify(T(n, k)), k = 0..8)), n = 0..9);
T := proc(n, k) option remember; if n = 0 or n = 1 then 1 else T(n, k-1) +
n*(k-1)*T(n, k-2) fi end: for n from 0 to 9 do seq(T(n, k), k=0..9) od;
# Only to check the interpretation as a determinant of a lower Hessenberg matrix:
gen := proc(i, j, n) local ev, tv; ev := irem(j+i, 2) = 0; tv := j < i and not ev;
if j > i + 1 then 0 elif j = i + 1 then -1 elif j <= i and ev then 1
elif tv and i < n then x*(n + 1 - i) - 1 else x fi end:
det := M -> LinearAlgebra:-Determinant(M):
p := (n, k) -> subs(x = k, det(Matrix(n, (i, j) -> gen(i, j, n)))):
for n from 0 to 9 do seq(p(n, k), k = 0..7) od;
MATHEMATICA
T[n_, k_] := Sum[Binomial[n, j] Factorial2[j-1] * If[j==0, 1, k^(j/2)], {j, 0, n, 2}];
Table[T[n-k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 25 2023 *)
PROG
(Python)
from math import factorial, comb
def oddfactorial(n: int) -> int:
return factorial(2 * n) // (2**n * factorial(n))
def T(n: int, k: int) -> int:
return sum(comb(n, 2 * j) * oddfactorial(j) * k**j for j in range(n + 1))
for n in range(10): print([T(n, k) for k in range(8)])
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Jan 14 2023
STATUS
approved