|
| |
|
|
A359762
|
|
Array read by ascending antidiagonals. T(n, k) = n!*[x^n] exp(x + (k/2) * x^2). A generalization of the number of involutions (or of 'telephone numbers').
|
|
8
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 10, 7, 4, 1, 1, 1, 26, 25, 10, 5, 1, 1, 1, 76, 81, 46, 13, 6, 1, 1, 1, 232, 331, 166, 73, 16, 7, 1, 1, 1, 764, 1303, 856, 281, 106, 19, 8, 1, 1, 1, 2620, 5937, 3844, 1741, 426, 145, 22, 9, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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}];
|
|
|
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
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
