A007799 Irregular triangle read by rows: Whitney numbers of the second kind a(n,k), n >= 1, k >= 0, for the star poset.

1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 9, 5, 1, 4, 12, 30, 44, 26, 3, 1, 5, 20, 70, 170, 250, 169, 35, 1, 6, 30, 135, 460, 1110, 1689, 1254, 340, 15, 1, 7, 42, 231, 1015, 3430, 8379, 13083, 10408, 3409, 315, 1, 8, 56, 364, 1960, 8540, 28994, 71512, 114064, 96116, 36260

Offset

1,5

Comments

Row sums are factorials. - N. J. A. Sloane, Mar 05 2017

a(n,k) is the number of permutations of 1..n that can be reached from the identity permutation in k steps using only the n-1 transpositions (1 2) (1 3) .. (1 n). The maximum value of k is given by floor(3*(n-1)/2). - Andrew Howroyd, May 13 2017

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1875

S. Grusea and A. Labarre, Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution, arXiv:1604.04766 [math.CO], 2016.

S. Grusea and A. Labarre, Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution, Advances in Applied Mathematics, Elsevier, 2016, 78, pp. 94-113; see also hal-01242140.

Navid Imani, Hamid Sarbazi-Azad, and Selim G. Akl, Some topological properties of star graphs: The surface area and volume, Discrete Mathematics 309.3 (2009): 560-569. See Table 1.

F. J. Portier and T. P. Vaughan, Whitney numbers of the second kind for the star poset, Europ. J. Combin., 11 (1990), 277-288.

K. Qiu and S. G. Akl, On some properties of the star graph, VLSI Design, Vol. 2, No. 4 (1995), 389-396.

Eric Weisstein's World of Mathematics, Permutation Star Graph

Formula

a(n,0) = 1, a(n,1) = n-1, a(n,2) = (n-1)(n-2), a(n,k) = a(n-1, k) + (n-1)a(n-1, k-1) - (n-2)a(n-2, k-1) + (n-2)a(n-2, k-3) for k >= 3.

a(n,0) = 1, a(n,1) = n - 1, a(n,2) = (n-1)(n-2); a(n,i) = (n-1)a(n-1, i-1) + Sum_{j=1 .. n-2} j a(j, i-3). For 0 <= i <= ceiling(3(n-1)/2) and n >= 1 we have Sum_{k=0 .. i+1} (-1)^k binomial(i+1, k) a(n+i+1-k, i) = 0. For example, for i=2, we have a(n+3, 2) - 3a(n+2, 2) + 3a(n+1, 2) - a(n, 2) = 0. - Ke Qiu (kqiu(AT)brocku.ca), Feb 06 2005

Example

Triangle begins:
  1;
  1,    1;
  1,    2,    2,    1;
  1,    3,    6,    9,    5;
  1,    4,   12,   30,   44,   26,    3;
  1,    5,   20,   70,  170,  250,  169,   35;
  1,    6,   30,  135,  460, 1110, 1689, 1254,  340,   15;
  ...

Mathematica

nmax = 9; a[n_, 0] = 1; a[n_, 1] = n - 1; a[n_, 2] = (n - 1) (n - 2); a[n_, k_ /; k >= 2] := a[n, k] = (n - 1) a[n - 1, k - 1] + Sum[j a[j, k-3], {j, 1, n - 2}]; Flatten[Table[a[n, k], {n, 1, nmax}, {k, 0, Floor[3 (n - 1)/2]}]] (* Jean-François Alcover, Nov 10 2011, after Ke Qiu *)
Table[Sum[Binomial[n - 1, k] Binomial[n - 1 - k, t] StirlingS1[k + 1, i - k + 1 - 2 t] (-1)^(i + 2 - t), {k, 0, Min[n - 1, i + 1]}, {t, Max[0, Ceiling[(i - 2 k)/2]], Min[n - 1 - k, Floor[(i + 1 - k)/2]]}], {n, 9}, {i, 0, Floor[3 (n - 1)/2]}] // Flatten (* Eric W. Weisstein, Dec 09 2017 *)

Crossrefs

Cf. A192837.

Sequence in context: A360571 A088459 A300699 * A122888 A371830 A266378

Adjacent sequences: A007796 A007797 A007798 * A007800 A007801 A007802

Keyword

nonn,tabf,easy,nice

Author

Frederick J. Portier [fportier(AT)msmary.edu]

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Mar 22 2000

Status

approved