login
Number of compositions of n when parts 1 and 2 are of two kinds.
10

%I #41 Jun 30 2021 18:05:08

%S 1,2,6,17,49,141,406,1169,3366,9692,27907,80355,231373,666212,1918281,

%T 5523470,15904198,45794313,131859469,379674209,1093228314,3147825473,

%U 9063802210,26098178316,75146709475,216376326215,623030800329

%N Number of compositions of n when parts 1 and 2 are of two kinds.

%C The g.f. for compositions of k_1 kinds of 1's, k_2 kinds of 2's, ..., k_j kinds of j's, ... is 1/(1 - Sum_{j>=1} k_j * x^j). - _Joerg Arndt_, Jul 06 2011

%H Michael De Vlieger, <a href="/A052536/b052536.txt">Table of n, a(n) for n = 0..2177</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=467">Encyclopedia of Combinatorial Structures 467</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-1).

%F G.f.: (1-x)/(1 - 3*x + x^3).

%F G.f.: 1/(1 - (2*x + 2*x^2 + Sum_{j>=3} x^j)). - _Joerg Arndt_, Jul 06 2011

%F a(n) = Sum(-(1/9)*(-2 + r^2 - r)*r^(-1-n)), r = RootOf(1 - 3*x + x^3).

%F a(0)=1, a(1)=2, a(2)=6, a(n) = 3*a(n-1) - a(n-3) for n >= 3. - _Emeric Deutsch_, Apr 10 2005

%F a(n) = left term in M^n * [1 0 0], where M = the 3 X 3 matrix [2 1 1 / 1 1 0 / 1 0 0]. Right term in M^n *[1 0 0] is a(n-1); middle term is A076264(n-1). - _Gary W. Adamson_, Sep 05 2005

%F 3*a(n) = A123891(n+1). - _Jeffrey R. Goodwin_, Jul 03 2011

%e a(2)=6 because we have (2),(2'),(1,1),(1,1'),(1',1) and (1',1').

%p spec := [S,{S=Sequence(Union(Z,Prod(Z,Union(Z,Sequence(Z)))))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

%t a[0] = 1; a[1] = 2; a[2] = 6; a[n_] := a[n] = 3*a[n-1] - a[n-3]; Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Jun 12 2013, after _Emeric Deutsch_ *)

%o (PARI) Vec((1-x)/(1-3*x+x^3)+O(x^99)) \\ _Charles R Greathouse IV_, Nov 20 2011

%Y Row sums of A105478.

%Y Cf. A105478, A076264.

%K easy,nonn

%O 0,2

%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000

%E More terms from _James A. Sellers_, Jun 06 2000

%E Edited by _Emeric Deutsch_, Apr 10 2005

%E More terms from _Gary W. Adamson_, Sep 05 2005