A098825 Triangle read by rows: T(n,k) = number of partial derangements, that is, the number of permutations of n distinct, ordered items in which exactly k of the items are in their natural ordered positions, for n >= 0, k = n, n-1, ..., 1, 0.

1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 6, 8, 9, 1, 0, 10, 20, 45, 44, 1, 0, 15, 40, 135, 264, 265, 1, 0, 21, 70, 315, 924, 1855, 1854, 1, 0, 28, 112, 630, 2464, 7420, 14832, 14833, 1, 0, 36, 168, 1134, 5544, 22260, 66744, 133497, 133496, 1, 0, 45, 240, 1890, 11088, 55650, 222480, 667485, 1334960, 1334961

Offset

0,9

Comments

In other words, T(n,k) is the number of permutations of n letters that are at Hammimg distance k from the identity permutation (cf. Diaconis, p. 112). - N. J. A. Sloane, Mar 02 2007

The sequence d(n) = 1, 0, 1, 2, 9, 44, 265, 1854, 14833, ... (A000166) is the number of derangements, that is, the number of permutations of n distinct, ordered items in which none of the items is in its natural ordered position.

Links

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened

P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.

Chris D. H. Evans, John Hughes and Julia Houston, Significance-testing the validity of idiographic methods: A little derangement goes a long way, British Journal of Mathematical and Statistical Psychology, 1 November 2002, Vol. 55, pp. 385-390.

Eric Weisstein's World of Mathematics, Partial Derangement

Formula

T(0, 0) = 1; d(0) = T(0, 0); for k = n, n-1, ..., 1, T(n, k) = c(n, k) d(n-k) where c(n, k) = n! / [(k!) (n-k)! ]; T(n, 0) = n! - [ T(n, n) + T(n, n-1) + ... + T(n, 1) ]; d(n) = T(n, 0).

T(n,k) = A008290(n,n-k). - Vladeta Jovovic, Sep 04 2006

Assuming a uniform distribution on S_n, the mean Hamming distance is n-1 and the variance is 1 (Diaconis, p. 117). - N. J. A. Sloane, Mar 02 2007

From Manfred Boergens, Oct 25 2022: (Start)

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

T(n,0)=1; T(n, k) = C(n, k)*round(k!/e) = C(n,k)*A000166(k) = C(n, k)*floor(k!/e + 1/2) for k > 0. (End)

Example

Assume d(0), d(1), d(2) are given. Then
  T(3, 3) = c(3, 3)*d(0) = (1)*(1) = 1;
  T(3, 2) = c(3, 2)*d(1) = (3)*(0) = 0;
  T(3, 1) = c(3, 1)*d(2) = (3)*(1) = 3;
  T(3, 0) = 3! - (1 + 0 + 3) = 6 - 4 = 2.
  d(3) = T(3, 0).
Triangle begins:
  1;
  1, 0;
  1, 0,  1;
  1, 0,  3,  2;
  1, 0,  6,  8,   9;
  1, 0, 10, 20,  45,  44;
  1, 0, 15, 40, 135, 264,  265;
  1, 0, 21, 70, 315, 924, 1855, 1854;
  ...

Mathematica

t[0, 0] = 1; t[n_, k_] := Binomial[n, k]*k!*Sum[(-1)^j/j!, {j, 0, k}]; Flatten[ Table[ t[n, k], {n, 0, 10}, {k, 0, n}]] (* Robert G. Wilson v, Nov 04 2004 *)
T[n_, k_] := Binomial[n, n-k] Subfactorial[k];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 01 2021 *)
(* Sum-free code *)
T[n_, k_] = If[k==0, 1, Binomial[n, k] Round[k!/E]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* Manfred Boergens, Oct 25 2022 *)

Prog

(Haskell)
a098825 n k = a098825_tabl !! n !! k
a098825_row n = a098825_tabl !! n
a098825_tabl = map (zipWith (*) a000166_list) a007318_tabl
-- Reinhard Zumkeller, Dec 16 2013

Crossrefs

Mirror of triangle A008290.

Cf. A000166, A007318.

T(2n,n) gives A281262.

Keyword

nonn,tabl

Author

Gerald P. Del Fiacco, Nov 02 2004

Extensions

More terms from Robert G. Wilson v, Nov 04 2004

Status

approved

A084269 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes having chromatic number k, 1 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 5, 12, 3, 1, 0, 17, 64, 26, 4, 1, 0, 44, 475, 282, 46, 5, 1, 0, 182, 5036, 5009, 809, 74, 6, 1, 0, 730, 80947, 149551, 27794, 1940, 110, 7, 1, 0, 4032, 2010328, 7694428, 1890221, 113272, 4125, 156, 8, 1, 0, 25598, 76115143, 667036310, 248580644, 14545025, 389583, 8040, 212, 9, 1

Offset

0,8

Links

Table of n, a(n) for n=0..65.

Eric Weisstein's World of Mathematics, n-Chromatic Graph

Example

Triangle begins:
  1;
  0,   1;
  0,   1,     1;
  0,   3,     2,      1;
  0,   5,    12,      3,     1;
  0,  17,    64,     26,     4,    1;
  0,  44,   475,    282,    46,    5,   1;
  0, 182,  5036,   5009,   809,   74,   6, 1;
  0, 730, 80947, 149551, 27794, 1940, 110, 7, 1;
  ...

Crossrefs

Row sums are A001349.

Columns k=3..7 are A126737, A126738, A126739, A126740, A241702.

Partial row sums include A005142, A076322, A076323, A076324, A076325, A076326, A076327, A076328.

Essentially the same table as A126736.

Cf. A084268 (not necessarily connected), A115597.

Keyword

nonn,tabl

Author

Eric W. Weisstein, May 24 2003

Extensions

a(37)-a(66) from Andrew Howroyd, Dec 02 2018

Status

approved

A113081 Square table T, read by antidiagonals, where T(n,k) gives the number of n-th generation descendents of a node labeled (k), in the tree of 3-tournament sequences, for n>=1.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 21, 10, 3, 1, 0, 331, 114, 21, 4, 1, 0, 11973, 2970, 331, 36, 5, 1, 0, 1030091, 182402, 11973, 724, 55, 6, 1, 0, 218626341, 27392682, 1030091, 33476, 1345, 78, 7, 1, 0, 118038692523, 10390564242, 218626341, 3697844, 75695, 2246

Offset

0,8

Comments

A 3-tournament sequence is an increasing sequence of positive integers (t_1,t_2,...) such that t_1 = p, t_i = p (mod 2) and t_{i+1} <= 3*t_i, where p>=1. This is the table of 3-tournament sequences when the starting node has label p = k for column k>=1.

Links

Table of n, a(n) for n=0..51.

M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.

Formula

For n>=k>0: T(n, k) = Sum_{j=1..k} T(n-1, k+2*j); else for k>n>0: T(n, k) = Sum_{j=1..n+1}(-1)^(j-1)*C(n+1, j)*T(n, k-j); with T(0, k)=1 for k>=0. Column k of T equals column 0 of the matrix k-th power of triangle A113084, which satisfies the matrix recurrence: A113084(n, k) = [A113084^3](n-1, k-1) + [A113084^3](n-1, k) for n>k>=0.

Example

Table begins:
1,1,1,1,1,1,1,1,1,1,1,1,1,...
0,1,2,3,4,5,6,7,8,9,10,11,...
0,3,10,21,36,55,78,105,136,171,210,...
0,21,114,331,724,1345,2246,3479,5096,7149,...
0,331,2970,11973,33476,75695,148926,265545,440008,...
0,11973,182402,1030091,3697844,10204145,23694838,...
0,1030091,27392682,218626341,1011973796,3416461455,...
0,218626341,10390564242,118038692523,706848765844,...
0,118038692523,10210795262650,166013096151621,...

Prog

(PARI) /* Generalized Cook-Kleber Recurrence */ T(n, k, q=3)=if(n==0, 1, if(n<0 || k<=0, 0, if(n==1, k, if(n>=k, sum(j=1, k, T(n-1, k+(q-1)*j)), sum(j=1, n+1, (-1)^(j-1)*binomial(n+1, j)*T(n, k-j))))))
(PARI) /* Matrix Power Recurrence (Paul D. Hanna) */ T(n, k, q=3)=local(M=matrix(n+1, n+1)); for(r=1, n+1, for(c=1, r, M[r, c]=if(r==c, 1, if(c>1, (M^q)[r-1, c-1])+(M^q)[r-1, c]))); return((M^k)[n+1, 1])

Crossrefs

Cf. A113084, A113085 (column 1), A113089 (column 2); tables: A093729 (2-tournaments), A113092 (4-tournaments), A113103 (5-tournaments).

Keyword

nonn,tabl

Author

Paul D. Hanna, Oct 14 2005

Status

approved

A253286 Square array read by upward antidiagonals, A(n,k) = Sum_{j=0..n} (n-j)!*C(n,n-j)* C(n-1,n-j)*k^j, for n>=0 and k>=0.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 13, 8, 3, 1, 0, 73, 44, 15, 4, 1, 0, 501, 304, 99, 24, 5, 1, 0, 4051, 2512, 801, 184, 35, 6, 1, 0, 37633, 24064, 7623, 1696, 305, 48, 7, 1, 0, 394353, 261536, 83079, 18144, 3145, 468, 63, 8, 1

Offset

0,8

Links

Seiichi Manyama, Antidiagonals n = 0..139, flattened

Index entries for sequences related to Laguerre polynomials

Formula

A(n,k) = k*n!*hypergeom([1-n],[2],-k)) for n>=1 and 1 for n=0.

Row sums of triangle, Sum_{k=0..n} A(n-k, k) = 1 + A256325(n).

From Seiichi Manyama, Feb 03 2021: (Start)

E.g.f. of column k: exp(k*x/(1-x)).

T(n,k) = (2*n+k-2) * T(n-1,k) - (n-1) * (n-2) * T(n-2, k) for n > 1. (End)

From G. C. Greubel, Feb 23 2021: (Start)

A(n, k) = k*(n-1)!*LaguerreL(n-1, 1, -k) with A(0, k) = 1.

T(n, k) = k*(n-k-1)!*LaguerreL(n-k-1, 1, -k) with T(n, n) = 1.

T(n, 2) = A052897(n) = A086915(n)/2.

Sum_{k=0..n} T(n, k) = 1 + Sum_{k=0..n-1} (n-k-1)*k!*LaguerreL(k, 1, k-n+1). (End)

Example

Square array starts, A(n,k):
      1,       1,       1,       1,      1,      1,      1, ...  A000012
      0,       1,       2,       3,      4,      5,      6, ...  A001477
      0,       3,       8,      15,     24,     35,     48, ...  A005563
      0,      13,      44,      99,    184,    305,    468, ...  A226514
      0,      73,     304,     801,   1696,   3145,   5328, ...
      0,     501,    2512,    7623,  18144,  37225,  68976, ...
      0,    4051,   24064,   83079, 220096, 495475, 997056, ...
A000007, A000262, A052897, A255806, ...
Triangle starts, T(n, k) = A(n-k, k):
  1;
  0,   1;
  0,   1,   1;
  0,   3,   2,  1;
  0,  13,   8,  3,  1;
  0,  73,  44, 15,  4, 1;
  0, 501, 304, 99, 24, 5, 1;

Maple

L := (n, k) -> (n-k)!*binomial(n, n-k)*binomial(n-1, n-k):
A := (n, k) -> add(L(n, j)*k^j, j=0..n):
# Alternatively:
# A := (n, k) -> `if`(n=0, 1, simplify(k*n!*hypergeom([1-n], [2], -k))):
for n from 0 to 6 do lprint(seq(A(n, k), k=0..6)) od;

Mathematica

A253286[n_, k_]:= If[k==n, 1, k*(n-k-1)!*LaguerreL[n-k-1, 1, -k]];
Table[A253286[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Feb 23 2021 *)

Prog

(PARI) {T(n, k) = if(n==0, 1, n!*sum(j=1, n, k^j*binomial(n-1, j-1)/j!))} \\ Seiichi Manyama, Feb 03 2021
(PARI) {T(n, k) = if(n<2, (k-1)*n+1, (2*n+k-2)*T(n-1, k)-(n-1)*(n-2)*T(n-2, k))} \\ Seiichi Manyama, Feb 03 2021
(Sage) flatten([[1 if k==n else k*factorial(n-k-1)*gen_laguerre(n-k-1, 1, -k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Feb 23 2021
(Magma) [k eq n select 1 else k*Factorial(n-k-1)*Evaluate(LaguerrePolynomial(n-k-1, 1), -k): k in [0..n], n in [0..12]]; // G. C. Greubel, Feb 23 2021

Crossrefs

Main diagonal gives A293145.

Cf. A000262, A001477, A005563, A052897, A226514, A255806, A256325.

Keyword

tabl,easy,nonn

Author

Peter Luschny, Mar 24 2015

Status

approved

A184182 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n). A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67. Its longest block has length 3.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 11, 10, 2, 1, 0, 53, 53, 11, 2, 1, 0, 309, 334, 63, 11, 2, 1, 0, 2119, 2428, 415, 64, 11, 2, 1, 0, 16687, 20009, 3121, 425, 64, 11, 2, 1, 0, 148329, 184440, 26402, 3205, 426, 64, 11, 2, 1, 0, 1468457, 1881050, 248429, 27145, 3215, 426, 64, 11, 2, 1

Offset

0,8

Comments

Sum of entries in row n is n!.

T(n,1) = A000255(n-1) for n>=1.

Links

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

Formula

T(n,k) = Sum_{m=1..n} (b(n,m,k)-b(n,m,k-1))*(d(m)+d(m-1)), where b(n,m,k) = coefficient of t^n in (t+t^2+...+t^k)^m and d(j) = A000166(j) are the derangement numbers.

Example

T(3,1) = 3 because we have 132, 213, and 321.
T(4,3) = 2 because we have 4123 and 2341.
Triangle starts:
  1;
  0,   1;
  0,   1,   1;
  0,   3,   2,  1;
  0,  11,  10,  2,  1;
  0,  53,  53, 11,  2, 1;
  0, 309, 334, 63, 11, 2, 1;
  ...

Maple

d[-1]:= 0: d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: b := proc (n, m, k) options operator, arrow: coeff(add(t^j, j = 1 .. k)^m, t, n) end proc: T := proc (n, k) options operator, arrow: add(b(n, m, k)*(d[m]+d[m-1]), m = 0 .. n)-add(b(n, m, k-1)*(d[m]+d[m-1]), m = 1 .. n) end proc: for n from 0 to 11 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

Crossrefs

Columns k=0..3 give A000007, A000255(n-1), A370390, A370392.

Cf. A000166, A184180.

Row sums are A000142.

Keyword

nonn,tabl

Author

Emeric Deutsch, Feb 13 2011

Extensions

Row n=0 and column k=0 added by Alois P. Heinz, Feb 17 2024

Status

approved

A370419 A(n, k) = 2^n*Pochhammer(k/2, n). Square array read by ascending antidiagonals.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 15, 8, 3, 1, 0, 105, 48, 15, 4, 1, 0, 945, 384, 105, 24, 5, 1, 0, 10395, 3840, 945, 192, 35, 6, 1, 0, 135135, 46080, 10395, 1920, 315, 48, 7, 1, 0, 2027025, 645120, 135135, 23040, 3465, 480, 63, 8, 1

Offset

0,8

Links

Paolo Xausa, Table of n, a(n) for n = 0..11324 (first 150 antidiagonals, flattened).

Formula

The polynomials P(n, x) = Sum_{k=0..n} Stirling1(n, k)*(-2)^(n-k)*x^k are ordinary generating functions for row n, i.e., A(n, k) = P(n, k).

From Werner Schulte, Mar 06 and 07 2024: (Start)

A(n, k) = Product_{i=1..n} (2*i - 2 + k).

E.g.f. of column k: Sum_{n>=0} A(n, k) * t^n / (n!) = (1/sqrt(1 - 2*t))^k.

A(n, k) = A(n+1, k-2) / (k - 2) for k > 2.

A(n, k) = Sum_{i=0..k-1} i! * A265649(n, i) * binomial(k-1, i) for k > 0.

E.g.f. of row n > 0: Sum_{k>=1} A(n, k) * x^k / (k!) = (Sum_{k=1..n} A035342(n, k) * x^k) * exp(x).

Sum_{n>=0, k>=0} A(n, k) * x^k * t^n / (k! * n!) = exp(x/sqrt(1 - 2*t)).

Sum_{n>=0, k>=0} A(n, k) * x^k * t^n / (n!) = 1 / (1 - x/sqrt(1 - 2*t)).

The LU decomposition of this array is given by the upper triangular matrix U which is the transpose of A007318 and the lower triangular matrix L, where L is defined L(n, k) = A035342(n, k) * k! for 1 <= k <= n and L(n, 0) = 0^n. Note that L(n, k) + L(n, k+1) = A265649(n, k) * k! for 0 <= k <= n. (End)

Example

The array starts:
[0] 1,   1,    1,     1,     1,     1,     1,      1,      1, ...
[1] 0,   1,    2,     3,     4,     5,     6,      7,      8, ...
[2] 0,   3,    8,    15,    24,    35,    48,     63,     80, ...
[3] 0,  15,   48,   105,   192,   315,   480,    693,    960, ...
[4] 0, 105,  384,   945,  1920,  3465,  5760,   9009,  13440, ...
[5] 0, 945, 3840, 10395, 23040, 45045, 80640, 135135, 215040, ...
.
Seen as the triangle T(n, k) = A(n - k, k):
[0] 1;
[1] 0,   1;
[2] 0,   1,   1;
[3] 0,   3,   2,   1;
[4] 0,  15,   8,   3,  1;
[5] 0, 105,  48,  15,  4, 1;
[6] 0, 945, 384, 105, 24, 5, 1;
.
From Werner Schulte, Mar 07 2024: (Start)
Illustrating the LU decomposition of A:
    / 1                \   / 1 1 1 1 1 ... \   / 1   1   1   1    1 ... \
    | 0   1            |   |   1 2 3 4 ... |   | 0   1   2   3    4 ... |
    | 0   3   2        | * |     1 3 6 ... | = | 0   3   8  15   24 ... |
    | 0  15  18   6    |   |       1 4 ... |   | 0  15  48 105  192 ... |
    | 0 105 174 108 24 |   |         1 ... |   | 0 105 384 945 1920 ... |
    | . . .            |   | . . .         |   | . . .                  |. (End)

Maple

A := (n, k) -> 2^n*pochhammer(k/2, n):
for n from 0 to 5 do seq(A(n, k), k = 0..9) od;
T := (n, k) -> A(n - k, k): seq(seq(T(n, k), k = 0..n), n = 0..9);
# Using the exponential generating functions of the columns:
EGFcol := proc(k, len) local egf, ser, n; egf := (1 - 2*x)^(-k/2);
ser := series(egf, x, len+2): seq(n!*coeff(ser, x, n), n = 0..len) end:
seq(lprint(EGFcol(n, 9)), n = 0..8);
# Using the generating polynomials for the rows:
P := (n, x) -> local k; add(Stirling1(n, k)*(-2)^(n - k)*x^k, k=0..n):
seq(lprint([n], seq(P(n, k), k = 0..8)), n = 0..5);
# Implementing the comment of Werner Schulte about the LU decomposition of A:
with(LinearAlgebra):
L := Matrix(7, 7, (n, k) -> A371025(n - 1,  k - 1)):
U := Matrix(7, 7, (n, k) -> binomial(n - 1, k - 1)):
MatrixMatrixMultiply(L, Transpose(U));  #  Peter Luschny, Mar 08 2024

Mathematica

A370419[n_, k_] := 2^n*Pochhammer[k/2, n];
Table[A370419[n-k, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Mar 06 2024 *)

Prog

(SageMath)
def A(n, k): return 2**n * rising_factorial(k/2, n)
for n in range(6): print([A(n, k) for k in range(9)])

Crossrefs

Columns: A000007, A001147, A000165, A001147 (shifted), A002866, A051577, A051578, A051579, A051580.

Rows: A000012, A001477, A005563, A370912, A190577.

Cf. A035342, A265649, A370890, A370982 (row sums of the triangle), A370915, A371025, A371077.

Keyword

nonn,tabl

Author

Peter Luschny, Mar 04 2024

Status

approved

A085771 Triangle read by rows. T(n, k) = A059438(n, k) for 1 <= k <= n, and T(n, 0) = n^0.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 13, 7, 3, 1, 0, 71, 32, 12, 4, 1, 0, 461, 177, 58, 18, 5, 1, 0, 3447, 1142, 327, 92, 25, 6, 1, 0, 29093, 8411, 2109, 531, 135, 33, 7, 1, 0, 273343, 69692, 15366, 3440, 800, 188, 42, 8, 1, 0, 2829325, 642581, 125316, 24892, 5226, 1146, 252, 52, 9, 1

Offset

0,8

Comments

The convolution triangle of A003319, the number of irreducible permutations. - Peter Luschny, Oct 09 2022

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 262 (#14).

Links

Table of n, a(n) for n=0..65.

FindStat - Combinatorial Statistic Finder, The decomposition number of a permutation.

Formula

Let f(x) = Sum_{n>=0} n!*x^n, g(x) = 1 - 1/f(x). Then g(x) is the g.f. of the second column, A003319.

Triangle T(n, k) read by rows, given by [0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] DELTA A000007, where DELTA is Deléham's operator defined in A084938.

G.f.: 1/(1 - xy/(1 - x/(1 - 2x/(1 - 2x/(1 - 3x/(1 - 3x/(1 - 4x/(1-.... (continued fraction). - Paul Barry, Jan 29 2009

Example

Triangle starts:
[0] [1]
[1] [0,      1]
[2] [0,      1,     1]
[3] [0,      3,     2,     1]
[4] [0,     13,     7,     3,    1]
[5] [0,     71,    32,    12,    4,   1]
[6] [0,    461,   177,    58,   18,   5,   1]
[7] [0,   3447,  1142,   327,   92,  25,   6,  1]
[8] [0,  29093,  8411,  2109,  531, 135,  33,  7, 1]
[9] [0, 273343, 69692, 15366, 3440, 800, 188, 42, 8, 1]

Maple

# Uses function PMatrix from A357368.
PMatrix(10, A003319); # Peter Luschny, Oct 09 2022

Prog

(SageMath) # Using function delehamdelta from A084938.
def A085771_triangle(n) :
    a = [0, 1] + [(i + 3) // 2 for i in range(1, n-1)]
    b = [0^i for i in range(n)]
    return delehamdelta(a, b)
A085771_triangle(9) # Peter Luschny, Sep 10 2022

Crossrefs

T(2*n, n) = A308650(n).

Variants: A059439, A263484 (row reversed).

Cf. A003319, A059440, A055998, A059438, A000007, A084938.

Keyword

easy,nonn,tabl

Author

Philippe Deléham, Jul 22 2003

Status

approved

A344499 T(n, k) = F(n - k, k), where F(n, x) is the Fubini polynomial. Triangle read by rows, T(n, k) for 0 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 13, 10, 3, 1, 0, 75, 74, 21, 4, 1, 0, 541, 730, 219, 36, 5, 1, 0, 4683, 9002, 3045, 484, 55, 6, 1, 0, 47293, 133210, 52923, 8676, 905, 78, 7, 1, 0, 545835, 2299754, 1103781, 194404, 19855, 1518, 105, 8, 1, 0, 7087261, 45375130, 26857659, 5227236, 544505, 39390, 2359, 136, 9, 1

Offset

0,8

Comments

The array rows are recursively generated by applying the Akiyama-Tanigawa algorithm to the powers (see the Python implementation below). In this way the array becomes the image of A004248 under the AT-transformation when applied to the columns of A004248. This makes the array closely linked to A371761, which is generated in the same way, but applied to the rows of A004248. - Peter Luschny, Apr 27 2024

Links

Table of n, a(n) for n=0..65.

Formula

T(n, k) = (n - k)! * [x^(n - k)] (1 / (1 + k * (1 - exp(x)))).

T(2*n, n) = A094420(n).

Example

Triangle starts:
[0] 1;
[1] 0, 1;
[2] 0, 1,      1;
[3] 0, 3,      2,       1;
[4] 0, 13,     10,      3,       1;
[5] 0, 75,     74,      21,      4,      1;
[6] 0, 541,    730,     219,     36,     5,     1;
[7] 0, 4683,   9002,    3045,    484,    55,    6,    1;
[8] 0, 47293,  133210,  52923,   8676,   905,   78,   7,   1;
[9] 0, 545835, 2299754, 1103781, 194404, 19855, 1518, 105, 8, 1;
.
Seen as an array A(n, k) = T(n + k, n):
[0] [1, 0,   0,    0,     0,       0,         0, ...  A000007
[1] [1, 1,   3,   13,    75,     541,      4683, ...  A000670
[2] [1, 2,  10,   74,   730,    9002,    133210, ...  A004123
[3] [1, 3,  21,  219,  3045,   52923,   1103781, ...  A032033
[4] [1, 4,  36,  484,  8676,  194404,   5227236, ...  A094417
[5] [1, 5,  55,  905, 19855,  544505,  17919055, ...  A094418
[6] [1, 6,  78, 1518, 39390, 1277646,  49729758, ...  A094419
[7] [1, 7, 105, 2359, 70665, 2646007, 118893705, ...  A238464

Maple

F := proc(n) option remember; if n = 0 then return 1 fi:
expand(add(binomial(n, k)*F(n - k)*x, k = 1..n)) end:
seq(seq(subs(x = k, F(n - k)), k = 0..n), n = 0..10);

Mathematica

F[n_] := F[n] = If[n == 0, 1,
   Expand[Sum[Binomial[n, k]*F[n - k]*x, {k, 1, n}]]];
Table[Table[F[n - k] /. x -> k, {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jun 06 2024, after Peter Luschny *)

Prog

(SageMath)  # Computes the triangle.
@cached_function
def F(n):
    R.<x> = PolynomialRing(ZZ)
    if n == 0: return R(1)
    return R(sum(binomial(n, k)*F(n - k)*x for k in (1..n)))
def Fval(n): return [F(n - k).substitute(x = k) for k in (0..n)]
for n in range(10): print(Fval(n))
(SageMath)  # Computes the square array using the Akiyama-Tanigawa algorithm.
def ATFubini(n, len):
    A = [0] * len
    R = [0] * len
    for k in range(len):
        R[k] = (n + 1)**k  # Chancing this to R[k] = k**n generates A371761.
        for j in range(k, 0, -1):
            R[j - 1] = j * (R[j] - R[j - 1])
        A[k] = R[0]
    return A
for n in range(8): print([n], ATFubini(n, 7))  # Peter Luschny, Apr 27 2024

Crossrefs

Variant of the array is A094416 (which has column 0 and row 0 missing).

The coefficients of the Fubini polynomials are A131689.

Cf. A094420 (main diagonal of array), A372346 (row sums), A004248, A371761.

Keyword

nonn,tabl

Author

Peter Luschny, May 21 2021

Status

approved

A111106 Riordan array (1, x*g(x)) where g(x) is g.f. of double factorials A001147.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 15, 7, 3, 1, 0, 105, 36, 12, 4, 1, 0, 945, 249, 64, 18, 5, 1, 0, 10395, 2190, 441, 100, 25, 6, 1, 0, 135135, 23535, 3807, 691, 145, 33, 7, 1, 0, 2027025, 299880, 40032, 5880, 1010, 200, 42, 8, 1

Offset

0,8

Comments

Triangle T(n,k), 0 <= k <= n, given by [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Links

Table of n, a(n) for n=0..54.

Formula

T(n, k) = Sum_{j=0..n-k} T(n-1, k-1+j)*A111088(j).

Sum_{k=0..n} T(n, k) = A112934(n).

G.f.: 1/(1-xy/(1-x/(1-2x/(1-3x/(1-4x/(1-... (continued fraction). - Paul Barry, Jan 29 2009

Sum_{k=0..n} T(n,k)*2^(n-k) = A168441(n). - Philippe Deléham, Nov 28 2009

Example

Rows begin:
  1;
  0,       1;
  0,       1,      1;
  0,       3,      2,     1;
  0,      15,      7,     3,    1;
  0,     105,     36,    12,    4,    1;
  0,     945,    249,    64,   18,    5,   1;
  0,   10395,   2190,   441,  100,   25,   6,  1:
  0,  135135,  23535,  3807,  691,  145,  33,  7, 1;
  0, 2027025, 299880, 40032, 5880, 1010, 200, 42, 8, 1;

Maple

# Uses function PMatrix from A357368.
PMatrix(10, n -> doublefactorial(2*n-3)); # Peter Luschny, Oct 19 2022

Crossrefs

Columns: A000007, A001147, A034430; diagonals: A000012, A001477, A055998.

Cf. A084938, A111088, A112934, A168441.

Keyword

easy,nonn,tabl

Author

Philippe Deléham, Oct 13 2005, Dec 20 2008

Status

approved

A232006 Triangular array read by rows: T(n,k) is the number of simple labeled graphs on vertex set {1,2,...,n} with exactly k components (all of which are trees) such that the labels {1,2,...,k} are all in distinct components (trees), n >= 0, 0 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 16, 8, 3, 1, 0, 125, 50, 15, 4, 1, 0, 1296, 432, 108, 24, 5, 1, 0, 16807, 4802, 1029, 196, 35, 6, 1, 0, 262144, 65536, 12288, 2048, 320, 48, 7, 1, 0, 4782969, 1062882, 177147, 26244, 3645, 486, 63, 8, 1, 0, 100000000, 20000000, 3000000, 400000, 50000, 6000, 700, 80, 9, 1

Offset

0,8

Comments

Row sums = (n^n-n)/(n-1)^2 = A058128(n).

Column k without leading zeros is the k-th exponential (also called binomial) convolution of the sequence {A000272(n+1)} = {A232006(n+1, 1)}, for n >= 0, with e.g.f. LamberW(-x)/(-x), where LambertW is the principal branch of the Lambert W-function. This is also the row polynomial P(n, x) of the unsigned triangle A137452, evaluated at x = k. - Wolfdieter Lang, Apr 24 2023

References

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Proposition 5.3.2.

Links

G. C. Greubel, Rows n=0..75 of triangle, flattened

Chad Casarotto, Graph Theory and Cayley's Formula, 2006

Alan D. Sokal, A remark on the enumeration of rooted labeled trees, arXiv:1910.14519 [math.CO], 2019.

Marc van Leeuwen, I am stuck with a combinatoric problem... Math Stackexchange, Answer May 14 2017.

Eric Weisstein's World of Mathematics, Lambert W-function

Wikipedia, Lambert W function

Formula

T(n, k) = k*n^(n-k-1).

T(n, k) = Sum_{i=0..n-k} T(n-1, k-1+i)*C(n-k,i), T(0, 0) = 1, T(n, 0) = 0 when n >= 1.

From Wolfdieter Lang, Apr 24 2023: (Start)

E.g.f. for {T(n+k, k)}_{n>=0} is (LambertW(-x)/(-x))^k, for k >= 0.

T(n, k) = Sum_{m=0..n-k} |A137452(n-k, m)|*k^m, for n >= 0 and k = 0..n. That is, T(n, n) = 1, for n >= 0, and T(n, k) = Sum_{m=1..n-k} binomial(n-k-1, m-1)*(n-k)^(n-k-m)*k^m, for k = 0..n-1 and n >= k+1. (End)

Example

The triangle begins:
n\k  0         1        2       3      4     5    6   7  8 9 10 ...
0:   1
1:   0         1
2:   0         1        1
3:   0         3        2       1
4:   0        16        8       3      1
5:   0       125       50      15      4     1
6:   0      1296      432     108     24     5    1
7:   0     16807     4802    1029    196    35    6   1
8:   0    262144    65536   12288   2048   320   48   7  1
9:   0   4782969  1062882  177147  26244  3645  486  63  8 1
10:  0 100000000 20000000 3000000 400000 50000 6000 700 80 9  1
... Reformatted by Wolfdieter Lang, Apr 24 2023

Mathematica

Prepend[Table[Table[k n^(n-k-1), {k, 0, n}], {n, 1, 8}], {1}]//Grid

Prog

(PARI) {T(n, k) = if( k<0 || k>n, 0, n^(n-k-1))}; /* Michael Somos, May 15 2017 */

Crossrefs

Cf. A058128, |A137452|.

Columns give A000007, A000272, A007334, A362354, A362355, A362356, ...

Keyword

nonn,tabl,easy

Author

Geoffrey Critzer, Nov 16 2013

Status

approved