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)

0
votes
1answer
1k views

Combinatorial proof of $\sum \limits_{k=1}^n k {n\choose k}^2 = n {2n-1 \choose n-1}.$ [closed]

Give a combinatorial proof & proof using generating functions of the following identity: $$\sum_{k=1}^n k {n\choose k}^2 = n {2n-1 \choose n-1}.$$
1
vote
1answer
142 views

Can we get general computational complexity of finding factors of two almost prime number N if it is not divisible by 2,3,5?

What is computational complexity of finding factors of two almost prime number N, which is not divisible by 2 and 3 and 5? Can we help our selfs with knowledge that we know digit sum of that number ...
5
votes
2answers
483 views

Probability that a triangle can be formed from a permutation of three edges of random length

What is the probability that a particular set of integer edge lengths selected from an interval $[1, N]$, can form a triangle? How might this extend to the case where one selects real number edge ...
5
votes
2answers
250 views

regarding Pigeonhole principle

Let A be a set of 100 natural numbers. prove that there is a set B $$B\subseteq A$$ such that the sum of B's elements can be divided by 100 I am stuck for a few days now. Please help!
0
votes
1answer
67 views

Possibility of constructing a desirable subset

Here is a question.I am quoting it: Question by user Nahum Litvin Let A be a set of 100 natural numbers. prove that there is a set B B⊆A such that the sum of B's elements can be divided by ...
-1
votes
1answer
823 views

Given an Alphabet, how many words can you make with these restrictions.

I'm trying to understand from a combinatoric point of view why a particular answer is wrong. I'm given the alphabet $\Sigma = \{ 0,1,2 \}$ and the set of 8 letter words made from that alphabet, ...
2
votes
1answer
169 views

Is the following product of $q$-binomial coefficients a polynomial in $q$?

$$\frac{\binom{n}{j}_q\binom{n+1}{j}_q \cdots\binom{n+k-1}{j}_q}{\binom{j}{j}_q\binom{j+1}{j}_q\cdots\binom{j+k-1}{j}_q}$$ where $n,j,k$ are non-negative integers.
0
votes
1answer
416 views

Counting the number of combinations when some values are fixed

A reading list for a humanities course consists of 10 books; of which 4 are biographies and the rest are novels. Each student is required to read a selection of 4 books from the list including ...
3
votes
1answer
150 views

How many possible solutions for 6 wires?

Imagine 2 sets of 6 wires. How would I find how many possible connections there are? Every wire must be used to be considered a connection. ...
2
votes
1answer
493 views

Proving that every non-negative integer has an unique binary expansion with generating functions

Could you tell me how can I prove that every non-zero integer has an unique binary expansion using the generating functions, please?
2
votes
1answer
2k views

How many maximum number of isosceles triangle are possible in a regular polygon of $n$ sides?

How many maximum number of isosceles triangle are possible in a regular polygon of $n$ sides? By separable theorem, we can say that "All regular $n$-sided polygons are separable into n congruent ...
3
votes
2answers
269 views

Given a finite list of prime factors, what is the fastest way to find all numbers that can be formed from them

$$ \text{Let} \ S = \{p_1,p_2,p_3,...,p_n\} $$ $$ \text{where} \ p_i \in \Bbb P$$ What is the fastest known method method/algorithm to generate all unique numbers through product operation on $S$? ...
0
votes
1answer
712 views

Dimension of the vector space of homogeneous polynomials.

Let $R$ be a polynomial ring with $n_k$ variables of degree $k$, for $1\leq k\leq m$. Is there a writeable formula to express the dimension of the vector space $R_l$ of degree $l$ homogeneous ...
2
votes
0answers
203 views

Minimum number of circles to fill up a square

Suppose there is a square each of side $a$. I want to fill the square with circle of radius $r$. How many overlapping circles are needed to fill up the square?
5
votes
1answer
379 views

Counting some special derangements

A derangement of a list of $n$ distinct entries is a permutation of that list such that no corresponding entries match. It is well-known that the number of such derangements is the nearest integer to ...
3
votes
2answers
140 views

Calculate max/min of $x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$

What is a good way to calculate max/min of $$x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$$ where $x_1+y_1+z_1+w_1=a$ and $x_2+y_2+z_2+w_2=b$ and $x, y, z, w, a, b \in \mathbb{N} \cup \{0 \}$, and please explain ...
8
votes
4answers
364 views

Why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k} = 0$?

I know that the expansion of $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k}$ equals to zero. But why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$ also equal to zero for $n \geq 2$? I've been ...
5
votes
1answer
173 views

a question on summation expansion

Q1. $$\sum\limits_{j=0}^{N-1} \sum\limits_{i=0}^{N-1} \sum\limits_{y=0}^{j} \sum\limits_{x=0}^{i} a(x)a(y)b(|x-y|) $$ Given that $b(0) = 0$, Find the coefficient of $b(k)$, $0\le k \le N-1$ in the ...
3
votes
1answer
1k views

Counting the number of directed graphs with $N$ vertices and $E$ edges?

Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even ...
1
vote
1answer
277 views

Deriving recursion from generating function

Given a generating function for some sequence, I'm basically interested in the first few values. Well an explicit closed form would be nice, but often there isn't any. I suppose if there is any, I'd ...
1
vote
1answer
863 views

How many PINs can you make with x digits?

You want to access a particular smartphone which has a 4-digit numeric pin, entered by tapping the screen. One day you see the owner wipe the screen, unlock the device, and then get distracted and ...
2
votes
3answers
98 views

Count points and lines in $\mathbb{A}^2(\mathbb{F}_p)$

Let $p$ be a prime, then $\mathbb{F}_p$ is a finite field. $\mathbb{A}^2(\mathbb{F}_p)$ is an affine plane. Number of points in $\mathbb{A}^2(\mathbb{F}_p)$ is $p^2$. I look at a line equation ...
8
votes
3answers
406 views

Non-probabilistic proofs of a binomial coefficient identity from a probability question

Combining the answers given by me and Ralth to the probability question at Probability Question, we get the following identity: $$ \sum\limits_{k = m}^n {{n \choose k}p^k (1 - p)^{n - k} {k \choose ...
2
votes
1answer
237 views

Vector spaces, Linear mappings and a relation to the inclusion-exclusion principle

Exercise Let $S$ be a set containing $n$ elements and $V$ be the $2^n$-dimensional vector space of all mappings $f : 2^S \rightarrow \mathbb{C}$. Let $\phi : V \rightarrow V$ be a linear map ...
1
vote
0answers
145 views

Efficient factorion search in arbitrary base

A factorion in base $N$ is a natural number equal to the sum of the factorials of its digits in base $N$. So, the decimal factorions are: $1 = 1!$ $2 = 2!$ $145 = 1! + 4! + 5!$ $40585 = 4! + 0! + 5! ...
3
votes
1answer
99 views

Counting possibilities of building words

Let $k \geq 1$ be fix and $b_n$ be the amount of possible words $w = v_1 \cdots v_n$ of length $n$ on the alphabet $\{1,\ldots,k\}$, such that $v_i \neq v_{i+1},\; 1 \leq i \leq n -1$. a) Show by ...
11
votes
1answer
307 views

Regularizing divergent series and Bernoulli numbers

Here is the actual problem I need a proof for: (I made an error writing down the equation initially) $$B_{k+1} = \frac{(-1)^k}{2^{k+2}-2} \sum_{q=0}^{k} \binom{k+1}{q} 2^q B_q$$ Below is my ...
7
votes
2answers
458 views

Counting Irreducible Polynomials

I'm investigating irreducible polynomials over finite fields at the moment, and I wanted to know if there is a formula for the number of irreducible polynomials of degree n over a fixed finite field ...
4
votes
2answers
277 views

How many ordered triple $ (p,a,b) $ is possible such that $p^a=b^4+4$?

If we have a prime number $p$ and two natural numbers $a$ and $b$ such that $p^a=b^4+4$, then how many such ordered triplets $(p,a,b)$ exist? What should be the strategy to solve this one? The only I ...
3
votes
1answer
226 views

Number of ways of dividing a set into a set of sets

This is really two related questions. First, it seems to me that given a set of $n$ objects you can divide it into a set of subsets of $a_1$ sets containing $n_1$ objects, $a_2$ sets containing $n_2$ ...
6
votes
5answers
1k views

Algebraic proof that collection of all subsets of a set (power set) of $N$ elements has $2^N$ elements [duplicate]

In other words, is there an algebraic proof showing that $\sum_{k=0}^{N} {N\choose k} = 2^N$? I've been trying to do it some some time now, but I can't seem to figure it out.
58
votes
2answers
2k views

Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol ...
0
votes
1answer
175 views

counting the number of subsets defined by a partition

let $\nu=(\nu_1,\cdots,\nu_k)$ be a partition of $n$. to $\nu$ corresponds $\alpha=(\alpha_1,\cdots,\alpha_n)$ where $\alpha_i$ is the number of $i$ in $\nu$ for example to $\nu=(112)$ a partition of ...
2
votes
2answers
3k views

Bijective proof? Examples?

I'm having trouble with understanding bijective proofs. I searched a lot, but I could not find a simple and well-explained resource. Can you give a simple example of a bijective proof with ...
3
votes
1answer
358 views

Probable positions in line to share birthday in birthday problem

While reading through about the birthday problem on Wikipedia, I came across some of the variations described in formulating the problem, notably Another generalization is to ask how many people ...
1
vote
2answers
406 views

Representing the $q$-binomial coefficient as a polynomial with coefficients in $\mathbb{Q}(q)$?

Trying a bit of combinatorics this winter break, and I don't understand a certain claim. The claim is that for each $k$ there is a unique polynomial $P_k(x)$ of degree $k$ whose coefficients are ...
0
votes
1answer
147 views

How many unique posibilities of n numbers out m numbers?

Say I have a set with the numbers 1, 2, 3... m. How many unique combinations can be made of n numbers out of that set?
6
votes
3answers
114 views

Numbering students inequality problem

Ten students are sitting around a campfire. A teacher randomly assigns each student a different number from 1-10. Another teacher assigns a new number to each student with the requirement that the new ...
2
votes
4answers
105 views

How to “efficiently” compute the number of solution of $25x= 5y+8z$ such that $x,y,z \in [0,9]$ and $x,y,z \in \mathbb{W}$?

The mother problem: Find the sum of all $3$ digit numbers which are equal to $25$ times the sum of their digits. So we can write: $$\begin{align} 100x+10y+z &= 25 ...
4
votes
1answer
366 views

Ramsey number for books

Given a triangular book $B_n$ I am trying to prove that $r(B_n,B_n)\le 4n+2$ where $r(B_n,B_n)$ is defined as the least positive number such that any graph $G$ on $r(B_n,B_n)$ vertices either has a ...
6
votes
2answers
294 views

Is there a binomial identity for this expression $\frac{\binom{r}{k}}{\binom{n}{k}}$?

What I'm trying to prove is this summation: $$\sum_{i=0}^{k} \dfrac{\dbinom{r}{i} \cdot \dbinom{n - r}{k - i}}{\dbinom{n}{k}} \cdot i = \dfrac{r}{n} \cdot k$$ I used induction on $k$ as follows: ...
0
votes
2answers
80 views

Relating Combinatorical Equations to Operations on Sets

In my university we learn Set Theory prior to starting Combinatorics but they don't seem to be making a clear and explicit connection between the two. Yet it seems to me that there is in fact a very ...
5
votes
2answers
525 views

Number of positive integral solutions for $ab + cd = a + b + c + d $ with $1 \le a \le b \le c \le d$

How many positive integral solutions exist for: $ab + cd = a + b + c + d $,where $1 \le a \le b \le c \le d$ ? I need some ideas for how to approach this problem.
6
votes
1answer
215 views

Is there a combinatorial interpretation for these identities?

I recently stumbled across the two seemingly similar identities $$ \prod_{i\geq 1}\frac{1}{1-xq^i}=\sum_{n\geq 0}\frac{x^nq^n}{(1-q)(1-q^2)\cdots(1-q^n)} $$ and $$ \prod_{i\geq ...
3
votes
2answers
333 views

Number of nonnegative integral solutions of $x_1 + x_2 + \cdots + x_k = n$

To find all solutions greater than or equal to $1$ of a linear equation in the form $$x_1+x_2+x_3+\cdots+x_k=n ,$$ the number of them is $\binom{n-1}{k-1}$. If I need all solutions to be greater or ...
5
votes
2answers
194 views

Partitions in which no part is a square?

I asked a similar question earlier about partitions, and have a suspicion about another way to count partitions. Is it true that the number of partitions of $n$ in which each part $d$ is repeated ...
2
votes
1answer
233 views

How to solve the following combinatorics problem?

There are $C$ kinds of colored balls, with $f_i$ being the frequency of each color $c_i$, such that $\Sigma_{i=1}^{C}f_i = n$, and $F= max(f_i)$. Let $G(x)$ be the number of ways in which these $n$ ...
2
votes
3answers
139 views

Combinatorics question concerning two square-board game pieces

I have a combinatorics problem to solve, and I'm realy not sure how to do it. Here's the problem: In [0,0] of a plane is a black piece and in [n,n] is a white one. The black moves each second per 1 ...
3
votes
1answer
433 views

Prove $n_0=(k-1)n_k+(k-2)n_{k-1}+\dots+3n_4+2n_3+n_2+1$

I want to prove $$n_0=(k-1)n_k+(k-2)n_{k-1}+\dots+3n_4+2n_3+n_2+1$$ for T as a binary tree where $n_i$ is nodes of degree $i$. I tried to prove it using the handshake lemma but came up with nothing ...
1
vote
1answer
257 views

A perpetual calendar cubes spinoff problem

Perpetual calendar cubes keep track of the date all year around. They must be turned (or even transposed) once a day. The following is a spinoff problem I'm having trouble with. Any hints are much ...