A038719 Triangle T(n,k) (0 <= k <= n) giving number of chains of length k in partially ordered set formed from subsets of n-set by inclusion.
1, 2, 1, 4, 5, 2, 8, 19, 18, 6, 16, 65, 110, 84, 24, 32, 211, 570, 750, 480, 120, 64, 665, 2702, 5460, 5880, 3240, 720, 128, 2059, 12138, 35406, 57120, 52080, 25200, 5040, 256, 6305, 52670, 213444, 484344, 650160, 514080, 221760, 40320, 512, 19171
Offset: 0
Examples
Triangle begins
1;
2, 1;
4, 5, 2;
8, 19, 18, 6;
16, 65, 110, 84, 24;
...
From _Peter Bala_, Feb 02 2022: (Start)
Table of successive differences of k^2 starting at k = 2
4 9 16
5 7
2
gives [4, 5, 2] as row 2 of this triangle.
Table of successive differences of k^3 starting at k = 2
8 27 64 125
19 37 61
18 24
6
gives [8, 19, 8, 6] as row 3 of this triangle. (End)
Links
- Alois P. Heinz, Rows n = 0..140, flattened
- Peter Bala, Deformations of the Hadamard product of power series
- L. Bartlomiejczyk and J. Drewniak, A characterization of sets and operations invariant under bijections, Aequationes Mathematicae 68 (2004), pp. 1-9.
- M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
- Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.
- R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 23-31.
- Index entries for sequences related to posets
Crossrefs
Programs
-
Haskell
a038719 n k = a038719_tabl !! n !! k a038719_row n = a038719_tabl !! n a038719_tabl = iterate f [1] where f row = zipWith (+) (zipWith (*) [0..] $ [0] ++ row) (zipWith (*) [2..] $ row ++ [0]) -- Reinhard Zumkeller, Jul 08 2012 -
Maple
T:= proc(n, k) option remember; `if` (n=0, `if`(k=0, 1, 0), k*T(n-1, k-1) +(k+2)*T(n-1, k)) end: seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Aug 02 2011 -
Mathematica
t[n_, k_] := Sum[ (-1)^(k-i)*Binomial[k, i]*(2+i)^n, {i, 0, k}]; Flatten[ Table[ t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, after Pari *) -
PARI
T(n,k)=sum(i=0,k,(-1)^(k-i)*binomial(k,i)*(2+i)^n)
Formula
T(n, k) = Sum_{j=0..k} (-1)^j*C(k, j)*(k+2-j)^n.
T(n+1, k) = k*T(n, k-1) + (k+2)*T(n, k), T(0,0) = 1, T(0,k) = 0 for k>0.
E.g.f.: exp(2*x)/(1+y*(1-exp(x))). - Vladeta Jovovic, Jul 21 2003
A038719 as a lower triangular matrix is the binomial transform of A028246. - Gary W. Adamson, May 15 2005
Binomial transform of n-th row = 2^n + 3^n + 4^n + ...; e.g., binomial transform of [8, 19, 18, 6] = 2^3 + 3^3 + 4^3 + 5^3 + ... = 8, 27, 64, 125, ... - Gary W. Adamson, May 15 2005
From Peter Bala, Jul 09 2014: (Start)
T(n,k) = k!*( Stirling2(n+2,k+2) - Stirling2(n+1,k+2) ).
T(n,k) = k!*A143494(n+2,k+2).
n-th row polynomial = 1/(1 + x)*( sum {k >= 0} (k + 2)^n*(x/(1 + x))^k ). Cf. A028246. (End)
The row polynomials have the form (2 + x) o (2 + x) o ... o (2 + x), where o denotes the black diamond multiplication operator of Dukes and White. See example E12 in the Bala link. - Peter Bala, Jan 18 2018
Z(P,m) = Sum_{k=0..n} T(n,k)Binomial(m-2,k) = m^n, the zeta polynomial of the poset B_n. Each length m multichain from 0 to 1 in B_n corresponds to a function from [n] into [m]. - Geoffrey Critzer, Dec 25 2020
The entries in row n are the first terms in a table of the successive differences of the sequence [2^n, 3^n, 4^n, ...]. Examples are given below. - Peter Bala, Feb 02 2022
Extensions
More terms from Larry Reeves (larryr(AT)acm.org), May 09 2000
Comments