# Number of loops of size k starting from a specific node

Given two positive integer **n, k**. Consider an undirected complete connected graph of n nodes in a complete connected graph. The task is to calculate the number of ways in which one can start from any node and return to it by visiting K nodes.

**Examples: **

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

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

Lets **f(n, k)** be a function which return number of ways in which one can start from any node and return to it by visiting K nodes.

If we start and end from one node, then we have K – 1 choices to make for the intermediate nodes since we have already chosen one node in the beginning. For each intermediate choice, you have n – 1 options. So, this will yield (n – 1)^{k – 1} but then we have to remove all the choices cause smaller loops, so we subtract **f(n, k – 1)**.

So, recurrence relation becomes, f(n, k) = (n - 1)^{k - 1}- f(n, k - 1) with base case f(n, 2) = n - 1. On expanding, f(n, k) = (n - 1)^{k - 1}- (n - 1)^{k - 2}+ (n - 1)^{k - 3}..... (n - 1) (say eqn 1) Dividing f(n, k) by (n - 1), f(n, k)/(n - 1) = (n - 1)^{k - 2}- (n - 1)^{k - 3}+ (n - 1)^{k - 4}..... 1 (say eqn 2) On adding eqn 1 and eqn 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}

Below is the implementation of this approach:

## C++

`// 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

`// 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.` |

## Python3

`# 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#

`// 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` `// 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.` `?>` |

## Javascript

`<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>` |

**Output:**

3