Number of combinations with C-pair of N elements

Question

I have N buckets. Each bucket can contain 0 or 1. C is number that represents how many number 1 is showing continuously (e.g. if C=3 i would have 111).

E.g. for N=5 and C=2, total number of all combinations is 19 (yellow and gray rows are duplicates) (here C=2, so I have always to have at least two ones - 11 in row):

And this is calculation for first 20 N and C numbers (I marked yellow case above):

How to get to the formula that depends on C and N ?

Answer 1

I managed to create general n-Order Fibonacci alg. in O(logN). Not sure if it can be made faster in iterative/recursive way without formula?

import java.util.HashMap;
import java.util.Map;

public class nOrderFibonacci {

    Map<Long, Long> map = new HashMap<>();

    long fib(int n, long k){
        if(k==n-1){
            return 1;
        }
        if(k<n-1){
            return 0;
        }
        if((k%2==0 && n%2==0) || (k%2!=0 && n%2!=0)){
            long k21 = (k+(n-2))/2;
            long[] fn = new long[n];
            for(int i=0; i<n; i++){
                long v = k21-i;
                fn[i] = map.computeIfAbsent(v, g -> fib(n,g));
            }
            long f = 0;
            for(int i=0; i<n; i++){
                long fi = fn[i];
                long fis = 0;
                for(int j=0; j<n-i; j++){
                    fis += fn[j];
                }
                f += fi*fis;
            }
            return f;
        }
        else{
            long k22 = (k+(n-3))/2;
            long[] fn = new long[n];
            for(int i=0; i<n; i++){
                long v = k22-i;
                fn[i] = map.computeIfAbsent(v, g -> fib(n,g));
            }
            long f = 0;
            for(int i=0; i<n; i++){
                long fi = fn[i];
                long fis = 0;
                for(int j=0; j<n; j++){
                    fis += ((i+j < n-1 ? 2 : 1) * fn[j]);
                }
                f += fi*fis;
            }
            return f;
        }

    }

    public static void main(String[] args) {
        int firstX = 20;
        //Fibonacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(2, i));
        }
        //Tribonacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(3, i));
        }
        //Tetranacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(4, i));
        }
        //Pentanacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(5, i));
        }
        //Hexanacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(6, i));
        }
        //Heptanacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(7, i));
        }
        //Octanacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(8, i));
        }
        //Enneanacci
        for(int i = 0; i<firstX; i++) {
            System.out.println(new nOrderFibonacci().fib(9, i));
        }
    }
}

Answer 2

Thanks to the comment above, I managed to find algorithm to generate this sequence:

    private static int fib(int a, int b){
        if(b>a)
            return 0;
        if(a == b)
            return 1;
        int sum = 0;
        for(int i = a-b; i<=a-1; i++){
            sum += fib(i,b);
        }
        return sum;
    }

    private static int calculate(int N, int C){
        return (int) (Math.pow(2, N) - fib(N + C + 1, C));
    }