A086443 -id:A086443 - cp's OEIS frontend

A066810 Expansion of x^2/((1-3x)(1-2*x)^2).

0, 0, 1, 7, 33, 131, 473, 1611, 5281, 16867, 52905, 163835, 502769, 1532883, 4651897, 14070379, 42456897, 127894979, 384799049, 1156756443, 3475250065, 10436235955, 31330727961, 94038321227, 282211432673, 846835624611, 2540926304233, 7623651327931, 22872765923121

Offset: 0

N. J. A. Sloane, Jan 25 2002

Binomial transform of A000295.
a(n) = A112626(n, 2). - Ross La Haye, Jan 11 2006
Let Q be a binary relation on the power set P(A) of a set A having n = |A| elements such that for all x,y of P(A), xQy if x is a proper subset of y and |y| - |x| > 1. Then a(n) = |Q|. - Ross La Haye, Jan 11 2008
a(n) is the number of n-digit ternary sequences that have at least two 0's. - Geoffrey Critzer, Apr 14 2009

Harry J. Smith, Table of n, a(n) for n = 0..200
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Index entries for linear recurrences with constant coefficients, signature (7,-16,12).

Column k=1 of A238858 (with different offset).

List([0..30], n-> 3^n - 2^n - n*2^(n-1)); # G. C. Greubel, Nov 18 2019

[3^n-2^n-n*2^(n-1): n in [0..30]]; // Vincenzo Librandi, Nov 29 2015

seq(3^n - 2^n - n*2^(n-1), n=0..30); # G. C. Greubel, Nov 18 2019

RecurrenceTable[{a[n]==3*a[n-1] + (n-1) 2^(n-2), a[0]==0}, a, {n, 0, 30}] (* Geoffrey Critzer, Apr 14 2009 *)
CoefficientList[Series[x^2/((1-3x)(1-2x)^2), {x, 0, 30}], x] (* Vincenzo Librandi, Nov 29 2015 *)

a(n) = 3^n -2^n -n*2^(n-1) \\ Harry J. Smith, Mar 29 2010

[3^n - 2^n - n*2^(n-1) for n in (0..30)] # G. C. Greubel, Nov 18 2019

a(n) = 3^n - 2^n - n*2^(n-1).
From Ross La Haye, Apr 26 2006: (Start)
a(n) = A000244(n) - A001792(n).
a(n) = Sum_{k=2..n} binomial(n,k)2^(n-k). (End)
Inverse binomial transform of A086443. - Ross La Haye, Apr 29 2006
Convolution of A000244 beginning [0,1,3,9,27,81,...] and A001787. - Ross La Haye, Feb 15 2007
From Geoffrey Critzer, Apr 14 2009: (Start)
E.g.f.: exp(2*x)*(exp(x) - x - 1).
a(n) = 3*a(n-1) + (n-1)*2^(n-2). (End)

Additional comments from Ross La Haye, Sep 27 2005

A144697 Triangle of 3-Eulerian numbers.

Original entry on oeis.org

1, 1, 3, 1, 10, 9, 1, 25, 67, 27, 1, 56, 326, 376, 81, 1, 119, 1314, 3134, 1909, 243, 1, 246, 4775, 20420, 25215, 9094, 729, 1, 501, 16293, 115105, 248595, 180639, 41479, 2187, 1, 1012, 53388, 590764, 2048710, 2575404, 1193548, 183412, 6561

Offset: 3

Peter Bala, Sep 19 2008

This is the case r = 3 of the r-Eulerian numbers, denoted by A(r;n,k), defined as follows. Let [n] denote the ordered set {1,2,...,n} and let r be a nonnegative integer. Let Permute(n,n-r) denote the set of injective maps p:[n-r] -> [n], which we think of as permutations of n numbers taken n-r at a time. Clearly, |Permute(n,n-r)| = n!/r!. We say that the permutation p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number A(r;n,k) is defined as the number of permutations in Permute(n,n-r) with k excedances. Thus the 3-Eulerian numbers count the permutations in Permute(n,n-3) with k excedances (see the example section below for a numerical example).
For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144698 (r = 4) and A144699 (r = 5).
An alternative interpretation of the current array due to [Strosser] involves the 3-excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n-3) to have a 3-excedance at position i (1 <= i <= n-3) if p(i) >= i + 3.
Given a permutation p in Permute(n,n-3), define ~p to be the permutation in Permute(n,n-3) that takes i to n+1 - p(n-i-2). The map ~ is a bijection of Permute(n,n-3) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 3-excedance at position n-i-2. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (n-k) 3-excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n-3) with k 3-excedances.
Example: Represent a permutation p:[n-3] -> [n] in Permute(n,n-3) by its image vector (p(1),...,p(n-3)). In Permute(10,7) the permutation p = (1,2,4,10,3,6,5) does not have an excedance in the first two positions (i = 1 and 2) or in the final three positions (i = 5, 6 and 7). The permutation ~p = (6,5,8,1,7,9,10) has 3-excedances only in the first three positions and the final two positions.

			Triangle begins
=================================================
n\k|..0......1......2......3......4......5......6
=================================================
3..|..1
4..|..1......3
5..|..1.....10......9
6..|..1.....25.....67.....27
7..|..1.....56....326....376.....81
8..|..1....119...1314...3134...1909....243
9..|..1....246...4775..20420..25215...9094....729
...
T(5,1) = 10: We represent a permutation p:[n-3] -> [n] in Permute(n,n-3) by its image vector (p(1),...,p(n-3)). The 10 permutations in Permute(5,2) having 1 excedance are (1,3), (1,4), (1,5), (3,2), (4,2), (5,2), (2,1), (3,1), (4,1) and (5,1).

R. Strosser, Séminaire de théorie combinatoire, I.R.M.A., Universite de Strasbourg, 1969-1970.

G. C. Greubel, Rows n = 3..53 of the triangle, flattened
J. F. Barbero G., J. Salas, and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013-2015.
Mark Conger, A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n, arXiv:math/0508112 [math.CO], 2005.
Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 9.
Sergi Elizalde, Descents on quasi-Stirling permutations, arXiv:2002.00985 [math.CO], 2020.
D. Foata and M. Schutzenberger, Théorie Géométrique des Polynômes Eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math., no. 138, Springer Verlag, 1970.
L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 2005-2006.
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012

Cf. A008292, A060056, A143492, A143495, A144696, A144698, A144699.

Cf. A001715 (row sums), A000244 (right diagonal).

m:=3; [(&+[(-1)^(k-j)*Binomial(n+1,k-j)*Binomial(j+m,m-1)*(j+1)^(n-m+1): j in [0..k]])/m: k in [0..n-m], n in [m..13]]; // G. C. Greubel, Jun 04 2022

with(combinat):
T:= (n,k) -> 1/3!*add((-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-2)*(j+2)*(j+3),j = 0..k):
for n from 3 to 11 do
seq(T(n,k),k = 0..n-3)
end do;

T[n_, k_] /; 0 < k <= n-3 := T[n, k] = (k+1) T[n-1, k] + (n-k) T[n-1, k-1];
T[, 0] = 1; T[, _] = 0;
Table[T[n, k], {n, 3, 11}, {k, 0, n-3}] // Flatten (* Jean-François Alcover, Nov 11 2019 *)

m=3 # A144697
def T(n,k): return (1/m)*sum( (-1)^(k-j)*binomial(n+1,k-j)*binomial(j+m,m-1)*(j+1)^(n-m+1) for j in (0..k) )
flatten([[T(n,k) for k in (0..n-m)] for n in (m..13)]) # G. C. Greubel, Jun 04 2022

T(n,k) = (1/3!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*(j+1)^(n-2)*(j+2)*(j+3);
T(n,n-k) = (1/3!)*Sum_{j = 3..k} (-1)^(k-j)*binomial(n+1,k-j)*j^(n-2)*(j-1)*(j-2).
Recurrence relation:
T(n,k) = (k+1)*T(n-1,k) + (n-k)*T(n-1,k-1) with boundary conditions T(n,0) = 1 for n >= 3, T(3,k) = 0 for k >= 1. Special cases: T(n,n-3) = 3^(n-3); T(n,n-4) = A086443 (n-2).
E.g.f. (with suitable offsets): (1/3)*((1 - x)/(1 - x*exp(t - t*x)))^3 = 1/3 + x*t + (x + 3*x^2)*t^2/2! + (x + 10*x^2 + 9*x^3)*t^3/3! + ... .
The row generating polynomials R_n(x) satisfy the recurrence R_(n+1)(x) = (n*x+1)*R_n(x) + x*(1-x)*d/dx(R_n(x)) with R_3(x) = 1. It follows that the polynomials R_n(x) for n >= 4 have only real zeros (apply Corollary 1.2. of [Liu and Wang]).
The (n+2)-th row generating polynomial = (1/3!)*Sum_{k = 1..n} (k+2)!*Stirling2(n,k)*x^(k-1)*(1-x)^(n-k).
For n >= 3,
(1/3)*(x*d/dx)^(n-2) (1/(1-x)^3) = (x/(1-x)^(n+1)) * Sum_{k = 0..n-3} T(n,k)*x^k,
(1/3)*(x*d/dx)^(n-2) (x^3/(1-x)^3) = (1/(1-x)^(n+1)) * Sum_{k = 3..n} T(n,n-k)*x^k,
(1/(1-x)^(n+1)) * Sum_{k = 0..n-3} T(n,k)*x^k = (1/3!) * Sum_{m >= 0} (m+1)^(n-2)*(m+2)*(m+3)*x^m,
(1/(1-x)^(n+1)) * Sum_{k = 3..n} T(n,n-k)*x^k = (1/3!) * Sum_{m >= 3} m^(n-2)*(m-1)*(m-2)*x^m.
Worpitzky-type identities:
Sum_{k = 0..n-3} T(n,k)* binomial(x+k,n) = (1/3!)*x^(n-2)*(x-1)*(x-2);
Sum_{k = 3..n} T(n,n-k)* binomial(x+k,n) = (1/3!)*(x+1)^(n-2)*(x+2)*(x+3).
Relation with Stirling numbers (Frobenius-type identities):
T(n+2,k-1) = (1/3!) * Sum_{j = 0..k} (-1)^(k-j)* (j+2)!* binomial(n-j,k-j)*Stirling2(n,j) for n,k >= 1;
T(n+2,k-1) = (1/3!) * Sum_{j = 0..n-k} (-1)^(n-k-j)* (j+2)!* binomial(n-j,k)*S(3;n+3,j+3) for n,k >= 1 and
T(n+3,k) = (1/3!) * Sum_{j = 0..n-k} (-1)^(n-k-j)*(j+3)!* binomial(n-j,k)*S(3;n+3,j+3) for n,k >= 0, where S(3;n,k) denotes the 3-Stirling numbers A143495(n,k).
The row polynomials of this array are related to the 2-Eulerian polynomials (see A144696). For example, (1/3)*x*d/dx (x^3*(1 + 7*x + 4*x^2)/(1-x)^5) = x^3*(1 + 10*x + 9*x^2)/(1-x)^6 and (1/3)*x*d/dx (x^3*(1 + 18*x + 33*x^2 + 8*x^3)/(1-x)^6) = x^3*(1 + 25*x + 67*x^2 + 27*x^3)/(1-x)^7.
For n >=3, the shifted row polynomial t*R(n,t) = (1/3)*D^(n-2)(f(x,t)) evaluated at x = 0, where D is the operator (1-t)*(1+x)*d/dx and f(x,t) = (1+x*t/(t-1))^(-3). - Peter Bala, Apr 22 2012

A380024 a(n) = 4^n - 3^n - binomial(n,2)*3^(n-2).

Original entry on oeis.org

0, 1, 6, 28, 121, 511, 2152, 9094, 38563, 163729, 694282, 2934592, 12348541, 51697075, 215291356, 891989002, 3677964295, 15099277669, 61745907934, 251632677604, 1022414950465, 4143511249831, 16755357788176, 67628131638478, 272531374722091

Offset: 0

Enrique Navarrete, Feb 05 2025

a(n) is the number of words of length n defined on 4 letters where one of the letters is used at least once but not twice.

			For n=2, the 6 words on {0, 1, 2, 3} that use 0 at least once but not twice are 10, 01, 20, 02, 30, 03.

Index entries for linear recurrences with constant coefficients, signature (13,-63,135,-108).

Cf. A005061, A086443, A380651.

Array[4^#-3^#-Binomial[#,2]*3^(#-2)&,25,0] (* or *) LinearRecurrence[{13,-63,135,-108},{0,1,6,28},25] (* James C. McMahon, Feb 14 2025 *)

def A380024(n): return (1<<(n<<1))-((n*(n-1)>>1)+9)*3**(n-2) if n>1 else n # Chai Wah Wu, Feb 14 2025

E.g.f.: exp(3*x)*(exp(x)-(x^2)/2-1).

G.f.: x*(1 - 7*x + 13*x^2)/((1 - 3*x)^3*(1 - 4*x)). - Stefano Spezia, Mar 03 2025

A380249 a(n) = 4^n - binomial(n,2)*3^(n-2).

Original entry on oeis.org

1, 4, 15, 55, 202, 754, 2881, 11281, 45124, 183412, 753331, 3111739, 12879982, 53291398, 220074325, 906337909, 3721011016, 15228417832, 62133328423, 252794939071, 1025901734866, 4153971603034, 16786738847785, 67722274817305, 272813804258572

Offset: 0

Enrique Navarrete, Feb 06 2025

a(n) is the number of words of length n defined on 4 letters where one of the letters is not used or is used any number of times except twice.

			For n=2, the 15 words on {0, 1, 2, 3} that do not use 0 exactly twice are 12, 21, 13, 31, 23, 32, 11, 22, 33, 10, 01, 20, 02, 30, 03.

Index entries for linear recurrences with constant coefficients, signature (13,-63,135,-108).

Cf. A086443, A380651, A380024.

LinearRecurrence[{13,-63,135,-108},{1,4,15,55},25] (* Stefano Spezia, Mar 03 2025 *)

def A380249(n): return (1<<(n<<1))-(3**(n-2)*n*(n-1)>>1 if n>1 else 0) # Chai Wah Wu, Mar 15 2025

E.g.f.: exp(3*x)*(exp(x)-(x^2)/2).

G.f.: (1 - 9*x + 26*x^2 - 23*x^3)/((1 - 3*x)^3*(1 - 4*x)). - Stefano Spezia, Mar 03 2025

A384415 a(n) = 4^n - 3^n - n3^(n-1) - binomial(n,2)3^(n-2).

Original entry on oeis.org

0, 0, 0, 1, 13, 106, 694, 3991, 21067, 104680, 497452, 2285053, 10222777, 44788342, 192970834, 820244467, 3448381783, 14367483412, 59421385000, 244271688313, 999169721125, 4070288777410, 16525230017710, 66906367267471, 270271938430243

Offset: 0

Enrique Navarrete, May 28 2025

a(n) is the number of strings of length n defined on {0, 1, 2, 3} that contain at least three 0's.

			a(4) = 13 since the strings are the 4 permutations of 0001, the 4 permutations of 0002, the 4 permutations of 0003 and 0000.

Index entries for linear recurrences with constant coefficients, signature (13,-63,135,-108).

Cf. A086443, A345954.

a[n_]:=4^n - 3^n - n*3^(n-1) - Binomial[n,2]*3^(n-2); Array[a,25,0] (* Stefano Spezia, May 29 2025 *)

E.g.f.: exp(3*x)*(exp(x) - x^2/2 - x - 1).

G.f.: x^3/((1 - 3*x)^3*(1 - 4*x)). - Stefano Spezia, May 29 2025

cp's OEIS Frontend

A066810 Expansion of x^2/((1-3*x)*(1-2*x)^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A144697 Triangle of 3-Eulerian numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A380024 a(n) = 4^n - 3^n - binomial(n,2)*3^(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A380249 a(n) = 4^n - binomial(n,2)*3^(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A384415 a(n) = 4^n - 3^n - n*3^(n-1) - binomial(n,2)*3^(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A066810 Expansion of x^2/((1-3x)(1-2*x)^2).

A384415 a(n) = 4^n - 3^n - n3^(n-1) - binomial(n,2)3^(n-2).