Número de bucles de tamaño k a partir de un Node específico

Dados dos enteros positivos n, k . Considere un grafo conexo completo no dirigido de n Nodes en un grafo conexo completo. La tarea es calcular el número de formas en que uno puede comenzar desde cualquier Node y regresar visitando K Nodes.
Ejemplos: 
 

Input : n = 3, k = 3
Output : 2

Input : n = 4, k = 2
Output : 3

Sea f(n, k) una función que devuelve un número de formas en las que se puede empezar desde cualquier Node y volver a él visitando K Nodes. 
Si comenzamos y terminamos desde un Node, entonces tenemos K – 1 elecciones para hacer para los Nodes intermedios ya que ya hemos elegido un Node al principio. Para cada opción intermedia, tiene n – 1 opciones. Entonces, esto producirá (n – 1) ^{k – 1} pero luego tenemos que eliminar todas las opciones que causan bucles más pequeños, por lo que restamos f(n, k – 1) . 
Entonces, la relación de recurrencia se convierte en 
f(n, k) = (n – 1) ^{k – 1} – f(n, k – 1) con el caso base f(n, 2) = n – 1. 
Al expandir, 
f(n , k) = (n – 1) ^{k – 1} – (n – 1) ^{k – 2} + (n – 1)^{k – 3} ….. (n – 1) (digamos ecuación 1)
Dividiendo f(n, k) por (n – 1), 
f(n, k)/(n – 1) = (n – 1) ^{k – 2} – (n – 1) ^{k – 3} + (n – 1) ^{k – 4} ….. 1 (digamos la ecuación 2)
Al sumar la ecuación 1 y la ecuación 2, 
f(n, k) + f(n, k)/ (n – 1) = (n – 1) ^{k – 1} + (-1) ^k 
f(n, k) * ( (n -1) + 1 )/(n – 1) = (n – 1) ^{k – 1} + (-1) ^k

A continuación se muestra la implementación de este enfoque:
 

// C++ Program to find number of cycles of length
// k in a graph with n nodes.
#include <bits/stdc++.h>
using namespace std;
  
// Return the Number of ways from a
// node to make a loop of size K in undirected
// complete connected graph of N nodes
int numOfways(int n, int k)
{
    int p = 1;
  
    if (k % 2)
        p = -1;
  
    return (pow(n - 1, k) + p * (n - 1)) / n;
}
  
// Driven Program
int main()
{
    int n = 4, k = 2;
    cout << numOfways(n, k) << endl;
    return 0;
}

// Java Program to find number of
// cycles of length k in a graph
// with n nodes.
public class GFG {
      
    // Return the Number of ways
    // from a node to make a loop
    // of size K in undirected
    // complete connected graph of
    // N nodes
    static int numOfways(int n, int k)
    {
        int p = 1;
      
        if (k % 2 != 0)
            p = -1;
      
        return (int)(Math.pow(n - 1, k)
                    + p * (n - 1)) / n;
    }
      
    // Driver code
    public static void main(String args[])
    {
        int n = 4, k = 2;
      
        System.out.println(numOfways(n, k));
    }
}
  
// This code is contributed by Sam007.

# python Program to find number of 
# cycles of length k in a graph 
# with n nodes.
  
# Return the Number of ways from a
# node to make a loop of size K in
# undirected complete connected 
# graph of N nodes
def numOfways(n,k):
      
    p = 1
  
    if (k % 2):
        p = -1
  
    return (pow(n - 1, k) +
                   p * (n - 1)) / n
  
# Driver code
n = 4
k = 2
print (numOfways(n, k))
  
# This code is contributed by Sam007.

// C# Program to find number of cycles
// of length k in a graph with n nodes.
using System;
  
class GFG {
      
    // Return the Number of ways from
    // a node to make a loop of size
    // K in undirected complete 
    // connected graph of N nodes
    static int numOfways(int n, int k)
    {
        int p = 1;
      
        if (k % 2 != 0)
            p = -1;
      
        return (int)(Math.Pow(n - 1, k)
                     + p * (n - 1)) / n;
    }
      
    // Driver code
    static void Main()
    {
        int n = 4, k = 2;
          
        Console.Write( numOfways(n, k) );
    }
}
  
// This code is contributed by Sam007.

<?php
// PHP Program to find number
// of cycles of length
// k in a graph with n nodes.
  
// Return the Number of ways from a
// node to make a loop of size K 
// in undirected complete connected
// graph of N nodes
function numOfways( $n, $k)
{
$p = 1;
  
if ($k % 2)
    $p = -1;
  
return (pow($n - 1, $k) + 
        $p * ($n - 1)) / $n;
}
  
    // Driver Code
    $n = 4;
    $k = 2;
    echo numOfways($n, $k);
      
// This code is contributed by vt_m. 
?>

<script>
  
// JavaScript Program to find number of
// cycles of length k in a graph
// with n nodes.
  
    // Return the Number of ways
    // from a node to make a loop
    // of size K in undirected
    // complete connected graph of
    // N nodes
    function numOfways(n, k)
    {
        let p = 1;
        
        if (k % 2 != 0)
            p = -1;
        
        return (Math.pow(n - 1, k)
                    + p * (n - 1)) / n;
    }
   
// Driver code
         let n = 4, k = 2;
        document.write(numOfways(n, k));
      
    // This code is contributed by code_hunt.
</script>

3