login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007799 Irregular triangle read by rows: Whitney numbers of the second kind a(n,k), n >= 1, k >= 0, for the star poset. 6
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 (list; graph; refs; listen; history; text; internal format)
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

REFERENCES

S. Grusea, A. Labarre, Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution, Advances in Applied Mathematics, Elsevier, 2016, 78, pp. 94-113; https://hal.archives-ouvertes.fr/hal-01242140

LINKS

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

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

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: A055870 A088459 A300699 * A122888 A266378 A092113

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 19:15 EST 2018. Contains 317276 sequences. (Running on oeis4.)