A055137 Regard triangle of rencontres numbers (see A008290) as infinite matrix, compute inverse, read by rows.
1, 0, 1, -1, 0, 1, -2, -3, 0, 1, -3, -8, -6, 0, 1, -4, -15, -20, -10, 0, 1, -5, -24, -45, -40, -15, 0, 1, -6, -35, -84, -105, -70, -21, 0, 1, -7, -48, -140, -224, -210, -112, -28, 0, 1, -8, -63, -216, -420, -504, -378, -168, -36, 0, 1, -9, -80, -315, -720
Offset: 0
Examples
1; 0,1; -1,0,1; -2,-3,0,1; -3,-8,-6,0,1; ...
(Bagula's matrix has a different sign convention from the list.)
From _Roger L. Bagula_, Feb 20 2009: (Start)
{ 1},
{ 0, 1},
{-1, 0, 1},
{ 2, -3, 0, 1},
{-3, 8, -6, 0, 1},
{ 4, -15, 20, -10, 0, 1},
{-5, 24, -45, 40, -15, 0, 1},
{ 6, -35, 84, -105, 70, -21, 0, 1},
{-7, 48, -140, 224, -210, 112, -28, 0, 1},
{ 8, -63, 216, -420, 504, -378, 168, -36, 0, 1},
{-9, 80, -315, 720, -1050, 1008, -630, 240, -45, 0, 1}
(End)
R(3,x) = (-1)^3*Sum_{permutations p in S_3} sign(p)*(-x)^(fix(p)).
p | fix(p) | sign(p) | (-1)^3*sign(p)*(-x)^fix(p)
========+========+=========+===========================
(123) | 3 | +1 | x^3
(132) | 1 | -1 | -x
(213) | 1 | -1 | -x
(231) | 0 | +1 | -1
(312) | 0 | +1 | -1
(321) | 1 | -1 | -x
========+========+=========+===========================
| R(3,x) = x^3 - 3*x - 2
- _Peter Bala_, Aug 08 2011
References
- Norman Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993. p. 17.
- J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p.184 problem 3.
Links
- Problem B6, The 66th William Lowell Putnam Mathematical Competition Saturday, Dec 03 2005
- M. Bhargava, K. Kedlaya, and L. Ng, Solutions to the 66th William Lowell Putnam Mathematical Competition Saturday, Dec 03 2005
- T. Copeland, Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants
- T. Copeland, Riemann zeta function at positive integers and an Appell sequence of polynomials related to fractional calculus
Crossrefs
Programs
-
Mathematica
M[n_] := Table[If[i == j, x, 1], {i, 1, n}, {j, 1, n}]; a = Join[{{1}}, Flatten[Table[CoefficientList[Det[M[n]], x], {n, 1, 10}]]] (* Roger L. Bagula, Feb 20 2009 *) t[n_, k_] := (k-n+1)*Binomial[n, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 29 2013, after Pari *) -
PARI
T(n,k)=(1-n+k)*if(k<0 || k>n,0,n!/k!/(n-k)!)
Formula
G.f.: (x-n+1)*(x+1)^(n-1) = Sum_(k=0..n) T(n,k) x^k.
T(n, k) = (1-n+k)*binomial(n, k).
k-th column has o.g.f. x^k(1-(k+2)x)/(1-x)^(k+2). k-th row gives coefficients of (x-k)(x+1)^k. - Paul Barry, Jan 25 2004
T(n,k) = Coefficientslist[Det[Table[If[i == j, x, 1], {i, 1, n}, {k, 1, n}],x]. - Roger L. Bagula, Feb 20 2009
From Peter Bala, Aug 08 2011: (Start)
Given a permutation p belonging to the symmetric group S_n, let fix(p) be the number of fixed points of p and sign(p) its parity. The row polynomials R(n,x) have a combinatorial interpretation as R(n,x) = (-1)^n*Sum_{permutations p in S_n} sign(p)*(-x)^(fix(p)). An example is given below.
Note: The polynomials P(n,x) = Sum_{permutations p in S_n} x^(fix(p)) are the row polynomials of the rencontres numbers A008290. The integral results Integral_{x = 0..n} R(n,x) dx = n/(n+1) = Integral_{x = 0..-1} R(n,x) dx lead to the identities Sum_{p in S_n} sign(p)*(-n)^(1 + fix(p))/(1 + fix(p)) = (-1)^(n+1)*n/(n+1) = Sum_{p in S_n} sign(p)/(1 + fix(p)). The latter equality was Problem B6 in the 66th William Lowell Putnam Mathematical Competition 2005. (End)
From Tom Copeland, Jul 26 2017: (Start)
The e.g.f. in Copeland's 2008 comment implies this entry is an Appell sequence of polynomials P(n,x) with lowering and raising operators L = d/dx and R = x + d/dL log[exp(L)(1-L)] = x+1 - 1/(1-L) = x - L - L^2 - ... such that L P(n,x) = n P(n-1,x) and R P(n,x) = P(n+1,x).
P(n,x) = (1-L) exp(L) x^n = (1-L) (x+1)^n = (x+1)^n - n (x+1)^(n-1) = (x+1-n)(x+1)^(n-1) = (x+s.)^n umbrally, where (s.)^n = s_n = P(n,0).
The polynomials of this pair P_n(x) and Q_n(x) are umbral compositional inverses; i.e., P_n(Q.(x)) = x^n = Q_n(P.(x)), where, e.g., (Q.(x))^n = Q_n(x).
The exponential infinitesimal generator (infinigen) of this entry is the negated infinigen of A008290, the matrix (M) noted by Bala, related to A238363. Then e^M = [the lower triangular A008290], and e^(-M) = [the lower triangular A055137]. For more on the infinigens, see A238385. (End)
From the row g.f.s corresponding to Bagula's matrix example below, the n-th row polynomial has a zero of multiplicity n-1 at x = 1 and a zero at x = -n+1. Since this is an Appell sequence dP_n(x)/dx = n P_{n-1}(x), the critical points of P_n(x) have the same abscissas as the zeros of P_{n-1}(x); therefore, x = 1 is an inflection point for the polynomials of degree > 2 with P_n(1) = 0, and the one local extremum of P_n has the abscissa x = -n + 2 with the value (-n+1)^{n-1}, signed values of A000312. - Tom Copeland, Nov 15 2019
From Julian Hatfield Iacoponi, Aug 08 2024: (Start)
Extensions
Additional comments from Michael Somos, Jul 04 2002
Comments