|
| |
|
|
A079267
|
|
d(n,s) = number of perfect matchings on {1, 2, ..., n} with s short pairs.
|
|
15
|
|
|
|
1, 0, 1, 1, 1, 1, 5, 6, 3, 1, 36, 41, 21, 6, 1, 329, 365, 185, 55, 10, 1, 3655, 3984, 2010, 610, 120, 15, 1, 47844, 51499, 25914, 7980, 1645, 231, 21, 1, 721315, 769159, 386407, 120274, 25585, 3850, 406, 28, 1, 12310199, 13031514, 6539679, 2052309, 446544, 70371, 8106, 666, 36, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,7
|
|
|
COMMENTS
|
Read backwards, the n-th row of the triangle gives the Hilbert series of the variety of slopes determined by n points in the plane.
Reversal of coefficient array for the polynomials P(n,x) = Sum_{k=0..n} (C(n+k,2k)*(2k)!/(2^k*k!))*x^k*(1-x)^(n-k).
Note that P(n,x) = Sum_{k=0..n} A001498(n,k)*x^k*(1-x)^(n-k). (End)
Equivalent to the original definition: Triangle of fixed-point free involutions on [1..2n] (=A001147) by number of cycles with adjacent integers. - Olivier Gérard, Mar 23 2011
Conjecture: Asymptotically, the n-th row has a Poisson distribution with mean 1. - David Callan, Nov 11 2012
This is also the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_1 X P_2n (i.e., a path of length 2n) such that s such pairs are joined by an edge; equivalently the number of "s-domino" configurations in the game of memory played on a 1 X 2n rectangular array, see [Young]. - Donovan Young, Oct 23 2018
|
|
|
REFERENCES
|
G. Kreweras and Y. Poupard, Sur les partitions en paires d'un ensemble fini totalement ordonné, Publications de l'Institut de Statistique de l'Université de Paris, 23 (1978), 57-74.
|
|
|
LINKS
|
|
|
|
FORMULA
|
d(n, s) = (1/s!) * Sum_{h=s..n} (((-1)^(h-s)*(2*n-h)!/(2^(n-h)*(n-h)!*(h-s)!))).
E.g.f.: exp((x-1)*(1-sqrt(1-2*y)))/sqrt(1-2*y). - Vladeta Jovovic, Dec 15 2008
|
|
|
EXAMPLE
|
Triangle begins:
1
0 1
1 1 1
5 6 3 1
36 41 21 6 1
Production matrix begins
0, 1,
1, 1, 1,
4, 4, 2, 1,
18, 18, 9, 3, 1,
96, 96, 48, 16, 4, 1,
600, 600, 300, 100, 25, 5, 1,
4320, 4320, 2160, 720, 180, 36, 6, 1,
35280, 35280, 17640, 5880, 1470, 294, 49, 7, 1,
322560, 322560, 161280, 53760, 13440, 2688, 448, 64, 8, 1
Complete this by adding top row (1,0,0,0,...) and take inverse: we obtain
1,
0, 1,
-1, -1, 1,
-2, -2, -2, 1,
-3, -3, -3, -3, 1,
-4, -4, -4, -4, -4, 1,
-5, -5, -5, -5, -5, -5, 1,
-6, -6, -6, -6, -6, -6, -6, 1,
-7, -7, -7, -7, -7, -7, -7, -7, 1,
-8, -8, -8, -8, -8, -8, -8, -8, -8, 1 (End)
The 6 involutions with no fixed point on [1..6] with only one 2-cycle with adjacent integers are ((1, 2), (3, 5), (4, 6)), ((1, 3), (2, 4), (5, 6)), ((1, 3), (2, 6), (4, 5)), ((1, 5), (2, 3), (4, 6)), ((1, 5), (2, 6), (3, 4)), and ((1, 6), (2, 5), (3, 4)).
|
|
|
MAPLE
|
d := (n, s) -> 1/s! * sum('((-1)^(h-s)*(2*n-h)!/(2^(n-h)*(n-h)!*(h-s)!))', 'h'=s..n):
option remember ;
if n =0 and k =0 then
1;
elif k > n or k < 0 then
0;
else
procname(n-1, k-1)+(2*n-2-k)*procname(n-1, k)+(k+1)*procname(n-1, k+1) ;
end if;
end proc:
seq(seq( A079267(n, k), k=0..n), n=0..13) ;
|
|
|
MATHEMATICA
|
nmax = 9; d[n_, s_] := (2^(s-n)*(2n-s)!* Hypergeometric1F1[s-n, s-2n, -2])/ (s!*(n-s)!); Flatten[ Table[d[n, s], {n, 0, nmax}, {s, 0, n}]] (* Jean-François Alcover, Oct 19 2011, after Maple *)
|
|
|
PROG
|
(PARI) {T(n, k) = 2^(k-n)*binomial(n, k)*hyperu(k-n, k-2*n, -2)};
for(n=0, 10, for(k=0, n, print1(round(T(n, k)), ", "))) \\ G. C. Greubel, Apr 10 2019
(Sage) [[2^(k-n)*binomial(n, k)*hypergeometric_U(k-n, k-2*n, -2).simplify_hypergeometric() for k in (0..n)] for n in (0..10)] # G. C. Greubel, Apr 10 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
Jeremy Martin (martin(AT)math.umn.edu), Feb 05 2003
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
