重複組合せ

home > さまざまな言語で数値計算 > 数列の積・階乗・順列・組合せ >

重複組合せ

重複組合せ (異なる個のものから重複を許して個とる組合せの総数)は, 次の式で表せます.

組み合わせの計算に用いた関数が, そのまま使えます.

この節では, 異なる $ 10 $ 個のものから重複を許して $ 5 $ 個とる組合せの総数を求めます.

VBScript

'組合せ
Private Function Comb(n, r)
    If (r = 0) Or (r = n) Then
        Comb = 1
    ElseIf r = 1 Then
        Comb = n
    Else
        Comb = Comb(n - 1, r - 1) + Comb(n - 1, r)
    End If
End Function

'重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
Dim n: n = 10
Dim r: r = 5
WScript.Echo(Comb(n + r - 1, r))

Z:\>cscript //nologo 0409.vbs
2002

JScript

// 組合せ
function Comb(n, r) {
    if (r == 0 || r == n)
        return 1
    else if (r == 1)
        return n
    else
        return Comb(n - 1, r - 1) + Comb(n - 1, r)
}

// 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
var n = 10
var r = 5
WScript.Echo(Comb(n + r - 1, r))

Z:\>cscript //nologo 0409.js
2002

PowerShell

# 組合せ
function Comb($n, $r)
{
    if (($r -eq 0) -or ($r -eq $n))
    {
        1
    }
    elseif ($r -eq 1)
    {
        $n
    }
    else
    {
        (Comb ($n - 1) ($r - 1)) + (Comb ($n - 1) $r)
    }
}

# 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
$n = 10
$r = 5
Write-Host (Comb ($n + $r - 1) $r)

Z:\>powershell -file 0409.ps1
2002

Perl

# 組合せ
sub Comb
{
    my ($n, $r) = @_;

    if ($r == 0 || $r == $n)
    {
        1;
    }
    elsif ($r == 1)
    {
        $n;
    }
    else
    {
        Comb($n - 1, $r - 1) + Comb($n - 1, $r);
    }
}

# 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
$n = 10;
$r = 5;
print Comb($n + $r - 1, $r), "\n";

Z:\>perl 0409.pl
2002

PHP

<?php
# 組合せ
function Comb($n, $r)
{
    if ($r == 0 || $r == $n)
        return 1;
    elseif ($r == 1)
        return $n;
    else
        return Comb($n - 1, $r - 1) + Comb($n - 1, $r);
}

# 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
$n = 10;
$r = 5;
echo Comb($n + $r - 1, $r), "\n";
?>

Z:\>php 0409.php
2002

Python

# coding: Shift_JIS

# 組合せ
def Comb(n, r):
    if (r == 0 or r == n):
        return 1
    elif (r == 1):
        return n
    else:
        return Comb(n - 1, r - 1) + Comb(n - 1, r)

# 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
n = 10
r = 5
print Comb(n + r - 1, r)

Z:\>python 0409.py
2002

Ruby

# 組合せ
def Comb(n, r)
    if (r == 0 || r == n)
        1
    elsif (r == 1)
        n
    else
        Comb(n - 1, r - 1) + Comb(n - 1, r)
    end
end

# 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
n = 10
r = 5
puts Comb(n + r - 1, r)

Z:\>ruby 0409.rb
2002

Groovy

Pascal

Program Pas0409(arg);
    
    // 組合せ
    function Comb(n: Integer; r: Integer): Longint;
    begin
        if (r = 0) or (r = n) then
            Comb := 1
        else if r = 1 then
            Comb := n
        else
            Comb := Comb(n - 1, r - 1) + Comb(n - 1, r);
    end;

var
    n: Integer;
    r: Integer;
begin
    // 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
    n := 10;
    r := 5;
    writeln(Comb(n + r - 1, r));
end.

Z:\>fpc Pas0409.pp -v0
Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others

Z:\>Pas0409
2002

Ada

VB.NET

Module VB0409
    '組合せ
    Private Function Comb(ByVal n As Integer, ByVal r As Integer) As Integer
        If (r = 0) OrElse (r = n) Then
            Return 1
        ElseIf r = 1 Then
            Return n
        Else
            Return Comb(n - 1, r - 1) + Comb(n - 1, r)
        End If
    End Function

    Sub Main()
        '重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
        Dim n As Integer = 10
        Dim r As Integer = 5
        Console.WriteLine(Comb(n + r - 1, r))
    End Sub
End Module

Z:\>vbc -nologo VB0409.vb

Z:\>VB0409
2002

C#

using System;

public class CS0409
{
    // 組合せ
    private static int Comb(int n, int r)
    {
        if (r == 0 || r == n)
            return 1;
        else if (r == 1)
            return n;
        else
            return Comb(n - 1, r - 1) + Comb(n - 1, r);
    }

    public static void Main()
    {
        // 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
        int n = 10;
        int r = 5;
        Console.WriteLine(Comb(n + r - 1, r));
    }
}

Z:\>csc -nologo CS0409.cs

Z:\>CS0409
2002

Java

public class Java0409 {

    // 組合せ
    private static int Comb(int n, int r)
    {
        if (r == 0 || r == n)
            return 1;
        else if (r == 1)
            return n;
        elsereturn Comb(n - 1, r - 1) + Comb(n - 1, r);
    }

     public static void main(String []args) {
        // 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
        int n = 10;
        int r = 5;
        System.out.println(Comb(n + r - 1, r));
    }
}

Z:\>javac Java0409.java

Z:\>java Java0409
2002

C++

#include <iostream>

using namespace std;

// 組合せ
int Comb(int n, int r)
{
    if (r == 0 || r == n)
        return 1;
    else if (r == 1)
        return n;
    else
        return Comb(n - 1, r - 1) + Comb(n - 1, r);
}

int main()
{
    // 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
    int n = 10;
    int r = 5;
    cout << Comb(n + r - 1, r) << endl; 

    return 0;
}

Z:\>bcc32 CP0409.cpp
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
CP0409.cpp:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland

Z:\>CP0409
2002

Objective-C

#import <Foundation/Foundation.h>

// 組合せ
int Comb(int n, int r)
{
    if (r == 0 || r == n)
        return 1;
    else if (r == 1)
        return n;
    else
        return Comb(n - 1, r - 1) + Comb(n - 1, r);
}

int main()
{
    // 重複組合せ (異なる 10 個のものから重複を許して 5 個とる組合せの総数)
    int n = 10;
    int r = 5;
    printf("%d\n", Comb(n + r - 1, r));

    return 0;
}

Compiling the source code....
$gcc `gnustep-config --objc-flags` -L/usr/GNUstep/System/Library/Libraries -lgnustep-base main.m -o demo -lm -pthread -lgmpxx -lreadline 2>&1

Executing the program....
$demo
2002

D

Go

Scala

対話型実行環境を起動

Z:\>scala
Welcome to Scala version 2.10.2 (Java HotSpot(TM) Client VM, Java 1.7.0_21).
Type in expressions to have them evaluated.
Type :help for more information.

// 組合せ
def Comb(n: Int, r: Int): Int = {
    (n, r) match {
        case (_, 0)           => 1
        case (_, 1)           => n
        case (_, _) if n == r => 1
        case (_, _)           => Comb(n - 1, r - 1) + Comb(n - 1, r)
    }
}

// 異なる 10 個のものから重複を許して 5 個とる組合せの総数
val n = 10
val r = 5
Comb(n + r - 1, r)

res0: Integer = 2002

終了

scala> :quit

F#

対話型実行環境を起動

Z:\>fsi
Microsoft (R) F# 2.0 Interactive build 4.0.40219.1
Copyright (c) Microsoft Corporation. All Rights Reserved.

For help type #help;;

// 組合せ
let rec Comb(n:int) (r:int):int =
    match n, r with
        | _, 0            -> 1
        | _, 1            -> n
        | _, _ when n = r -> 1
        | _, _            -> Comb (n - 1) (r - 1) + Comb(n - 1) r

// 異なる 10 個のものから重複を許して 5 個取る組合せの総数
let n = 10
let r = 5
Comb (n + r - 1) r

val it : int = 2002

終了

> #quit;;

Clojure

対話型実行環境を起動

Z:\>java -cp C:\ProgramFiles\clojure-1.5.1\clojure-1.5.1.jar clojure.main
Clojure 1.5.1

; 組合せ
(defn Comb [n r]
    (cond (or (= r 0) (= r n)) 1
          (= r 1)              n
          true                 (+ (Comb (- n 1) (- r 1)) (Comb (- n 1) r))))

; 異なる 10 個のものから重複を許して 5 個取る組合せの総数
(def n 10)
(def r 5)
(Comb (+ n (- r 1)) r)

終了

user=> (. System exit 0)

Haskell

対話型実行環境を起動

Z:\>ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.

-- 組合せ
comb n 0 = 1
comb n 1 = n
comb n r
    | n == r    = 1
    | otherwise = (comb (n - 1) (r - 1)) + (comb (n - 1) r)

-- 異なる 10 個のものから重複を許して 5 個取ってできる組合せの総数
let n = 10
let r = 5
comb (n + r - 1) r

終了

Prelude> :quit
Leaving GHCi.

VBScript
JScript
PowerShell
Perl
PHP
Python
Ruby
Groovy

Pascal
Ada
VB.NET

C#
Java
C++
Objective-C
D
Go

Scala
F#
Clojure
Haskell