For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. Combinatorics is a ...

learn more… | top users | synonyms (4)

1
vote
2answers
39 views

Double Factorial

I am having trouble proving/understanding this question. Let $n=2k$ be even, and $X$ a set of $n$ elements. Define a factor to be a partition of $X$ into $k$ sets of size $2$. Show that the ...
1
vote
2answers
50 views

combinatorics dice question

There are $10$ identical dice ($1$ - $6$). How many different results can we get so that the set of results will be exactly $3$. for example: $7$ dice will be the number $2$, $2$ dice will be $3$ and ...
1
vote
0answers
34 views

Generating function from a set of binary strings

So this question is in my textbook and there's no solution, so I'm seeing if I can get a confirmation? Q: Let $S$ be the set of all binary strings of length 4, where for each string $a\in S$, the ...
2
votes
1answer
24 views

Different combinations of objects with restrictions

first of all please excuse the title, hopefully the question will make it more clear. Suppose that there are 17 students in a class. For assignment 1, the students are to partition themselves into 4 ...
1
vote
1answer
14 views

Combinatorics Number of Possible Assignment Combinations

Say I have Group A and Group B Group A needs 1 student and group B needs 2 students. There are 3 students total (A,B,C). What sort of formula could I use to determine the total number of assignment ...
3
votes
3answers
83 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
4
votes
2answers
41 views

What is the number $p(n)$ of partitions of an abundant number $n$ into distinct, proper divisors of $n$?

For lack of a better symbol, $p_{\sigma\tau}(n)$ (feel free to suggest something better). For example, $p_{\sigma\tau}(12) \geq 2$ since $12 = 1 + 2 + 3 + 6 = 2 + 4 + 6$. Of course if $n$ is ...
0
votes
1answer
23 views

permutation on relations

Let $A = \{1, 2, 3, 4\}$. Call a binary relation on $A$ interesting if it is symmetric or it does not contain the pair $(1, 4)$. How to calculate the number of interesting binary relations on $A$. My ...
3
votes
1answer
37 views

Bringing a permutation back to the identity

I'm working with transposition distance (nothing to do with algebraic transpositions) on given permutations. Given a permutation, how many moves (transpositions) will it take to get back to the ...
3
votes
2answers
151 views

Combinatorial Proof Of A Number Theory Theorem--Confusion

I came across a combinatorial proof of the Fermat's Little Theorem which states that If $p$ is a prime number then the number ($a$$p$-$a$) is a multiple of $p$ for any natural number $a$. Let me ...
3
votes
5answers
195 views

$n\times n$ board, non-challenging rooks

Consider an $n \times n$ board in which the squares are colored black and white in the usual chequered fashion and with at least one white corner square. (i) In how many ways can $n$ non-challenging ...
0
votes
1answer
47 views

Generating Functions of Partitions?

Show that $2(1-x)^{-3} [(1-x)^{-3} + (1+x)^{-3}]$ is the generating function for the number of ways to toss $r$ identical dice and obtain an even sum. Workings: I'm not too sure on this problem. ...
6
votes
1answer
54 views

Number of ways to pick N numbers from 0,1,…,N-1, with possible duplication, with sum equal 0 mod N

We have the numbers $0,1,2,....,N-1$ in $\mathbb Z_N.$ I want to pick $N$ numbers from these. These are the rules: Duplication may occur We don't care about ordering, $00041$ is equivalent to ...
0
votes
1answer
28 views

With $m>n$ , In how many ways $m$ men and $n$ women can seat in row for a photograph so that no two women are adjacent? [duplicate]

Given $m>n$ , In how many ways $ m$ men and $n$ women can seat in row for a photograph so that no two women are adjacent? My effort : There are $m-1$ gaps if $m$ men are seated. Now we have to ...
3
votes
0answers
49 views

$n$ solutions Sudoku

Is there an algorithm which can calculate a $9 \times 9$ Sudoku with non-trivial $n$ possible solutions? So if you play it you can play it for example 4 times? So if you play it there's a choice in ...
10
votes
3answers
3k views

Combinatorial interpretation of sum of squares, cubes

Consider the sum of the first $n$ integers: $$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$ This has always made the following bit of combinatorial sense to me. Imagine the set ...
6
votes
1answer
114 views

Combinatorial interpretation of a sum identity: $\sum_{k=1}^n(k-1)(n-k)=\binom{n}{3}$

I solved $\sum_{k=1}^n(k-1)(n-k)$ algebraically \begin{eqnarray*} \sum_{k=1}^n(k-1)(n-k)&=&\sum_{k=1}^n(nk-n-k^2+k)\\ &=&\sum_{k=1}^nnk-\sum_{k=1}^nn-\sum_{k=1}^nk^2+\sum_{k=1}^nk\\ ...
7
votes
3answers
479 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
1
vote
0answers
35 views

Counting problems that still remains unsolved?

I just proved that the cartesian product of $\mathbb{Q}$ and $\mathbb{N}$ is countable and I started to wonder if there exists any sets that is still not yet proven to be countable/uncountable? Also, ...
1
vote
1answer
29 views

Combinations with Repetition

I am looking the basics of combinations with repetition. The other name is Stars and Bars problem. On MIT OCW I found this: An ice-cream store specializes in super-sized deserts. They offer a ...
3
votes
1answer
21 views

Exponents with Combinatorics

How many of the first $242$ positive integers are expressible as a sum of three or fewer members of the set $\{3^0,3^1,3^2,3^3,3^4\}$ if we are allowed to use the same power more than once. For ...
2
votes
3answers
73 views

The number of positive integers less than 1000 with an odd number of divisors

How many positive integers less than 1000 have an odd number of positive integer divisors? Well I know that the number has to be composite because a prime number has 2 divisors, which are 1 and ...
0
votes
1answer
25 views

Solving a summation where the inner summation is limited by the iterator of the two outer summations

I'm trying to solve the following summation (where C is some constant) but I'm stuck because of the inner most summation which is limited by $i\sqrt[2]{j}$ where i and j are the iterators of the outer ...
1
vote
1answer
269 views

Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
0
votes
1answer
45 views

proof of the negative binomial series using induction?

$$(1-x)^{-n} = \sum_{k\ge0}{k+n-1 \choose n-1}x^k$$ I'm supposed to prove this for any integer n $\ge$ 1 via induction on n. Base case where n = 1 is easy enough to prove, but what about the ...
2
votes
0answers
39 views

Zeilbergers algorithm in Maple

I try to prove several hard combinatorial identities. One of them is following \begin{align*} \sum_{s=0}^{\min\{k,n-1\}} \sum_{i=0}^{k-s} (-1)^{i} {2n+k-i-1 \choose k-s-i} {i-n \choose s} {n+i-1 ...
2
votes
3answers
79 views

Combinatorics Problem w/ money (exact purchase with XXX coins)

Mr. Long Johns has 2 pennies, 3 nickels, 2 dimes, 3 quarters, and 8 dollar coins. For how many different amounts can John make an exact purchase? (no change required) A penny is 1 cent A nickel is 5 ...
1
vote
2answers
543 views

Show how the probability that an 8 character password contains exactly 1 OR 2 integers is .630

A password is 8 characters long. Each character can contain 26 lower case or 26 uppercase letters or a integer from 0-9. What is the probability that an 8 character password contains exactly 1 OR 2 ...
1
vote
1answer
37 views

Generating Functions for Two Variables

Find the generating function for the number of words, from the standard 26-letter alphabet, that have $k$ letter with exactly 1 A and at least 2 Bs. ($k$ will vary) Workings: For the time being I'm ...
0
votes
1answer
31 views

Rank notion of a matrix

$\newcommand{\rank}{\operatorname{rank}}$Divide $p-1$ ($p=q^k>2$ with $k>1$, $q$ prime) elements in $\Bbb F_p^\times$ into equal disjoint subsets $S_+,S_-$. Given square $0-1$ matrix $A$, ...
2
votes
1answer
22 views

Finding external angles for Misiurewicz points in the Mandelbrot set

In the Mandelbrot set for the quadratic polynomial $z \to z^2 + c$, rational external angles with even denominator are pre-periodic and have corresponding external rays which land at Misiurewicz ...
-1
votes
1answer
35 views

Probability of sum of dice rolls combinatorics [closed]

The question is as follows. A cyclist is going for a bike journey of 1950 kilometres. Every morning he tosses a die, and if the outcome is k, where k = 1, 2, . . . , 6, he cycles 10k kilometres on ...
5
votes
2answers
78 views

A combinatorial identity.

Let $n \in \mathbb N$ and $X_1,\ldots,X_n$ be subsets of $\{1,\ldots,n\}$ such that there is some $p$ such that $\forall i\in \{1,\ldots,n\}, |X_i|=p$. Suppose as well that there is some $q$ ...
0
votes
1answer
35 views

Linear Permutations of $n$ objects

Suppose there are $n$ distinct objects $O_{1},O_{2},O_{3},\ldots,O_{n-1},O_{n}$. We have to find out the number of ways we can arrange them. But, there is a catch. We have to arrange them such that ...
1
vote
1answer
34 views

Nth pemutation of Lexicographic String

Can someone please explain the logic behind the mathematical equation, that for finding the Nth Lexicographic rank of a string the Leading Entry is $a_q$ if $k=q\cdot (n!)+r.$ The link to the problem ...
1
vote
4answers
47 views

How many ways letter can be placed in the box?

There are 6 letters and 6 boxes numbered 1 to 6 , letters are to placed in the box such that letter having number 1 should not be placed in box having number 1 and so on. Letter 1 is fixly placed in ...
4
votes
6answers
2k views

A die is rolled 3 times. What is the probability that a five is rolled at least twice?

The probability of not getting a five is $(\frac56)^3$, and I figure the probability of getting at least one 5 is $1-(\frac56)^3$, but I don't know how to figure out if it is rolled at least twice. ...
0
votes
2answers
22 views

Number of ways to distribute 4 objects in 6 drawers with some restrictions

The question is: We have 4 different objects, and 6 drawers on top of another. So the question in how many ways can we distribute the objects to the drawers so that the top drawer will have exactly ...
1
vote
0answers
16 views

Definition of minimal presentation of a group

I'm working on a problem on the braid monodromy of complex lines arrangements in $\mathbb{C}^{2}.$ I have the following question. It's just a simple definition. However, I didn't find anywhere. Let ...
1
vote
4answers
136 views

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^{m}x_i=10$ [closed]

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^m x_i=10$ A. $89$, B. $91$, C. $92$, D. $120.$
7
votes
2answers
3k views

How can I assign weights to coins so that they can be counted in a single weighing?

I was sorting out the coins in my loose-change jar the other day, and the following thought crossed my head: Is it possible to deduce the number of each type of coin in this pile by simply weighing ...
1
vote
2answers
44 views

Number of circular permutation of word 'CIRCULAR' [closed]

Hey please help me with this question... Find the number of circular permutation of the word 'CIRCULAR'. Number of circular permutaion is (n-1)!
-4
votes
0answers
40 views

Sequence and Divisibility

Consider a sequence $a_1$, $a_2$, ..., $a_9$, $a_{10}$, with $a_1=a_{10}$, such that for $i \neq j$, $a_ia_j$ is divisible by $n$ if and only if $|i-j| \neq 1$. What is the minimum value of $n$?
2
votes
3answers
682 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
1
vote
1answer
36 views

Proof By Induction Using Binomial Coefficients

I'm having a really hard time with this proof by induction: Prove this formula by induction: $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$. Easy enough, right? Wrong. I have to do it using ...
2
votes
2answers
42 views

Letters of the word “PARAMETER” [closed]

I have one question that bothers me. The total number of words that can be made by writing the letters of the word PARAMETER so that no vowel is between two consonants. The answer is 1800. I couldn't ...
1
vote
1answer
23 views

Finding the coefficient of a power series

How would I find the coefficient of: $[x^{10}]x^6(1-2x)^{-5}$ I know that I can simplify this as follows: $[x^4](1-2x)^{-5}$ and that generally the following formula would be used to solve this: ...
0
votes
2answers
22 views

Possible number of throws in nonagonal dice (ie. two nine-sided dice) [closed]

I have two nine-sided die. Or, in other words, a single pair of nonagonal dice. I was hoping someone could help me with two questions…. How many combinations can be possibly thrown (in a single ...
0
votes
2answers
35 views

Probability using combinatorics problem

The problem is simple: "Find the probability of getting no aces with four dice". Now, i'm supposed to solve this using combinatorics. So, I see two ways of doing this. First: considering my sample ...
0
votes
1answer
20 views

The Probability of 4 heads given the first toss is a head

The Question Alice tosses a fair coin seven times. Find the probability that she tosses 4 heads given her first toss is a head. Then, find the probability that she tosses 4 heads given her first and ...