A105219 -id:A105219 - cp's OEIS frontend

A144084 T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set.

1, 1, 1, 1, 4, 2, 1, 9, 18, 6, 1, 16, 72, 96, 24, 1, 25, 200, 600, 600, 120, 1, 36, 450, 2400, 5400, 4320, 720, 1, 49, 882, 7350, 29400, 52920, 35280, 5040, 1, 64, 1568, 18816, 117600, 376320, 564480, 322560, 40320

Offset: 0

Abdullahi Umar, Sep 10 2008, Sep 30 2008

T(n,k) is also the number of elements in the Green's J equivalence classes in the symmetric inverse monoid, I sub n.
T(n,k) is also the number of ways to place k nonattacking rooks on an n X n chessboard. It can be obtained by performing P(n,k) permutations of n-columns over each C(n,k) combination of n-rows for the given k-rooks. The rule is also applicable for unequal (m X n) sized rectangular boards. - Antal Pinter, Nov 12 2014
Rows also give the coefficients of the matching-generating polynomial of the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Apr 24 2017
Rows also give the coefficients of the independence polynomial of the n X n rook graph and clique polynomial of the n X n rook complement graph. - Eric W. Weisstein, Jun 13 and Sep 14 2017
T(n,k) is the number of increasing subsequences of length n-k over all permutations of [n]. - Geoffrey Critzer, Jan 08 2023

			T(3,1) = 9 because there are exactly 9 partial bijections (on a 3-element set) of height 1, namely: (1)->(1), (1)->(2), (1)->(3), (2)->(1), (2)->(2), (2)->(3), (3)->(1), (3)->(2), (3)->(3).
Triangle T(n,k) begins:
  1;
  1,  1;
  1,  4,   2;
  1,  9,  18,    6;
  1, 16,  72,   96,   24;
  1, 25, 200,  600,  600,  120;
  1, 36, 450, 2400, 5400, 4320, 720;
  ...

O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, 2009, page 61.
J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995).
Vaclav Kotesovec, Non-attacking chess pieces, 6th ed. (2013), p. 216, p. 218.

Alois P. Heinz, Rows n = 0..140, flattened
Wayne A. Johnson, Exponential Hilbert series of equivariant embeddings, arXiv:1804.04943 [math.RT], 2018.
W. D. Munn, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13-18.
Eric Weisstein's World of Mathematics, Clique Polynomial
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Eric Weisstein's World of Mathematics, Rook Complement Graph
Eric Weisstein's World of Mathematics, Rook Graph

T(n,k) = |A021010|. Sum of rows of T(n,k) is A002720. T(n,n) is the order of the symmetric group on an n-element set, n!.
Columns k=2..10 are A163102, A179058, A179059, A179060, A179061, A179062, A179063, A179064, A179065.
Cf. A089231, A105219, A295383.

/* As triangle */ [[(Binomial(n,k)^2)*Factorial(k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jun 13 2017

T:= (n, k)-> (binomial(n, k)^2)*k!:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Dec 04 2012

Table[Table[Binomial[n, k]^2 k!,{k, 0, n}], {n, 0, 6}] // Flatten (* Geoffrey Critzer, Dec 04 2012 *)
Table[ CoefficientList[n!*LaguerreL[n, x], x] // Abs // Reverse, {n, 0, 8}] // Flatten (* Jean-François Alcover, Nov 18 2013 *)
CoefficientList[Table[n! x^n LaguerreL[n, -1/x], {n, 0, 8}], x] // Flatten (* Eric W. Weisstein, Apr 24 2017 *)
CoefficientList[Table[(-x)^n HypergeometricU[-n, 1, -(1/x)], {n, 5}],
  x] // Flatten (* Eric W. Weisstein, Jun 13 2017 *)

T(n,k) = k! * binomial(n,k)^2 \\ Andrew Howroyd, Feb 13 2018

T(n,k) = (C(n,k)^2)*k!.
T(n,k) = A007318(n,k) * A008279(n,k). - Antal Pinter, Nov 12 2014
From Peter Bala, Jul 04 2016: (Start)
G.f.: exp(x*t)*I_0(2*sqrt(x)) = 1 + (1 + t)*x/1!^2 + (1 + 4*t + 2*t^2)*x^2/2!^2 + (1 + 9*t + 18*t^2 + 6*t^3)*x^3/3!^2 + ..., where I_0(x) = Sum_{n >= 0} (x/2)^(2*n)/n!^2 is a modified Bessel function of the first kind.
The row polynomials R(n,t) satisfy R(n,t + u) = Sum_{k = 0..n} T(n,k)*t^k*R(n-k,u).
R(n,t) = 1 + Sum_{k = 0..n-1} (-1)^(n-k+1)*n!/k!*binomial(n,k) *t^(n-k)*R(k,t). Cf. A089231. (End)
From Peter Bala, Oct 05 2019: (Start)
E.g.f.: 1/(1 - t*x)*exp(x/(1 - t*x)).
Recurrence for row polynomials: R(n+1,t) = (1 + (2*n+1)*t)R(n,t) - n^2*t^2*R(n-1,t), with R(0,t) = 1 and R(1,t) = 1 + t.
R(n,t) equals the denominator polynomial of the finite continued fraction 1 + n*t/(1 + n*t/(1 + (n-1)*t/(1 + (n-1)*t/(1 + ... + 2*t/(1 + 2*t/(1 + t/(1 + t/(1)))))))). The numerator polynomial is the (n+1)-th row polynomial of A089231. (End)
Sum_{n>=0} Sum_{k=0..n} T(n,k)*y^k*x^n/A001044(n) = exp(y*x)*E(x) where E(x) = Sum_{n>=0} x^n/A001044(n). - Geoffrey Critzer, Jan 08 2023
Sum_{k=0..n} k*T(n,k) = A105219(n). - Alois P. Heinz, Jan 08 2023
T(n,k) = Sum_{d=0..2*k} c(k,d)*n^d, where c(k,d) = Sum_{j=max(d-k,0)..k} binomial(k,j)*A008275(k+j,d)/j!. - Eder G. Santos, Jan 23 2025

A206703 Triangular array read by rows. T(n,k) is the number of partial permutations (injective partial functions) of {1,2,...,n} that have exactly k elements in a cycle. The k elements are not necessarily in the same cycle. A fixed point is considered to be in a cycle.

Original entry on oeis.org

1, 1, 1, 3, 2, 2, 13, 9, 6, 6, 73, 52, 36, 24, 24, 501, 365, 260, 180, 120, 120, 4051, 3006, 2190, 1560, 1080, 720, 720, 37633, 28357, 21042, 15330, 10920, 7560, 5040, 5040, 394353, 301064, 226856, 168336, 122640, 87360, 60480, 40320, 40320

Offset: 0

Geoffrey Critzer, Feb 11 2012

			     1;
     1,     1;
     3,     2,     2;
    13,     9,     6,     6;
    73,    52,    36,    24,    24;
   501,   365,   260,   180,   120,  120;
  4051,  3006,  2190,  1560,  1080,  720,   720;
  ...

Mohammad K. Azarian, On the Fixed Points of a Function and the Fixed Points of its Composite Functions, International Journal of Pure and Applied Mathematics, Vol. 46, No. 1, 2008, pp. 37-44. Mathematical Reviews, MR2433713 (2009c:65129), March 2009. Zentralblatt MATH, Zbl 1160.65015.
Mohammad K. Azarian, Fixed Points of a Quadratic Polynomial, Problem 841, College Mathematics Journal, Vol. 38, No. 1, January 2007, p. 60. Solution published in Vol. 39, No. 1, January 2008, pp. 66-67.

Alois P. Heinz, Rows n = 0..140, flattened
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132.

Columns k = 0..1 give: A000262, A006152.
Main diagonal gives A000142.
Row sums give A002720.
T(2n,n) gives A088026.
Cf. A002720, A052852, A103194, A105219, A331725.

b:= proc(n) option remember; `if`(n=0, 1, add((p-> p+x^j*
      coeff(p, x, 0))(b(n-j)*binomial(n-1, j-1)*j!), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..10);  # Alois P. Heinz, Feb 19 2022

nn = 7; a = 1/(1 - x); ay = 1/(1 - y x); f[list_] := Select[list, # > 0 &]; Map[f, Range[0, nn]! CoefficientList[Series[Exp[a x] ay, {x, 0, nn}], {x, y}]] // Flatten

E.g.f.: exp(x/(1-x))/(1-y*x).
From Alois P. Heinz, Feb 19 2022: (Start)
Sum_{k=1..n} T(n,k) = A052852.
Sum_{k=0..n} k * T(n,k) = A103194(n).
Sum_{k=0..n} (n-k) * T(n,k) =  A105219(n).
Sum_{k=0..n} (-1)^k * T(n,k) = A331725(n). (End)

A152474 Triangle T(n,k) read by rows: Sum_{k=0..binomial(n,2)} T(n,k)q^k = n!Sum_{pi} faq(n,q)/Product_{i=1..n} e(i)!faq(i,q)^e(i), where pi runs over all nonnegative integer solutions to e(1) + 2e(2) + ... + n*e(n) = n and faq(i,q) = Product_{j=1..i} (q^j-1)/(q-1), i = 1..n.

Original entry on oeis.org

1, 1, 3, 1, 13, 8, 8, 1, 73, 63, 89, 78, 41, 15, 1, 501, 544, 909, 1095, 1200, 842, 680, 315, 129, 24, 1, 4051, 5225, 9734, 13799, 18709, 20441, 20520, 18101, 14831, 10200, 5891, 3199, 1109, 314, 35, 1, 37633, 55656, 112370, 177457, 270746, 352969, 442897

Offset: 0

Vladeta Jovovic, Dec 05 2008

			Triangle T(n,k) begins:
    1;
    1;
    3,   1;
   13,   8,   8,    1;
   73,  63,  89,   78,   41,  15,   1;
  501, 544, 909, 1095, 1200, 842, 680, 315, 129, 24, 1;
  ...

Alois P. Heinz, Rows n = 0..36, flattened

Cf. A000262 (first column), A105219(second column), A137341 (row sums), A152534.

T(n,n) gives A346981.

{T(n,k)=local(e_q=sum(j=0,n,x^j/prod(i=1,j,(q^i-1)/(q-1)))+x*O(x^n)); n!*polcoeff(polcoeff(exp(e_q-1),n,x)*prod(j=1,n,(q^j-1)/(q-1)),k,q)} \\ Paul D. Hanna, Dec 15 2008

Sum_{k=0..binomial(n,2)} T(n,k)*exp(2*Pi*I*k/n) = n!. - Vladeta Jovovic, Dec 05 2008
From Paul D. Hanna, Dec 15 2008: (Start)
E.g.f.: A(x,q) = exp(e_q(x,q) - 1) = Sum_{n>=0} Sum_{k=0..n(n-1)/2} T(n,k)*q^k*x^n/(n!*faq(n,q)) where e_q(x,q) = Sum_{n>=0} x^n/faq(n,q) and faq(n,q) = Product_{j=1..n} (q^j-1)/(q-1) with faq(0,q)=1.
Sum_{k=0..n(n-1)/2} T(n,k)*(-1)^k = n!*A000110((n+1)/2), where A000110 is the Bell numbers. (End)

T(0,0)=1 prepended by Alois P. Heinz, Feb 04 2018

A341200 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Sum_{j=0..n} j^k * (n-j)! * binomial(n,j)^2.

Original entry on oeis.org

1, 0, 2, 0, 1, 7, 0, 1, 6, 34, 0, 1, 8, 39, 209, 0, 1, 12, 63, 292, 1546, 0, 1, 20, 117, 544, 2505, 13327, 0, 1, 36, 243, 1168, 5225, 24306, 130922, 0, 1, 68, 549, 2800, 12525, 55656, 263431, 1441729, 0, 1, 132, 1323, 7312, 33425, 145836, 653023, 3154824, 17572114

Offset: 0

Seiichi Manyama, Feb 06 2021

			Square array begins:
     1,    0,    0,     0,     0,     0, ...
     2,    1,    1,     1,     1,     1, ...
     7,    6,    8,    12,    20,    36, ...
    34,   39,   63,   117,   243,   549, ...
   209,  292,  544,  1168,  2800,  7312, ...
  1546, 2505, 5225, 12525, 33425, 97125, ...

Columns k=0..4 gives A002720, A103194, A105219, A105218, A341196.
Main diagonal gives A341197.
Cf. A289192.

T[n_, k_] := Sum[If[j == k == 0, 1, j^k] * (n - j)! * Binomial[n, j]^2, {j, 0, n}]; Table[T[k, n - k], {n, 0, 9}, {k, 0, n}] // Flatten (* Amiram Eldar, Feb 06 2021 *)

T(n, k) = sum(j=0, n, j^k*(n-j)!*binomial(n, j)^2);

About e.g.f. of column k, see A105218 or A105219 comment.

A344054 a(n) = Sum_{k = 0..n} E1(n, k)*k^2, where E1 are the Eulerian numbers A173018.

Original entry on oeis.org

0, 0, 1, 8, 64, 540, 4920, 48720, 524160, 6108480, 76809600, 1037836800, 15008716800, 231437606400, 3792255667200, 65819609856000, 1206547550208000, 23297526540288000, 472708591939584000, 10055994967130112000, 223826984752250880000, 5202760944485744640000, 126075414965721661440000, 3179798058882852126720000, 83346901966165164687360000, 2267221868000212451328000000

Offset: 0

Peter Luschny, May 11 2021

nonn

The Eulerian transform of the squares.

Transforms of the squares: A151881 (StirlingCycle), A033452 (StirlingSet), A105219 (Laguerre), A103194 (Lah), A065096 (SchröderBig), A083411 (Fubini), A141222 (Narayana), A000330 (Units A000012).

Cf. A173018.

a := n -> add(combinat[eulerian1](n, k)*k^2, k = 0..n):
# Recurrence:
a := proc(n) option remember; if n < 2 then 0 elif n = 2 then 1 else
((n-3)*(n-1)*(23*n-44)*a(n-2) + ((159 - 7*n)*n - 286)*a(n-1))/(16*(n - 2)) fi end:
seq(a(n), n = 0..29);

a[n_] := Sum[Sum[(-1)^j Binomial[n + 1, j] k^2 (k + 1 - j)^n, {j,0,k}], {k,0,n}]; a[0] := 0; Table[a[n], {n, 0, 25}]

def aList(len):
    R. = PowerSeriesRing(QQ, default_prec=len+2)
    f = x^2*(-x^2 + x - 3)/(6*(x - 1)^3)
    return f.egf_to_ogf().list()[:len]
print(aList(20))

a(n) = n! * [x^n] x^2*(-x^2 + x - 3)/(6*(x - 1)^3).
a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^j*binomial(n + 1, j)*k^2*(k + 1 - j)^n.
a(n) = ((n - 3)*(n - 1)*(23*n - 44)*a(n-2) + ((159 - 7*n)*n - 286)*a(n-1))/(16*(n - 2)) for n >= 3.

cp's OEIS Frontend

A144084 T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A206703 Triangular array read by rows. T(n,k) is the number of partial permutations (injective partial functions) of {1,2,...,n} that have exactly k elements in a cycle. The k elements are not necessarily in the same cycle. A fixed point is considered to be in a cycle.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A152474 Triangle T(n,k) read by rows: Sum_{k=0..binomial(n,2)} T(n,k)*q^k = n!*Sum_{pi} faq(n,q)/Product_{i=1..n} e(i)!*faq(i,q)^e(i), where pi runs over all nonnegative integer solutions to e(1) + 2*e(2) + ... + n*e(n) = n and faq(i,q) = Product_{j=1..i} (q^j-1)/(q-1), i = 1..n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A341200 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Sum_{j=0..n} j^k * (n-j)! * binomial(n,j)^2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A344054 a(n) = Sum_{k = 0..n} E1(n, k)*k^2, where E1 are the Eulerian numbers A173018.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

A152474 Triangle T(n,k) read by rows: Sum_{k=0..binomial(n,2)} T(n,k)q^k = n!Sum_{pi} faq(n,q)/Product_{i=1..n} e(i)!faq(i,q)^e(i), where pi runs over all nonnegative integer solutions to e(1) + 2e(2) + ... + n*e(n) = n and faq(i,q) = Product_{j=1..i} (q^j-1)/(q-1), i = 1..n.