Firstly, Information about Ferrers diagram can be found in this previous article

A recursively palindromic (RP) word is one that is a palindrome and whose left

half-word and right half-word are each RP. Thus ABACABA is, and MADAM is not,

an RP word. – quoted from this Paper .

The objective of this puzzle is to find the total number of RP that can be formed from the integer partitions of a number

For example:

for number = 4

Ferrers Diagram

4 = 1+1+1+1

4 = 2+1+1

4 = 2+2

4 = 3+1

4 = 4

The total no of the RP partitions are 4

4

1+1+1+1

2+2

1+2+1

Note: every integer > 1 has at least two recursively palindromic partitions one consisting of all ones and a second consisting of the integer itself

Algorithm 1:

1 . Construct the Ferrer Diagram using the algorithm used in this article

2. For all Ferrers Partitions

3. Send every partition values to a function called PossiblePalindrome described in this article.

4. If successful, increment a counter

Algorithm 2:

1. F(N) is the no of RP’s of N

2. if N is even, put any even number K <= N in the center and then a RP partition of (N-K)/2 on either side so

F(N) = 1 + F(2) + … + F(N/2) = F(N-2) + F(N/2) (1 is the case where K = N)

3.if N is odd, put any odd number K <= N in the center and then RP partition of (N-K)/2 on either side so

F(N) = 1 + F(2) + … + F((N-1)/2) = F(N-1) (1 is the case where K = N)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int array[100];
int max;
int PalindromePartition(int val)
{
int i;
if(val <= max)
{
return array[val];
}
for(i = max+1; i <= val; i++)
{
if((i & 1) != 0)
{
array[i] = array[i-1];
}
else
{
array[i] = array[i-2] + array[i/2];
}
}
max = val;
return array[val];
}
int main()
{
int num;
printf("Enter the Number:\n");
scanf("%d",&num);
array[0] = array[1] = 1;
max = 1;
PalindromePartition(10);//compute for until 10 or any number
printf("The total number of possible Palindrome partitions are %d\n",array[num]);
return 0;
}

OUTPUT:

laptop:~/code$ ./a.out

Enter the Number:

7

The total number of possible Palindrome partitions are 6

Look at ferrers table for 7

7 = 1+1+1+1+1+1+1

7 = 2+1+1+1+1+1

7 = 2+2+1+1+1

7 = 2+2+2+1

7 = 3+1+1+1+1

7 = 3+2+1+1

7 = 3+2+2

7 = 3+3+1

7 = 4+1+1+1

7 = 4+2+1

7 = 4+3

7 = 5+1+1

7 = 5+2

7 = 6+1

7 = 7

It is evident visually that from these 15 partitions only 6 are RP.

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

It would be interesting to implement a function to print the RP in a formatted manner.

Thanks for Reading !

### Like this:

Like Loading...

*Related*

Was very useful… Thanks