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.

learn more… | top users | synonyms (4)

0
votes
1answer
47 views

Does any one know a closed form for $1+\sum \limits_{s=1}^{d} \frac{x^s}{1-x^s}$?

Does any one know a closed form for $1+\sum \limits_{s=1}^{d} \frac{x^s}{1-x^s}$? To me, it is the generating function $f(x)=\sum f_n x^n$, where $f_n$ counts the number of composition of $n$ that ...
1
vote
0answers
52 views

Finding a formula for number of permutations satisfying pattern constraints

I'm trying to find a formula that gives the number of unique permutations of a set of 3 values of n length given a set of constraints. The values: $-1, 0, 1$ Example Set: $[0, -1, 1, 1, 1, 1]$ the ...
-1
votes
1answer
18 views

number of combinations of numbers 1 to 12

I have 12 couples meeting for dinner each week in groups of 4. How many times can they meet without any couple meeting twice? Is there a table I could use to figure all the ...
3
votes
4answers
66 views

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size 2 are there? 2.How many subsets are there altogether?

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size $2$ are there? 2.How many subsets are there altogether? Answer: 1) I think there are $7$ subsets of size two are ...
1
vote
1answer
21 views

Giving coordinates in a projective plane

When we are giving coordinates to the points of the Fano plane, we do so by giving every point a triplet: $(a_1, a_2,a_3)$ from $\mathbb F_2$ so that if three points are collinear then the pointwise ...
3
votes
2answers
75 views

how many distinct values does it have?

I solved this problem by manually adding parentheses and counting them, and got correct answer of 32. Is there a simple to find the answer? Thanks. The value of the expression $1÷2÷3÷5÷7÷11÷13$ ...
1
vote
2answers
36 views

How many ways are there to order $n$ women and $n$ men in circle

I have the following question : How many ways are there to order $n$ women and $n$ men in circle so there is no man next to man and no woman next to man meaning the order is man,woman,man,woman... ...
0
votes
0answers
16 views

Approximating the coefficients of $\prod_{i=1}^{N}\frac{1}{1-\frac{1}{2}q^i}$ for large $N$

I have $$\frac{1}{2^{N}}\prod_{i=1}^{N}\frac{1}{1-\frac{1}{2}q^i}$$ the reciprocal of the q-Pochhammer symbol $(\frac{1}{2},q)_{N+1}$ (multiplied by a power of $1/2$). Its Maclaurin series for ...
1
vote
0answers
52 views

Lower bound related to Goldbach conjecture

I am curious to know if a lower bound on the number of ways (call this $\beta$ and assume $p_1 + p_2$ distinct from $p_2 + p_1$) in which two primes $p_1, p_2$ that add up to a given even integer $n$, ...
2
votes
0answers
16 views

Is a simplex with permuted vertices $\pm$homologous to the original?

Take a singular $n$-simplex $\sigma: \Delta^n \to X$, where $\Delta^n\subset \mathbb{R}^{n+1}$ is the convex hull of the standard basis, with the obvious vertex ordering. Then one can obtain $(n+1)!$ ...
2
votes
2answers
24 views

Construction of a finite projective plane of order $p$, for any prime $p$

I have this construction of a finite projective plane (FPP) of prime order $p$, but I am not sure what's going on. We have already proved that FPPs of order $q$ have $q^2+q+1$ lines and points (if ...
-2
votes
2answers
19 views

Hints for Solving Elementary Combination problem of Doughnuts. [on hold]

There are eight varieties of Doughnuts, if a box contains $1$ dozen doughnuts how many different option are there for a box of doughnuts ?
0
votes
0answers
24 views

Understanding Theorem on Combinatorics.

What following Theorem wants to convey (how there can be infinite repetitions), pls give some examples to explain.
3
votes
2answers
128 views

How large can a set of pairwise disjoint 2-(7,3,1) designs (Fano planes) be?

As wikipedia defines well, the Fano plane is a small symmetric block design, specifically a 2-(7,3,1)-design. The points of the design are the points of the plane, and the blocks of the design are the ...
3
votes
1answer
54 views

Tic Tac Toe: What is the probability that a random player draws against an infallible player?

I have simulated a tournament between an infallible Tic Tac Toe player and one that chooses its moves randomly. Even after 5 million games, the infallible player wins every single game. I know that ...
0
votes
0answers
48 views

Number of valid parenthesis

I have to find out the number of valid parenthesis.Parenthesis are of two type [] ,(). How many ways are there to construct a valid sequence using ...
0
votes
1answer
34 views

Calculating the coefficient of a generating function

Calculate the coefficient of $x^{10}$ in $$\frac{1+x^3}{1-2x+x^3-x^4}$$ I am unsure how to even start and would appreciate a hint? I haven't dealt with problems like this (complicated) before.
17
votes
5answers
851 views

A strange combinatorial identity [duplicate]

In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to ...
0
votes
1answer
34 views

Number of possible subsequences

Given 4 integers - $A,B,C,D$ such that $A \leq B \leq C \leq D$ (i.e they are in non decreasing order). Now we need to find number of possible non decreasing subsequences $(W,X,Y,Z)$ such that $1 ...
6
votes
1answer
65 views

Matrices and prime numbers

Let $ p $ be a prime number and \begin{align} K=\left\{ \begin{pmatrix} a &b \\ c& d \end{pmatrix} \mid a,b,c,d \in \left\{0,1,\ldots,p-1 \right\}, \right. & a+d \equiv 1 \!\!\!\! ...
1
vote
1answer
60 views

How many partial derivatives does a multivariate polynomial have?

My motivation for this question is from the following toy example; define the (nondeterministic) finite state machine generated by the polynomial $f(x_0 , ... , x_n) \in \mathbb{Z} [x_0 , x_1 , ... , ...
-4
votes
0answers
17 views

Number of Non Decreasing Sequence. [on hold]

I have to find the number of non decreasing sequence (A,B,C,D) such that ...
0
votes
1answer
25 views

probability for two people to arrange something in the same order

What is the probability that two people independently arrange for instance a sequence of the $10$ elements: $0,1,2,3,4,5,6,7,8,9$, in the same order? I'm not sure how I should go about this problem, ...
5
votes
1answer
63 views

Combinatorial proof of a certain alternating sum of binomial coefficients

The following identity appeared as a question earlier today $$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 ...
1
vote
3answers
42 views

Seating arrangements of 7 boys and 5 girls in a row.

In how many ways can these boys and girls be arranged in a row if between two particular boys A and B there are no boys but exactly 3 girls?
142
votes
17answers
25k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
-1
votes
0answers
17 views

A SDR extension problem [on hold]

enter image description here I think we should use induction. for subset I when $|I|=1$ then we have for any $i\in \{1,\dots,n\}$ $|A_i|\leq 2$. Then for any $A_i$ we have $2$ SDR. then we suppose ...
4
votes
0answers
46 views

Find the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even

Let $n$ denote the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even. Find the last digit of $n$. There are two cases. $ab,cd$ is odd. Which means $a,b,c,d \in \text{odd}$. ...
6
votes
2answers
31 views

For a group of 7 people, find the probability that all of their birthdays do not occur in the winter using the stars and bars counting method

So for a group a 7 people, find the probability that all of their birthdays do not occur in the winter. That is, all of their birthdays occur either in the spring, summer or fall. Assume that the ...
9
votes
1answer
143 views

Application of Combinatorics/Graph Theory to Organic Chemistry?

Recently, I have been self-teaching graph theory and having an organic chemistry course at school. When I was learning isomer enumeration I found great resemblance between organic molecules and ...
1
vote
2answers
30 views

Total number of perfect square which are factors of n [on hold]

A number $N$ can be factorized as $$N = p_1^5 p_2^4 p_3^7.$$ Find total number of perfect square, which are factors of $N$.
4
votes
1answer
59 views

What is the probability that all $n$ colors are selected in $m$ trials?

I have a concrete problem, say, there are $n$ different balls ($n$ different colors to distinguish them), each ball will be selected uniformly at random. The way I choose a ball is that I randomly get ...
4
votes
1answer
29 views

On the GCD of two palindromes.

I had an observation. Which I will discuss below. My question will be Is my observation correct? If so, how can one prove it? Observation: Consider the string of palindromes below: $100...01$ and ...
3
votes
0answers
34 views

Isomorphism of Non-Symmetric Matrix when Permutation-Set is given: A simple observation

Context: Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not ...
0
votes
0answers
25 views
+50

What is the number of interior faces adjacent to an interior vertex in a triangulation in $\mathbb{R}^3$?

Let $\Omega$ be a polygonal domain in $\mathbb{R}^3$. Assume $\Omega$ is partitioned into tetrahedra using the most common admissible triangulation, that is, roughly speaking, two adjacent tetrahedra ...
3
votes
2answers
87 views

How can I prove this equation holds?

As the final part of a big proof I got for uni homework: (It is an extra question, may be unsolvable) $$k^n<\sum_{i=0}^n\binom{n}ik^{n-i}(2^i-1)$$ My idea is to develop the right side into an ...
0
votes
1answer
30 views

Letter combinatorics and probabilities

Hello I've got some problems and I don't know if my solutions are correct: Given a Text with two letters $A$ and $B$ and the the probability of occurrence of letter $A$ is $p_a$ and $B$ is $p_b$, the ...
1
vote
2answers
62 views

Sum of odd integers $= x$

How many sums are there that add up to a whole number $x$, and are made of only odd numbers? Each number can be used more than once.
1
vote
0answers
26 views

Vandermonde-type convolution with geometric term

Is there a closed-form solution to the following sum? \begin{align*} f(r, s, n) = \sum_{k=0}^{n}c^k\binom{r}{k}\binom{s}{n-k} \end{align*} I know this corresponds to find the coefficient of $x^n$ of ...
2
votes
1answer
33 views

Probability - Combinations

I am having big problems with this exercise: There are $n$ customers and $k$ types of products and number $i$, where $n \ge k \ge i$. I have to find the probability of the situation where ...
-3
votes
1answer
51 views

What is the probability of getting intial state (read details)? [closed]

Alex, Bob and Charlie each have 5 different colored marbles in their bags(same 5 colors in each of those bags though). Alex randomly picks a marble from Bob's box and puts it into his bag. Then ...
1
vote
1answer
20 views

Pigeonhole Principle by using induction

Prove the generalized Pigeonhole Principle: Let $n$ and $m$ be natural numbers, $X$ and $Y$ sets with $|X| = mn + 1,\; |Y | = n$, and $f : X\to Y$ a function. Then there exists $y \in Y$ such that ...
3
votes
2answers
61 views

How many colours do we at least need so that we can ensure all 250 countries have different flags.

One for FN standardized flag consists of three horizontal rectangular fields. If we assume that the middle field not are allowed to have the same colour as the top or bottom field, how many colours do ...
6
votes
1answer
42 views

Tokens in boxes problem

Tokens numbered $1,2,3...$ are placed in turn in a number of boxes. A token cannot be placed in a box if it is the sum of two other tokens already placed inside that box. How far can you reach for a ...
0
votes
1answer
53 views

Number of additive partitions [closed]

Show that the number of additive partitions of $n$ in which no summand appears more than $d$ times equals the number of additive partitions of $n$ in which no summand is a multiple of $d+1$. Now ...
0
votes
2answers
40 views

12 books shelf and bag.

I got two varieties for the same question: Ways that four books out of a bag of 12 books can be placed on a shelf. Ways to choose 4 books out of 12 arranged on a shelf and put them in a bag. ...
1
vote
2answers
40 views

Number of possible arrangements of rings on a hand

This is a homework question that I'm having trouble figuring out how to start. Here's the question. A woman has 3 different rings. On any given day she wears 1, 2, or (inclusive) 3 of her rings on ...
2
votes
1answer
18 views

Suppose a bookshelf contains five discrete math texts, two data structures texts, six calculus texts, and three Java texts

(a) How many ways can you choose one of the texts? (b) How many ways can you choose one of each type of text? Solution: a) By the rule of sum, there are all together $5 + 2 + 6 + 3 = 16$ ...
4
votes
1answer
24 views

There are how many ways can we list, without repetition of all the elements of $S = \{ x, y, z\}$

Solution: there are six ways: $xyz$, $xzy$, $yxz$, $yzx$, $zxy$ and $zyx$. Doubt: How do we know there are six possible ways?
0
votes
1answer
40 views

How many coefficients in $(x_1 +x_2 + \cdots + x_L)^N$?

How many coefficients in $(x_1 + x_2 + \cdots + x_L)^N$? That is to say, what is the number of coefficients when it represents as sum of products.