A357927 Number of subsets of [n] in which exactly half of the elements are Fibonacci numbers.

1, 1, 1, 1, 4, 5, 15, 35, 56, 126, 252, 462, 792, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760, 116280, 170544, 245157, 346104, 480700, 657800, 888030, 1184040, 1560780, 2035800, 2629575, 3365856, 4272048, 18156204, 23535820, 30260340, 38608020, 48903492

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Formula

a(n) = binomial(n,A072649(n)).

a(n) = Sum_{j>=0} binomial(A072649(n),j)*binomial(n-A072649(n),j).

Example

a(6) = 15: {}, {1,4}, {1,6}, {2,4}, {2,6}, {3,4}, {3,6}, {4,5}, {5,6}, {1,2,4,6}, {1,3,4,6}, {1,4,5,6}, {2,3,4,6}, {2,4,5,6}, {3,4,5,6}.

Maple

f:= proc(n) option remember; `if`(n=0, 0, f(n-1)+
     `if`((t-> ormap(issqr, [t-4, t+4]))(5*n^2), 1, 0))
    end:
a:= n-> binomial(n, f(n)):
seq(a(n), n=0..38);

Mathematica

f[n_] := Module[{j}, For[j = Floor@Log[GoldenRatio, n], Fibonacci[j+1] <= n, j++]; j-1];
a[n_] := If[n == 0, 1, Binomial[n, f[n]]];
Table[a[n], {n, 0, 38}] (* Jean-François Alcover, Nov 17 2022 *)

Crossrefs

Cf. A000045, A037031, A072649, A102366, A180272, A357812.

Sequence in context: A006491 A321174 A304921 * A051721 A050226 A119562

Adjacent sequences: A357924 A357925 A357926 * A357928 A357929 A357930

Keyword

nonn

Author

Alois P. Heinz, Oct 20 2022

Status

approved