|
%I #51 Aug 11 2021 08:49:10
%S 1,1,1,3,2,1,11,9,3,1,53,44,18,4,1,309,265,110,30,5,1,2119,1854,795,
%T 220,45,6,1,16687,14833,6489,1855,385,63,7,1,148329,133496,59332,
%U 17304,3710,616,84,8,1,1468457,1334961,600732,177996,38934,6678,924,108,9,1
%N Triangle read by rows: T(n,k) is the number of permutations of [n] having k small descents (n >= 1; 0 <= k <= n-1). A small descent in a permutation (x_1,x_2,...,x_n) is a position i such that x_i - x_(i+1) = 1.
%C This triangle is essentially A010027 (ascending pairs in permutations of [n]) with a different offset. The same triangle gives the number of permutations of [n] having k unit ascents (n >= 1; 0 <= k <= n-1). For permutations sorted by number of non-unitary (i.e., > 1) descents (also called "big" descents), see A120434. For permutations sorted by number of unitary moves (i.e., ascent or descent), see A001100. - _Olivier Gérard_, Oct 09 2007
%C With offsets n=0 (k=0) this is a binomial convolution triangle, a Sheffer triangle of the Appell type: ((exp(-x))/(1-x)^2),x). See the e.g.f. given below.
%D Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 for S_{n,k} (without row n=1 and column k=0).
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263 (Table 7.5.1).
%H Alois P. Heinz, <a href="/A123513/b123513.txt">Rows n = 1..150, flattened</a>
%H Bhadrachalam Chitturi and Krishnaveni K S, <a href="https://arxiv.org/abs/1601.04469">Adjacencies in Permutations</a>, arXiv preprint arXiv:1601.04469 [cs.DM], 2016. See Table 0.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000214/">The number of adjacencies of a permutation</a>
%H Sergey Kitaev, Philip B. Zhang, <a href="https://arxiv.org/abs/1811.07679">Distributions of mesh patterns of short lengths</a>, arXiv:1811.07679 [math.CO], 2018.
%H J. Liese, J. Remmel, <a href="http://puma.dimai.unifi.it/21_2/10_Liese_Remmel.pdf">Q-analogues of the number of permutations with k-excedances</a>, PU. M. A. Vol. 21 (2010), No. 2, pp. 285-320 (see E_{n,1}(x) in Table 1 p. 291).
%H F. Poussin, <a href="http://www.numdam.org/item?id=ITA_1979__13_3_251_0">Énumération des permutations par nombre de marches</a>, RAIRO, Informatique théorique, 13 no. 3, 1979, p. 251-255.
%F T(n,1) = A000255(n-1).
%F T(n,2) = A000166(n-1) (the derangement numbers).
%F T(n,3) = A000274(n).
%F T(n,4) = A000313(n).
%F T(n,5) = A001260(n);
%F G.f.: exp(-x+tx)/(1-x)^2 (if offset is 0), i.e., T(n,k)=(n-1)!*[x^(n-1) t^k]exp(-x+tx)/(1-x)^2.
%F T(n,k) = binomial(n-1,k)*A000255(n-1), n-1 >= k >= 0, else 0.
%e Triangle starts:
%e 1;
%e 1, 1;
%e 3, 2, 1;
%e 11, 9, 3, 1;
%e 53, 44, 18, 4, 1;
%e 309, 265, 110, 30, 5, 1;
%e 2119, 1854, 795, 220, 45, 6, 1;
%e ...
%e T(4,2)=3 because we have 14/3/2, 2/14/3 and 3/2/14 (the unit descents are shown by a /).
%e T(4,2)=3 because we have 14/3/2, 2/14/3 and 3/2/14 (the small descents are shown by a /).
%p G:=exp(-x+t*x)/(1-x)^2: Gser:=simplify(series(G,x=0,15)): for n from 0 to 10 do P[n+1]:=sort(n!*coeff(Gser,x,n)) od: for n from 1 to 11 do seq(coeff(P[n],t,k),k=0..n-1) od; # yields sequence in triangular form
%t Needs["Combinatorica`"];
%t Table[Map[Count[#,1]&,Map[Differences,Permutations[n]]]//Distribution,{n,1,10}]//Grid
%t (* _Geoffrey Critzer_, Dec 15 2012 *)
%t T[n_, k_] := (n-1)! SeriesCoefficient[Exp[-x + t x]/(1-x)^2, {x, 0, n-1}, {t, 0, k}];
%t Table[T[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, Sep 25 2019 *)
%Y Cf. A000166, A000255, A000274, A000313, A001260.
%Y Cf. A010027 (mirror image), A120434, A001100.
%K nonn,tabl
%O 1,4
%A _Emeric Deutsch_, Oct 02 2006
|
