A127717 -id:A127717 - cp's OEIS frontend

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

Christian G. Bower, Apr 25 2000

The n-th row consists of coefficients of the characteristic polynomial of the adjacency matrix of the complete n-graph.
Triangle of coefficients of det(M(n)) where M(n) is the n X n matrix m(i,j)=x if i=j, m(i,j)=i/j otherwise. - Benoit Cloitre, Feb 01 2003
T is an example of the group of matrices outlined in the table in A132382--the associated matrix for rB(0,1). The e.g.f. for the row polynomials is exp(x*t) * exp(x) *(1-x). T(n,k) = Binomial(n,k)* s(n-k) where s = (1,0,-1,-2,-3,...) with an e.g.f. of exp(x)*(1-x) which is the reciprocal of the e.g.f. of A000166. - Tom Copeland, Sep 10 2008
Row sums are: {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...}. - Roger L. Bagula, Feb 20 2009
T is related to an operational calculus connecting an infinitesimal generator for fractional integro-derivatives with the values of the Riemann zeta function at positive integers (see MathOverflow links). - Tom Copeland, Nov 02 2012
The submatrix below the null subdiagonal is signed and row reversed A127717. The submatrix below the diagonal is A074909(n,k)s(n-k) where s(n)= -n, i.e., multiply the n-th diagonal by -n. A074909 and its reverse A135278 have several combinatorial interpretations. - Tom Copeland, Nov 04 2012
T(n,k) is the difference between the number of even (A145224) and odd (A145225) permutations (of an n-set) with exactly k fixed points. - Julian Hatfield Iacoponi, Aug 08 2024

			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

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.

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

Cf. A005563, A005564 (absolute values of columns 1, 2).
Cf. A008290, A133314, A238363, A238385.
Cf. A000312.
Cf. A145224, A145225, A003221, A000387.

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 *)

T(n,k)=(1-n+k)*if(k<0 || k>n,0,n!/k!/(n-k)!)

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 formalism of A133314 applies to the pair of entries A008290 and A055137.
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)
T(n,k) = A145224(n,k) - A145225(n,k).
T(n,k) = binomial(n,k)*(A003221(n-k)-A000387(n-k)). (End)

Additional comments from Michael Somos, Jul 04 2002

A373417 Triangle T(n,k) for the number of permutations in symmetric group S_n with (n-k) fixed points and an even number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k<=n that contain an even number of parts.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 0, 15, 20, 1, 0, 0, 0, 45, 120, 130, 1, 0, 0, 0, 105, 420, 910, 924, 1, 0, 0, 0, 210, 1120, 3640, 7392, 7413, 1, 0, 0, 0, 378, 2520, 10920, 33264, 66717, 66744, 1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476

Offset: 0

Julian Hatfield Iacoponi, Jun 04 2024

A343418(n) + a(n) = A098825(n) = partial derangement "rencontres" triangle.
A343418(n) - a(n) = (k-1) * binomial(n,k) = A127717(n-1,k-1).
Difference of 1st and 2nd leading diagonals (n > 0).
T(n,n) - T(n,n-1) = -1,0,0,3,5,10,14,21,27,36,44,...
                  = (-1) + (1+0) + (3+2) + (5+4) + (7+6) + (9+8) + ...
Cf. A176222(n) with 2 terms -1,0 prepended (moving its offset from 3 to 1).

			Triangle array T(n,k):
  n:  {k<=n}
  0:  {1}
  1:  {1, 0}
  2:  {1, 0, 0}
  3:  {1, 0, 0, 0}
  4:  {1, 0, 0, 0,   3}
  5:  {1, 0, 0, 0,  15,   20}
  6:  {1, 0, 0, 0,  45,  120,   130}
  7:  {1, 0, 0, 0, 105,  420,   910,    924}
  8:  {1, 0, 0, 0, 210, 1120,  3640,   7392,   7413}
  9:  {1, 0, 0, 0, 378, 2520, 10920,  33264,  66717,  66744}
  10: {1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476}
T(n,0) = 1 due to sole permutation in S_n with n fixed points, namely the identity permutation, with 0 non-fixed point cycles, an even number. (T(0,0)=1 relies on S_0 containing an empty permutation.)
T(n,1) = 0 due to no permutations in S_n with (n-1) fixed points.
T(n,2) = T(n,3) = 0 due to only non-unity partitions of 2 and 3 being of odd length, namely the trivial partitions (2),(3).
Example:
T(4,4) = 3 since S_4 contains 3 permutations with 0 fixed points and an even number of non-fixed point cycles, namely the derangements: (12)(34),(13)(24),(14)(23).
Worked Example:
T(7,6) = 910 permutations in S_7 with 1 fixed point and an even number of non-fixed point cycles.
T(7,6) = 910 possible (4,2)- and (3,3)-cycles of 7 items.
N(n,y) = possible y-cycles of n items.
N(n,y) = (n!/(n-k)!) / (M(y) * s(y)).
y = partition of k<=n with q parts = (p_1, p_2, ..., p_i, ..., p_q)
s.t. k = Sum_{i=1..q} p_i.
Or:
y = partition of k<=n with d distinct parts, each with multiplicity m_j = (y_1^m_1, y_2^m_2, ..., y_j^m_j, ..., y_d^m_d)
s.t. k = Sum_{j=1..d} m_j*y_j.
M(y) = Product_{i=1..q} p_i = Product_{j=1..d} y_j^m_j.
s(y) = Product_{j=1..d} m_j! ("symmetry of repeated parts").
Note: (n!/(n-k)!) / s(y) = multinomial(n, {m_j}).
Therefore:
T(7,6) = N(7,y=(4,2)) + N(7,y=(3^2))
       = (7!/(4*2)) + (7!/(3^2)/2!)
       = 7! * (1/8 + 1/18)
       = 5040 * (13/72)
T(7,6) = 910.

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)

Cf. A373418 (odd case), A373339 (row sums), A216778 (main diagonal).

b:= proc(n, t) option remember; `if`(n=0, t, add(expand(`if`(j>1, x^j, 1)*
      b(n-j, irem(t+signum(j-1), 2)))*binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1)):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 04 2024

Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)), {k, 0, n}], {n, 0, 10}]

T(n,k) = (n!/(n-k)!/2) * (Sum_{j=0..k} (-1)^j/j! - (k-1)/k!) Cf. Sum_{j=0..k} (-1)^j/j! = A053557(k) / A053556(k).

A127718 A007318 * A002260 as infinite lower triangular matrices; A002260 = [1; 1,2; 1,2,3; ...].

Original entry on oeis.org

1, 2, 2, 4, 6, 3, 8, 14, 12, 4, 16, 30, 33, 20, 5, 32, 62, 78, 64, 30, 6, 64, 126, 171, 168, 110, 42, 7, 128, 254, 360, 396, 320, 174, 56, 8, 256, 510, 741, 876, 815, 558, 259, 72, 9, 512, 1022, 1506, 1864, 1910, 1536, 910, 368, 90, 10, 1024, 2046, 3039, 3872, 4240

Offset: 1

Gary W. Adamson, Jan 25 2007

Binomial transform of A002260.

Row sums = A084851: (1, 4, 13, 38, 104, 272, ...) A002260 * A007318 = A127717.

			First few rows of the triangle:
   1;
   2,   2;
   4,   6,   3;
   8,  14,  12,   4;
  16,  30,  33,  20,   5;
  32,  62,  78,  64,  30,  6;
  64, 126, 171, 168, 110, 42, 7;
  ...

Cf. A002260, A007318, A084851, A127717.

A007318 := proc(n,k) binomial(n,k) ; end: A002260 := proc(n,k) if k <= n then k; else 0 ; fi ; end: A127718 := proc(n,k) add( A007318(n-1,i-1)*A002260(i,k),i=1..n) ; end: for n from 1 to 15 do for k from 1 to n do printf("%d,",A127718(n,k)) ; od: od: # R. J. Mathar, Oct 02 2007

T(n,k) = Sum_{i=1..n} A007318(n-1,i-1)*A002260(i,k). - R. J. Mathar, Oct 02 2007

More terms from R. J. Mathar, Oct 02 2007

A373418 Triangle read by rows: T(n,k) is the number of permutations in symmetric group S_n with (n-k) fixed points and an odd number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k <= n that contain an odd number of parts.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 3, 2, 0, 0, 6, 8, 6, 0, 0, 10, 20, 30, 24, 0, 0, 15, 40, 90, 144, 135, 0, 0, 21, 70, 210, 504, 945, 930, 0, 0, 28, 112, 420, 1344, 3780, 7440, 7420, 0, 0, 36, 168, 756, 3024, 11340, 33480, 66780, 66752, 0, 0, 45, 240, 1260, 6048, 28350, 111600, 333900, 667520, 667485

Offset: 0

Julian Hatfield Iacoponi, Jun 04 2024

a(n) + A343417(n) = A098825(n) = partial derangement "rencontres" triangle.
a(n) - A343417(n) = (k-1) * binomial(n,k) = A127717(n-1,k-1).
Difference of 2nd and 1st leading diagonals (n > 0):
T(n,n-1) - T(n,n) = 0,-1,1,2,6,9,15,20,28,35,45,54,...
                  = (0-1) + (2+1) + (4+3) + (6+5) + (8+7) + (10+9) + ...
Cf. A084265(n) with 2 terms 0,-1 prepended (moving its offset from 0 to -2).

			Triangle begins:
   n: {k<=n}
   0: {0}
   1: {0, 0}
   2: {0, 0,  1}
   3: {0, 0,  3,   2}
   4: {0, 0,  6,   8,    6}
   5: {0, 0, 10,  20,   30,   24}
   6: {0, 0, 15,  40,   90,  144,   135}
   7: {0, 0, 21,  70,  210,  504,   945,    930}
   8: {0, 0, 28, 112,  420, 1344,  3780,   7440,   7420}
   9: {0, 0, 36, 168,  756, 3024, 11340,  33480,  66780,  66752}
  10: {0, 0, 45, 240, 1260, 6048, 28350, 111600, 333900, 667520, 667485}
T(n,0) = 0 because the sole permutation in S_n with n fixed points, namely the identity permutation, has 0 non-fixed point cycles, not an odd number.
T(n,1) = 0 because there are no permutations in S_n with (n-1) fixed points.
Example:
T(3,3) = 2 since S_3 contains 3 permutations with 0 fixed points and an odd number of non-fixed point cycles, namely the derangements (123) and (132).
Worked Example:
T(7,6) = 945 permutations in S_7 with 1 fixed point and an odd number of non-fixed point cycles;
T(7,6) = 945 possible 6- and (2,2,2)-cycles of 7 items.
N(n,y) = possible y-cycles of n items;
N(n,y) = (n!/(n-k)!) / (M(y) * s(y)).
y = partition of k<=n with q parts = (p_1, p_2, ..., p_i, ..., p_q) such that k = Sum_{i=1..q} p_i.
Or:
y = partition of k<=n with d distinct parts, each with multiplicity m_j = (y_1^m_1, y_2^m_2, ..., y_j^m_j, ..., y_d^m_d) such that k = Sum_{j=1..d} m_j*y_j.
M(y) = Product_{i=1..q} p_i = Product_{j=1..d} y_j^m_j.
s(y) = Product_{j=1..d} m_j! ("symmetry of repeated parts").
Note: (n!/(n-k)!) / s(y) = multinomial(n, {m_j}).
Therefore:
T(7,6) = N(7,y=(6)) + N(7,y=(2^3))
       = (7!/6) + (7!/(2^3)/3!)
       = 7! * (1/6 + 1/48)
       = 5040 * (3/16);
T(7,6) = 945.

Cf. A373417 (even case), A373340 (row sums), A216779 (main diagonal).

b:= proc(n, t) option remember; `if`(n=0, t, add(expand(`if`(j>1, x^j, 1)*
      b(n-j, irem(t+signum(j-1), 2)))*binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..10);

Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)),{k,1,n}], {n,1,10}]

T(n,k) = (n!/(n-k)!/2) * ((Sum_{j=0..k} (-1)^j/j!) + (k-1)/k!). Cf. Sum_{j=0..k} (-1)^j/j! = A053557(k) / A053556(k).

cp's OEIS Frontend

A055137 Regard triangle of rencontres numbers (see A008290) as infinite matrix, compute inverse, read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A373417 Triangle T(n,k) for the number of permutations in symmetric group S_n with (n-k) fixed points and an even number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k<=n that contain an even number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A127718 A007318 * A002260 as infinite lower triangular matrices; A002260 = [1; 1,2; 1,2,3; ...].

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula