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.

%I A007799 #44 Feb 16 2025 08:32:31
%S A007799 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,
%T A007799 6,30,135,460,1110,1689,1254,340,15,1,7,42,231,1015,3430,8379,13083,
%U A007799 10408,3409,315,1,8,56,364,1960,8540,28994,71512,114064,96116,36260
%N A007799 Irregular triangle read by rows: Whitney numbers of the second kind a(n,k), n >= 1, k >= 0, for the star poset.
%C A007799 Row sums are factorials. - _N. J. A. Sloane_, Mar 05 2017
%C A007799 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
%H A007799 Vincenzo Librandi, <a href="/A007799/b007799.txt">Table of n, a(n) for n = 1..1875</a>
%H A007799 S. Grusea and A. Labarre, <a href="https://arxiv.org/abs/1604.04766">Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution</a>, arXiv:1604.04766 [math.CO], 2016.
%H A007799 S. Grusea and A. Labarre, <a href="https://doi.org/10.1016/j.aam.2016.04.002">Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution</a>, Advances in Applied Mathematics, Elsevier, 2016, 78, pp. 94-113; see also <a href="https://hal.archives-ouvertes.fr/hal-01242140">hal-01242140</a>.
%H A007799 Navid Imani, Hamid Sarbazi-Azad, and Selim G. Akl, <a href="https://doi.org/10.1016/j.disc.2008.08.007">Some topological properties of star graphs: The surface area and volume</a>,  Discrete Mathematics 309.3 (2009): 560-569. See Table 1.
%H A007799 F. J. Portier and T. P. Vaughan, <a href="https://doi.org/10.1016/S0195-6698(13)80127-8">Whitney numbers of the second kind for the star poset</a>, Europ. J. Combin., 11 (1990), 277-288.
%H A007799 K. Qiu and S. G. Akl, <a href="http://dx.doi.org/10.1155/1995/61390">On some properties of the star graph</a>, VLSI Design, Vol. 2, No. 4 (1995), 389-396.
%H A007799 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PermutationStarGraph.html">Permutation Star Graph</a>
%F A007799 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.
%F A007799 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
%e A007799 Triangle begins:
%e A007799   1;
%e A007799   1,    1;
%e A007799   1,    2,    2,    1;
%e A007799   1,    3,    6,    9,    5;
%e A007799   1,    4,   12,   30,   44,   26,    3;
%e A007799   1,    5,   20,   70,  170,  250,  169,   35;
%e A007799   1,    6,   30,  135,  460, 1110, 1689, 1254,  340,   15;
%e A007799   ...
%t A007799 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 *)
%t A007799 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 *)
%Y A007799 Cf. A192837.
%K A007799 nonn,tabf,easy,nice
%O A007799 1,5
%A A007799 Frederick J. Portier [fportier(AT)msmary.edu]
%E A007799 More terms from Larry Reeves (larryr(AT)acm.org), Mar 22 2000