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

Author

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

Keywords

• nonn
• tabf
• easy
• nice

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

Examples

			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;
  ...
		

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

Crossrefs

Cf. A192837.

Programs

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 *)

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

Extensions

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