A192837 -id:A192837 - cp's OEIS frontend

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

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

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

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

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

Cf. A192837.

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

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

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

A284039 Wiener index of the n-permutation star graph.

Original entry on oeis.org

0, 1, 27, 744, 26520, 1239840, 74662560, 5663831040, 530098007040, 60105991680000, 8127440487936000, 1292894601191424000, 239129895342514176000, 50899158690744139776000, 12356174324714508288000000, 3393918280427832764006400000, 1047355019625604129593753600000

Offset: 1

Eric W. Weisstein, Sep 13 2017

nonn

The permutation star graph of order n is a vertex transitive graph with n! vertices and degree n-1. The graph can be constructed as the Cayley graph of the permutations of 1..n with the n-1 generators (1 2), (1 3)..(1 n) where (1 k) is the transposition of 1 and k. The number of nodes at distance k from a specified node is given by A007799(n,k). - Andrew Howroyd, Sep 17 2017

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Permutation Star Graph
Eric Weisstein's World of Mathematics, Wiener Index

Cf. A007799, A192837.

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}];
Table[n!/2 Sum[k a[n, k], {k, Floor[3 (n - 1)/2]}], {n, 10}]

a(n) = n!/2 * Sum_{k=1..floor(3*(n-1)/2)} k*A007799(n, k). - Andrew Howroyd, Sep 17 2017

Terms a(8) and beyond from Andrew Howroyd, Sep 17 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions