A105794 -id:A105794 - cp's OEIS frontend

A227343 Matrix inverse of triangle A227342.

1, 1, 1, 3, 3, 1, 13, 13, 6, 1, 75, 75, 37, 10, 1, 541, 541, 270, 85, 15, 1, 4683, 4683, 2341, 770, 170, 21, 1, 47293, 47293, 23646, 7861, 1890, 308, 28, 1, 545835, 545835, 272917, 90930, 22491, 4158, 518, 36, 1, 7087261, 7087261, 3543630, 1181125, 294525, 57351, 8400, 822, 45, 1

Offset: 0

Peter Bala, Jul 11 2013

The e.g.f. has the form A(t)*exp(x*B(t)), where A(t) = 1/(2 - exp(t)) and B(t) = exp(t) - 1. Thus the row polynomials of this triangle form a Sheffer sequence for the pair (1 - t, log(1 + t)) (see Roman, p.17).

Let x_(k) := x*(x-1)*...*(x-k+1) denote the k-th falling factorial polynomial. Define a sequence x_[n] of basis polynomials for the polynomial algebra C[x] by setting x_[0] = 1, and setting x_[n] = x_(n-1)*(x - 2*n + 1) for n >= 1. The sequence begins [1, x-1, x*(x-3), x*(x-1)*(x-5), x*(x-1)*(x-2)*(x-7), ...]. Then this is the triangle of connection constants for expressing the monomial polynomials x^n as a linear combination of the basis x_[k], that is, x^n = sum {k = 0..n} T(n,k)*x_[k]. An example is given below.

			Triangle begins
n\k|   0    1    2    3    4    5
= = = = = = = = = = = = = = = = =
0 |   1
1 |   1    1
2 |   3    3    1
3 |  13   13    6    1
4 |  75   75   37   10    1
5 | 541  541  270   85   15    1
...
Connection constants. Row 4 = [75,75,37,10,1]: Thus
75 + 75*(x - 1) + 37*x*(x - 3) + 10*x*(x - 1)*(x - 5)+ x*(x - 1)*(x - 2)*(x - 7) = x^4.

S. Roman, The umbral calculus, Pure and Applied Mathematics 111, Academic Press Inc., New York, 1984. Reprinted by Dover in 2005.

Eric Weisstein's World of Mathematics, Sheffer Sequence

A000670 (columns 1 and 2), A048993, A059099 (row sums), A105794, A227342 (matrix inverse).

T[n_, k_] := n!/k! SeriesCoefficient[Series[1/(2 - Exp[t]) (Exp[t] - 1)^k, {t, 0, n}], n]
Flatten[Table[T[n, k], {n, 0, 12}, {k, 0, n}]]
U[n_, k_] := n!/k! SeriesCoefficient[Series[1/(1 - t^2) (t/Log[1 + t])^(n + 1), {t, 0, n - k}], n - k]
Flatten[Table[U[n, k], {n, 0, 8}, {k, 0, n}]] (* Emanuele Munarini, Dec 21 2016 *)

E.g.f.: 1/(2 - exp(t))*exp(x*(exp(t) - 1)) = 1 + (1 + x)*t + (3 + 3*x + x^2)*t^2/2! + (13 + 13*x + 6*x^2 + x^3)*t^3/3! + ....
Recurrence equation: T(n,0) = A000670(n), and for k >= 1, T(n,k) = 1/k*sum {i = 1..n} binomial(n,i)*T(n-i,k-1).
The row polynomials R(n,x) satisfy the Sheffer identity R(n,x + y) = sum {k = 0..n} binomial(n,k)*Bell(k,y)*R(n-k,x), where Bell(k,y) is the Bell or exponential polynomial (row polynomials of A048993).
The row polynomials also satisfy d/dx(R(n,x)) = sum {k = 0..n-1} binomial(n,k)*R(k,x).
Row sums A059099. Column 1 and column 2 = A000670. 1 + 2*column 3 = A000670 (apart from the first two terms).
From Emanuele Munarini, Dec 21 2016: (Start)
T(n,k) = (n!/k!)*[t^n](exp(t)-1)^k/(2-exp(t)).
T(n,k) = (n!/k!)*[t^(n-k)](t/log(1+t))^(n+1)/(1-t^2). (End)

A247493 Triangle read by rows: T(n, k) = C(n, k)C(2k, k)/(k+1) - sum(j = 0..k, (-1)^j(1-j)^nC(k, j)/k!), 0<=k<=n.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 0, 2, 6, 4, 0, 3, 11, 22, 13, 0, 4, 20, 45, 75, 41, 0, 5, 29, 110, 190, 261, 131, 0, 6, 42, 154, 560, 826, 938, 428, 0, 7, 55, 322, 749, 2646, 3570, 3452, 1429, 0, 8, 72, 335, 2499, 3885, 12012, 15198, 12897, 4861, 0, 9, 89, 770, 650, 16947, 21693, 53880, 63915, 48655, 16795, 0, 10, 110, 484, 11660, -8338, 97482

Offset: 0

Peter Luschny, Oct 02 2014

First negative value appears at T(11,5). - Indranil Ghosh, Mar 04 2017

			0;
0, 0;
0, 1, 1;
0, 2, 6, 4;
0, 3, 11, 22, 13;
0, 4, 20, 45, 75, 41;
0, 5, 29, 110, 190, 261, 131;
0, 6, 42, 154, 560, 826, 938, 428;

Indranil Ghosh, Rows 0..100, flattened

Cf. A001453, A098474, A105794, A247491.

T := proc(n, k) binomial(n,k)*binomial(2*k,k)/(k+1) - add((-1)^j*(1-j)^n /(j!*(k-j)!), j = 0..k) end:
for n from 0 to 12 do seq(T(n,k), k=0..n) od;

Flatten[Table[(Binomial[n,k] * Binomial[2k,k] / (k+1)) - Sum[(-1)^j*(1-j)^n*Binomial[k,j]/k!,{j,0,k}],{n,0,10},{k,0,n}]] (* Indranil Ghosh, Mar 04 2017 *)

tabl(nn) = {for (n=0, nn, for (k=0, n, print1((binomial(n,k)*binomial(2*k,k)/(k+1))-sum(j=0, k, (-1)^j*(1-j)^n*binomial(k,j)/k!),", ",);); print(););};
tabl(10); \\ Indranil Ghosh, Mar 04 2017

A105794(n, k) = (-1)^(n-k)*(C(n, k)*Catalan(k) - T(n, k)).
A247491(n) = Sum(k=0..n, (-1)^(n-k+1)*T(n, k)).
A001453(n) = T(n, n).
T(n,k) = A098474 (n,k) - A105794 (n,k). - Michel Marcus, Mar 04 2017

A132795 Triangle of Gely numbers, read by rows.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 5, 0, 1, 0, 16, 6, 1, 1, 0, 42, 56, 21, 0, 1, 0, 99, 316, 267, 36, 1, 1, 0, 219, 1408, 2367, 960, 85, 0, 1, 0, 466, 5482, 16578, 14212, 3418, 162, 1, 1, 0, 968, 19624, 99330, 153824, 77440, 11352, 341, 0, 1, 0, 1981, 66496, 534898, 1364848, 1233970, 389104, 36829, 672, 1

Offset: 0

Olivier Gérard, Aug 31 2007

First row is for n=0. First column is for k=0.
Sum of rows is n! = permutations of n symbols (A000142)
These numbers are related to the Eulerian numbers A(n,k).
Third Column (k=2) is A002662(n+1).
Second Diagonal (k=n-1) is A132796.
Binomial transform of this triangle gives set partitions without singletons (in a form very close to array A105794).

			Triangle starts:
1;
1, 0;
1, 0, 1;
1, 0, 5, 0;
1, 0, 16, 6, 1;
1, 0, 42, 56, 21, 0;
...

Charles O. Gely, Un tableau de conversion des polynomes cyclotomiques cousin des nombres Euleriens, Preprint Univ. Paris 7, 1999.
Olivier Gérard, Quelques facons originales de compter les permutations, submitted to Knuth07.
Olivier Gérard and Karol Penson, Set partitions, Multiset permutations and bi-permutations, in preparation.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1990, p. 269.

Cf. A000296, A132796.

T(n,k)= sum(j=0, k, (-1)^j*binomial(n+1, j)*sum(m=0, n, (k-j)^m)); \\ Michel Marcus, Jun 04 2014

T(n,k) = sum(j=0..k, (-1)^j*C(n+1,j)*sum(m=0..n, (k-j)^m) ).

A227341 Triangular array: Number of partitions of the vertex set of a forest of two trees on n vertices into k nonempty independent sets.

Original entry on oeis.org

1, 1, 1, 0, 2, 1, 0, 2, 4, 1, 0, 2, 10, 7, 1, 0, 2, 22, 31, 11, 1, 0, 2, 46, 115, 75, 16, 1, 0, 2, 94, 391, 415, 155, 22, 1, 0, 2, 190, 1267, 2051, 1190, 287, 29, 1, 0, 2, 382, 3991, 9471, 8001, 2912, 490, 37, 1, 0, 2, 766, 12355, 41875, 49476, 25473, 6342, 786, 46, 1

Offset: 1

Peter Bala, Jul 10 2013

For a graph G and a positive integer k, the graphical Stirling number S(G;k) is the number of set partitions of the vertex set of G into k nonempty independent sets (an independent set in G is a subset of the vertices, no two elements of which are adjacent).

Here we take the graph G to be a forest of two trees on n vertices. The corresponding graphical Stirling numbers S(G;k) do not depend on the choice of the trees. See Galvin and Thanh. If the graph G is a single tree on n vertices then the graphical Stirling numbers S(G;k) are the classical Stirling numbers of the second kind A008277. See also A105794.

			Triangle begins
n\k | 1 2  3   4   5  6  7
= = = = = = = = = = = = =
  1 | 1
  2 | 1 1
  3 | 0 2  1
  4 | 0 2  4   1
  5 | 0 2 10   7   1
  6 | 0 2 22  31  11  1
  7 | 0 2 46 115  75 16  1
Connection constants: Row 5: 2*x*(x-1) + 10*x*(x-1)*(x-2) + 7*x*(x-1)*(x-2)*(x-3) + x*(x-1)*(x-2)*(x-3)*(x-4) = x^2*(x-1)^3.

B. Duncan and R. Peele, Bell and Stirling Numbers for Graphs, Journal of Integer Sequences 12 (2009), article 09.7.1.
D. Galvin and D. T. Thanh, Stirling numbers of forests and cycles, Electr. J. Comb. Vol. 20(1): P73 (2013)

A008277, A011968 (row sums), A033484 (col. 3), A091344 (col. 4), A105794.

T(n,k) = Stirling2(n-1,k-1) + Stirling2(n-2,k-1), n,k >= 1.
Recurrence equation: T(n,k) = (k-1)*T(n-1,k) + T(n-1,k-1). Cf. A105794.
k-th column o.g.f.: x^k*(1+x)/((1-x)*(1-2*x)*...*(1-(k-1)*x)).
For n >= 2, sum {k = 0..n} T(n,k)*x_(k) = x^2*(x-1)^(n-2), where x_(k) = x*(x-1)*...*(x-k+1) is the falling factorial.
Column 3: A033484; Column 4: A091344; Row sums are essentially A011968.

cp's OEIS Frontend

A227343 Matrix inverse of triangle A227342.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A247493 Triangle read by rows: T(n, k) = C(n, k)*C(2*k, k)/(k+1) - sum(j = 0..k, (-1)^j*(1-j)^n*C(k, j)/k!), 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A132795 Triangle of Gely numbers, read by rows.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI

Formula

A227341 Triangular array: Number of partitions of the vertex set of a forest of two trees on n vertices into k nonempty independent sets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A247493 Triangle read by rows: T(n, k) = C(n, k)C(2k, k)/(k+1) - sum(j = 0..k, (-1)^j(1-j)^nC(k, j)/k!), 0<=k<=n.