A046739 -id:A046739 - cp's OEIS frontend

A219836 Triangular array counting derangements by number of descents.

1, 2, 0, 4, 4, 1, 8, 24, 12, 0, 16, 104, 120, 24, 1, 32, 392, 896, 480, 54, 0, 64, 1368, 5544, 5984, 1764, 108, 1, 128, 4552, 30384, 57640, 34520, 6048, 224, 0, 256, 14680, 153400, 470504, 495320, 180416, 19936, 448, 1

Offset: 2

David Callan, Nov 29 2012

T(n,k) is the number of derangements of [n] with k descents.

			Array begins
1
2, 0
4, 4, 1
8, 24, 12, 0
16, 104, 120, 24, 1
T(4,2) = 4 counts 2143, 3142, 3421, 4312.

Shishuo Fu, Z. Lin, J. Zeng, Two new unimodal descent polynomials, arXiv preprint arXiv:1507.05184 [math.CO], 2015-2019.

Cf. A008292. (analogous for permutations)

Row sums give A000166. A046739 counts derangements of [n] by number of excedances.

u[n_, 0] := 0; u[n_, k_] /; k == n-1 := If [EvenQ[n], 1, 0]; u[n_, k_] /; 1 <= k <= n - 2 := (n - k) u[n - 1, k - 1] + (k + 1) u[n - 1, k]; Table[u[n, k], {n, 2, 10}, {k, n - 1}]

The g.f. F(x,y) = Sum_{n>=2,1<=k<=n-1}T(n,k)x^n/n!y^k satisfies the partial differential equation (1-xy) D_{x}F + (y^2-y) D_{y}F = F + 1 - e^(-xy). (Is there a closed form solution?)

A065340 Third diagonal of triangle in A046740.

Original entry on oeis.org

2, 28, 182, 864, 3474, 12660, 43358, 142552, 455930, 1430796, 4431078, 13595664, 41441570, 125732836, 380212142, 1147057800, 3454803594, 10393245180, 31240551350, 93849578560, 281817169202, 846013542228, 2539215029502, 7620094559544, 22865383949594

Offset: 4

N. J. A. Sloane, May 15 2002

D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16. [Annotated scanned copy]
Index entries for linear recurrences with constant coefficients, signature (10,-40,82,-91,52,-12).

Cf. A046740.

a(n) = 3^n-(3*n+1)*2^(n-1)+2*n^2-2*n+1; \\ Michel Marcus, Oct 25 2017

a(n) = 3^n-(3*n+1)*2^(n-1)+2*n^2-2*n+1. - Vladeta Jovovic, Jan 04 2003

G.f.: -2*x^4*(9*x^2-4*x-1) / ((x-1)^3*(2*x-1)^2*(3*x-1)). [Colin Barker, Feb 03 2013]

More terms from Colin Barker, Feb 03 2013

A321967 Triangle read by rows, T(n,k) = binomial(-k-n-1, -2n-1)E1(k+n, n), E1 the Eulerian numbers A173018, for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, -4, 11, 0, 15, -156, 302, 0, -56, 1596, -9528, 15619, 0, 210, -14400, 193185, -882340, 1310354, 0, -792, 122265, -3213760, 30042672, -116857368, 162512286, 0, 3003, -1005004, 47887840, -802069632, 6034981134, -21078701112, 27971176092

Offset: 0

Peter Luschny, Dec 18 2018

			Triangle starts:
                       1;
                  0,        1;
              0,      -4,       11;
          0,     15,      -156,      302;
       0,   -56,     1596,    -9528,     15619;
    0,   210,  -14400,   193185,   -882340,   1310354;
  0, -792, 122265, -3213760, 30042672, -116857368, 162512286;

Row sums give A320337.

Cf. A046739, A180056 (main diagonal), A271697, A001791.

T := (n, k) -> binomial(-k-n-1, -2*n-1)*combinat:-eulerian1(k+n, n):
for n from 0 to 7 do seq(T(n,k), k=0..n) od;

E1[n_ /; n >= 0, 0] = 1; E1[n_, k_] /; k < 0 || k > n = 0;
E1[n_, k_] := E1[n, k] = (n - k) E1[n - 1, k - 1] + (k + 1) E1[n - 1, k];
T[n_, k_] := Binomial[-k - n - 1, -2 n - 1] E1[n + k, n];
Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten
(* Jean-François Alcover, Dec 30 2018 *)

A363656 Number of bounded affine permutations of size n.

Original entry on oeis.org

1, 3, 13, 87, 761, 8243, 106037, 1578671, 26685361, 504770859, 10562259533, 242216304839, 6040459572681, 162750100464643, 4711225866217381, 145818462291970911, 4805369568409107809, 167982555421167341147, 6208589923091273031293, 241898639921607255506039

Offset: 1

Justin M. Troyka, Jun 14 2023

nonn

An affine permutation of size n is a bijection p from the integers to the integers that satisfies (1) p(i+n) = p(i) + n for all i and (2) Sum_{i=1..n} p(i) = Sum_{i=1..n} i. A bounded affine permutation of size n is an affine permutation of size n that satisfies (3) |p(i) - i| < n for all i.

			Let [a,b] denote the affine permutation p of size 2 determined by p(1) = a and p(2) = b.
The 3 bounded affine permutations of size 2 are [1,2], [2,1], and [0,3], so a(2) = 3.

Alois P. Heinz, Table of n, a(n) for n = 1..404
N. Madras and J. M. Troyka, Bounded affine permutations I. Pattern avoidance and enumeration, Discrete Math. Theor. Comput. Sci. 22(2) (2021), #1.
N. Madras and J. M. Troyka, Bounded affine permutations II. Avoidance of decreasing patterns, Ann. Comb. 25 (2021), 1007-1048.

Cf. A046739, A173018.

a(n) = Sum_{m=0..n} binomial(n,m) Sum_{k=0..m} binomial(m,k) A046739(m,k) (Madras and Troyka I, Thm. 38(a)).
a(n) = Sum_{m=0..n} binomial(n,m) Sum_{k=0..m} binomial(m,n-k) (-1)^(n-m) A173018(m,k) (Madras and Troyka I, Thm. 38(b)).
a(n) ~ sqrt[3/(2*pi*e)] n^(-1/2) 2^n n! (Madras and Troyka I, Thm. 45).

A168423 Triangle read by rows: expansion of (1 - x)/(exp(t)(1 - xexp(t*(1 - x)))).

Original entry on oeis.org

1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 7, 1, -1, 1, 1, 21, 21, 1, 1, -1, 1, 51, 161, 51, 1, -1, 1, 1, 113, 813, 813, 113, 1, 1, -1, 1, 239, 3361, 7631, 3361, 239, 1, -1, 1, 1, 493, 12421, 53833, 53833, 12421, 493, 1, 1, -1, 1, 1003, 42865, 320107, 607009, 320107, 42865

Offset: 0

Roger L. Bagula, Nov 25 2009

This sequence was derived from the Eulerian number umbral calculus expansion and A046802 by taking the exp(t) term and inverting it.
What is interesting here is the '1,-1' terms that appear.
I had thought I would get "1,5,1" not "1,7,1" from this function.
An OEIS search came up with A046739 which has the same internal symmetric number structure.
Inverse binomial transform of Eulerian numbers A123125. [Paul Barry, May 10 2011]

			{1},
{-1, 1},
{1, -1, 1},
{-1, 1, 1, 1},
{1, -1, 1, 7, 1},
{-1, 1, 1, 21, 21, 1},
{1, -1, 1, 51, 161, 51, 1},
{-1, 1, 1, 113, 813, 813, 113, 1},
{1, -1, 1, 239, 3361, 7631, 3361, 239, 1},
{-1, 1, 1, 493, 12421, 53833, 53833, 12421, 493, 1},
{1, -1, 1, 1003, 42865, 320107, 607009, 320107, 42865, 1003, 1}

Cf. A046802, A046739, A000166 (row sums), A123125.

p[t_] = (1 - x)/(Exp[t]*(1 - x*Exp[t*(1 - x)]))
a = Table[ CoefficientList[FullSimplify[ExpandAll[n!*SeriesCoefficient[ Series[p[t], {t, 0, 30}], n]]], x], {n, 0, 10}];
Flatten[a]

E.g.f. sum(T(n,k) t^n/n! x^k) = p(x,t) = (1 - x)/(exp(t)*(1 - x*exp(t*(1 - x))))

T(n,k)=sum{j=0..n, (-1)^(n-j)*C(n,j)*A123125(j,k)}. [Paul Barry, May 10 2011]

A385588 Number of non-derangements of length n with 2 excedances.

Original entry on oeis.org

0, 4, 45, 251, 1078, 4054, 14115, 46837, 150612, 474200, 1471561, 4520959, 13792002, 41867242, 126649983, 382177817, 1151251648, 3463715980, 10412118981, 31280396611, 93933463950, 281993329214, 846382640155, 2539986780541, 7621705171308, 22868739391744, 68613734367105, 205856772356807

Offset: 3

Aurora Hiveley, Jul 03 2025

Number of permutations of length n guessed by a cyclic shifting strategy in 3 guesses such that the first correct entry occurs on guess 1. In other words, non-derangements guessable by cyclic shift in 3 guesses.

			For n=4, the non-derangements with 2 excedances are 1342, 2314, 2431, and 3241.

Aurora Hiveley, Experimenting with Permutation Wordle, arXiv:2506.23452 [math.CO], 2025.
Index entries for linear recurrences with constant coefficients, signature (10,-40,82,-91,52,-12).

Summation uses k=2 row of A046739.

LinearRecurrence[{10, -40, 82, -91, 52, -12}, {0, 4, 45, 251, 1078, 4054}, 28] (* Hugo Pfoertner, Jul 03 2025 *)

a(n) = 1 - 2^(n+1) + 3^n + n^2/2 + 5*n/2 - n*2^n.
a(n) = Sum_{k=1..n-3} binomial(n,k)*(2^(n-k) - 2*n + 2*k - 1).
G.f.: x^4 * (4 + 5*x - 39*x^2 + 40*x^3 - 12*x^4) / ((1 - x)^3 * (1 - 2*x)^2 * (1 - 3*x)). - Stefano Spezia, Jul 03 2025

cp's OEIS Frontend

A219836 Triangular array counting derangements by number of descents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A065340 Third diagonal of triangle in A046740.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A321967 Triangle read by rows, T(n,k) = binomial(-k-n-1, -2*n-1)*E1(k+n, n), E1 the Eulerian numbers A173018, for n >= 0 and 0 <= k <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

A363656 Number of bounded affine permutations of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A168423 Triangle read by rows: expansion of (1 - x)/(exp(t)*(1 - x*exp(t*(1 - x)))).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A385588 Number of non-derangements of length n with 2 excedances.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A321967 Triangle read by rows, T(n,k) = binomial(-k-n-1, -2n-1)E1(k+n, n), E1 the Eulerian numbers A173018, for n >= 0 and 0 <= k <= n.

A168423 Triangle read by rows: expansion of (1 - x)/(exp(t)(1 - xexp(t*(1 - x)))).